ABC136 F. Enclosed Points
問題
2次元平面上にN個の点があり、各点のx座標、y座標はそれぞれ相異なる。
この点からなる集合Sについて、Sの空でない部分集合Tを考える。
f(T) := 各辺が座標軸と平行であってTの点をすべて含むような最小の長方形に含まれる点の個数
と定めるとき、Sの空でないすべての部分集合Tについてf(T)の和を求めよ。
答えは大きくなるため998244353で割ったあまりを求めよ。
制約
- 1 <= N <= 2*10^5
- -10^9 <= x_i, y_i <= 10^9
- x_i != x_j (i != j)
- y_i != y_j (i != j)
解法
求める答えは「Σ_T f(T)」であるが、f(T)は「Σ_{点} 点はTに含まれるか」なので、「Σ_T Σ_{点} 点はTに含まれるか」と考えられる。
ここで、2つのΣは入れ替えてもよいことから、「Σ_{点} Σ_T 点はTに含まれるか」と考えると、各点について、その点を含むような部分集合の数を数え上げる問題と考えることができる。
ある点について、その点を含むような部分集合を考えると、その点から左上、左下、右上、右下にある点の数がわかれば、2^{その点の数}-1の部分集合が考えられる。
したがって、4方向について2^4通りの組み合わせ方の点を作れば良い。
(ただし、左上と右下、左下と右上の点を選んでいる部分集合の場合は、注目している点自身を含まないような集合でも点の数としてはカウントされるので、注目点のある/なしの分を考慮するため2倍にする)
ある点について、その点より左上、左下、右上、右下にある点の数を数える。
これは、BIT/FenwickTreeで左から右、下から上に点を入れていきながら数え上げられる。
(実装では、2^xは毎回計算すると遅くなってしまうため、事前計算しておく。)
ABC158 F. Removing Robots
問題
数直線上に1～Nの番号のついたロボットが置かれている。
ロボットiは座標X_iにあり、スイッチを入れるとD_iだけ移動し、直後取り除かれる。
また、以下の操作を好きなだけ行える。
- ロボットを1つスイッチを入れる。どれかのロボットが移動している間はこの操作は行えない。
ロボットは、X_i以上X_i+D_i未満に他のロボットがあった場合、そのロボットもスイッチが入り、これが再帰的に繰り返される。
これらの操作を繰り返したあとに残っているロボットの組合せは何通りありえるか？
998244353で割ったあまりを求めよ。
制約
- 1 <= N <= 2*10^5
- -10^9 <= X_i <= 10^9
- 1 <= D_i <= 10^9
- X_i != X_j (i != j)
解法
あるロボットiが起動した場合、連鎖的にどのロボットまで起動してしまうか？がわかれば、X_iの大きいロボットから逆方向に向かってdpで求められる。
以下、ロボットをX_i順に並べたもので考える。
このdpは、
dp[i] += dp[i+1]
dp[i] += dp[連鎖最後のロボットのindex + 1]
で求められる。
ロボットiを起動した場合の連鎖で起動する最後のロボットのindexをR[i]とする。
X_iが大きい方から処理していくことを考えると、R[i] = max(i, X_i以上X_i+D_i未満にあるR[j])で求められるので、SegmentTreeでRangeMaximumQueryを行えば求めていける。(X_iとX_i+D_iは座圧しておく)
ABC158 E. Divisible Substring
問題
0から9までの数字からなる長さNの文字列が与えられる。
この文字列の空出ない連続する部分文字列を考える。
部分文字列を数字として見たときに、素数Pで割り切れるものの個数を求めよ。
ただし、0から始まるものでもよく、それらは異なる数字とみなす。
制約
- 1 <= N <= 2 * 10^5
- 2 <= P <= 10000
- Pは素数
解法
元の文字列の数字は、
S[0] * 10^(N-1) + S[1] * 10^(N-2) + ... + S[N-1] * 10^0
のように考えることができる。
これのmod Pは、各桁について「S[i] * 10^(N-i-1)」のmod Pを足したものに相当する。
なので、ある部分文字列を考えるというのは、iからjまでの↑の和のmod Pで求められ、それが0になるようなものの個数を求める問題になっている。
単純に考えるとO(N^2)になってしまうが、低い桁からの累積和を考えて、iまでの累積和sum[i]と同じ値が0～i-1までに何個出ているか？を考えれば、その地点からiまでの和は0なので、求められる。
また、sum[i]自体が0の場合は、それ単独でmod P=0になるので、+1する。
ただし、コーナーケースとして、P=2,5のときは、「S[i] * 10^(N-i-1)」がN-i-1>0だと10の倍数でPで割り切れてしまうため、答えも0になってしまう。
P=2,5のときは、Pが小さいのでO(N*P)のdpで解くか、2,5で割り切れるかは最後の桁がPで割り切れるかで決まるので、S[i] mod P = 0ならi+1を加える処理でO(N)で求められる。
ABC156 E. Roaming
問題
n個の部屋があり、最初各部屋には1人ずついる。
ここで、ある部屋iから別の部屋j (i != j)へ移ることを「人の移動」と呼ぶことにする。
人の移動がk回起きたことがわかっているとき、各部屋にいる人数の組合せとして何通りあり得るか、10^9+7で割ったあまりを答えよ。
制約
- 3 <= n <= 2*10^5
- 2 <= k <= 10^9
解法
まず、どのような状態が答えとしてありえるか？を考える。
k回移動なので、部屋の中で0人の部屋の数は0～min(N-1, K)だけありえる。
また、例えば、「m回移動があった部屋の状態」も、k-m回適当にどこかの部屋にいた人を移動させ、そこからm回動かすことでk回移動での答えになりえる。(調整可能)
したがって、「k回以下の移動のすべての部屋の状態(ある部屋の状態への最小の移動回数がk回以下がすべて)」が答えになり得る。
上記で、ぴったりk回移動を考えなくてよく、k回以下で達成できる部屋の状態を考えれば良いことがわかったので、k回以下の移動で条件を満たす組み合わせを考える。
各部屋の状態は、0人の部屋と1人以上の部屋がありえている。
ここで、0人の部屋の数がp(<=k)部屋あった場合、p人が残りのN-p部屋のいずれかに行っていることになるが、これはすべてk回以下の移動なので、すべて条件を満たす移動になっている。
この組合せは、0人の部屋のp部屋の組合せ「N_C_p」とp人がどの部屋に行くかの組合せ「(N-p)_H_p」から「N_C_p * (N-1)_C_p」で求められる。
メモ
- k回ぴったり→k回以下
- 「減る」「増える」が混ざっている→片方を固定して考える
- 最終的に0人＝1回減るだけ、または、減る＋１＝増える → 1回減るだけ考えればよい
- 最終的に1人以上＝移動なし、または、減る＜＝増える → 0回以上増えるだけ考えればよい
ABC155 F. Perils in Parallel
問題
数直線上にN個の爆弾が仕掛けられており、i番目の爆弾はA_iの位置で、スイッチの状態がB_i(OFFは0、ONは1)で与えられる。
制御装置にはM本のコードがあり、j番目のコードを切ると、L_j以上R_j以下の位置にある爆弾のスイッチの状態が入れ替わる。
切るコードをうまく選んで、すべての爆弾の状態をOFFの状態にできるか？
できる場合、どのコードを使うと良いか、答えよ。
制約
- 1 <= N <= 10^5
- 1 <= A_i <= 10^9, A_iは互いに相異なる
- 1 <= M <= 2*10^5
- 1 <= L_j <= R_j <= 10^9
解法
解説放送より。
範囲に対して操作するのは大変なので、imos法のように、値の差分を保持するような数列を考える。これによって、範囲は始点と終点の2箇所で扱うことができる。
例えば、数直線上の爆弾を左からスイッチの状態が001101のような場合、
0 0 0 1 1 0 1 0 # 元の状態の両端に0を加えたもの 0 0 1 0 1 0 1 # 上の各隣り合う要素間の差分(xor)を取ったもの
(下から上の数列に戻すには累積xorを前からとっていけば良い)
差分列の方で、要素を2つ選んでそれぞれ0/1を反転させれば範囲更新に対応する処理が行える。
次に、各コードについて考える。
各コードは、差分列でのどの位置とどの位置の0/1を反転させるかに対応している。
この位置は、適当に二分探索などで計算しておくことができる。
したがって、問題は、コード(2要素を選んで0/1を反転)をうまく選んで、差分列のすべて要素を0にできるか？を解くことになる。
差分列のある1になっているような要素に注目すると、そこからコードでつながる他の要素の状況に合わせて1を0にしなければならない。
なので、ある1になっている要素について、そこからコードでつながる連結成分を考える。
(この連結成分は多重辺やループなどを含んでいる)
辺(コード)を選ぶと両端の要素を反転させることができるが、どのように選べばすべての要素を0にすることができるか？
これは、DFS木を作って、リーフから決めていけば求められる。
もし、ある要素eにおいて、子の要素cが1だった場合、eとcの間の辺は使う必要がある。
要素e自体の値は、子の要素に対し、使った辺の数と、要素eの元の0/1によって決まる。これをルートまで繰り返して、ルートでの値が0になればよい。
もし、ルートでの値が1だった場合は、不可能。
ABC155 E. Payment
問題
AtCoder王国では、価値が1,10,100,1000,...,10^(10^100)の紙幣になっている。
今、商品の価値がNであるような商品を買いたい。
各紙幣は十分な枚数を持っているとした場合、この商品を買うために払う枚数とおつりの枚数を適切に最小化した場合、最小で何枚にすることができるか？
制約
- 1 <= N <= 10^1000000
解法
各桁に注目すると、ある桁での数字N_iをそのまま払う場合は、「払う枚数はN_i枚、お釣りは0枚」で、もしそれよりも大きい価値の紙幣で払う場合は、「払う枚数は1枚、お釣りは(この桁については)10-N_i枚」になる。
したがって、各桁について、そのまま払うか？、より価値の高い紙幣で払うか？の選択が考えられるため、これをdpで求める。
dp[i][j] := i番目の桁で、j=1なら一つ前の桁で高い紙幣で払うことにした、j=0ならしなかった場合の、最小やり取り枚数
遷移は、もらうDPで考えると、i+1番目の桁では、
- dp[i][0]から、そのまま払う+N_iか、高い紙幣で払う+(10-N_i)か
- dp[i][1]から、そのまま払う+(N_i+1)か、高い紙幣で払う+(10-(N_i+1))か
の4種類で、
int n = N[i]-'0'; dp[i+1][0] = min(dp[i+1][0], dp[i][0] + n); dp[i+1][1] = min(dp[i+1][1], dp[i][0] + (10-n)); dp[i+1][0] = min(dp[i+1][0], dp[i][1] + (n+1)); dp[i+1][1] = min(dp[i+1][1], dp[i][1] + (10-(n+1)));
のような感じになる。
(Nにleading-zeroをつけて計算しておくと、最上位付近の桁での計算を木にしなくて良くなる)
ABC155 D. Pairs
問題
N個の整数A_iが与えられる。
このうち、2つを選んだ積の組合せをすべて考えると、これはN*(N-1)/2個できる。
小さい方からK番目の積が何になるか答えよ。
制約
- 2 <= N <= 2*10^5
- 1 <= K <= N*(N-1)/2
- -10^9 <= A_i <= 10^9
解法
積を小さい方から並べた数列Bを考える。(これは実際には列挙できない)
Bのうち、「x未満の個数」が高速に求められれば、K番目の要素は、「x未満の個数がK未満」の部分を二分探索すれば求められる。
例えば、Bが「1,2,4,4」の場合、「x未満の個数」をmとすると、
x 1 2 3 4 5 m 0 1 2 2 4
のようになるので、K=3だった場合は、xが4と5のところで分かれるので3番目に来るのは「4」だとわかる。(K=4でも、K未満となる位置は同じなので、答えが「4」であることがわかる。)
したがって、Bにおける「x未満の個数」を高速に求めれば良い。
今回、A_iは0や負もあり得るため、その積はやや複雑になっている。
正だけだった場合は、A_iを小さい順からソートして、二分探索でx未満となる位置を求めて個数を計算すれば、O(N*log(N))で求められる。
しかし、今回は負もあるため、負*負や負*正の時を気をつける必要がある。
実装的には、A_iを「①0未満のもの」と「②0以上のもの」と分けて、
①*①と①*②と②*②それぞれで個数を求めて合計してあげればよい。
(①*①のときは、負*負になるため、逆順にソートして上げると順方向の二分探索ができる。
①*②のときは、負*正になるため、②側のものを逆順にソートしてあげると順方向の二分探索にできる。
②*②のときは、正*正なので、そのまま二分探索してあげれば良い。)
ABC153 F. Silver Fox vs Monster
問題
N体のモンスターが一列に並んでいる。
i番目のモンスターは、座標x_iにいて、体力がh_iである。
今、爆弾を座標xに落とすと、x-D以上x+D以下の範囲にいるモンスターにダメージAを与えることができる。
すべてのモンスターの体力を0以下にするために必要な爆弾の個数の最小値を求めよ。
制約
- 1 <= N <= 2*10^5
- 0 <= D <= 10^9
- 1 <= A <= 10^9
- 0 <= x_i <= 10^9
- 1 <= h_i <= 10^9
解法
一番左にいるモンスターについて考えると、このモンスターを倒すためには、このモンスターを含む範囲の爆弾を倒すのに十分な回数落とす必要がある。
このモンスターの位置を左端とするような爆弾投下を十分な回数を透過したあと、次に一番左になるモンスターについても同様に考えていける。
したがって、貪欲法で、左から順番に処理していけば良い。
爆弾の投下によって、2*Dの範囲にいるモンスターに「A*投下回数」のダメージを与えることになるが、愚直にループを回すとO(N)かかってしまって間に合わない。
これは、遅延セグメント木やStarrySkyTree、imos法をしながら進めればO(logN)やO(1)で更新・取得ができる。
ABC133 F. Colorful Tree
問題
N個の頂点からなる木がある。
各辺iは、頂点a_iとb_iをつないでおり、1～N-1の整数で表される色c_iと、辺の長さd_iが割り当てられている。
このとき、以下のQ個の問いに答えよ。
「問いj: 色x_jのすべての辺の長さをy_jに変更したと仮定して、二頂点u_j, v_jの距離を求めよ」
(注意：各問いは独立で、変更は他の問いに影響しない)
制約
- 2 <= N <= 10^5
- 1 <= Q <= 10^5
- 1 <= c_i <= N-1
- 1 <= d_i <= 10^4
解法
まず、単純に2頂点間の距離を答えるだけの場合は、根付き木にして、LCAを求めて、「depth[u_j] + depth[v_j] - 2 * depth[lca(u_j, v_j)]」で求められる。
問いは、色x_jの辺の重みをy_jにするので、根付き木において、ある範囲内における色x_jの「辺の重みの合計」や「辺の数の合計」がわかれば、
答え＝「(u_jとv_jの距離) - (u_jとv_jの間の色x_jの辺の重み合計) + y_j * (u_jとv_jの間の色x_jの辺の変数合計)」
で求められる。
なので、基本的に、「根付き木について、根からある頂点までの間にある色がxの辺の重みや個数」を求めることが本質的な問題になっている。
1を根として、根付き木を考え、辺についてのEuler Tourを作ると上記のようになる。
行きがけは重みを＋、帰りがけは重みをーにして累積和を取ると、ある頂点vの根からの距離は、頂点vの根方向への辺eの重みの累積和を見ればO(1)で求められる。
(例：頂点5は、根方向への辺がe4で、それに対応するeuler tourのインデクスはi=3なので、その重みの累積和は50、とわかる)
辺の数についても同様に求められる。
ある色xについて考えると、この累積和のように、範囲内にある、色がxのものだけについて注目して累積和を求められばよいことがわかる。
なので、Euler Tourを各色ごとに分解して累積和を計算しなおしたものを考える。
ある頂点vについて、根方向への辺eに対応するeuler tourのインデクスがiだった場合を考えると、色がxのものだけに注目したい場合、その色だけ取り出した表の中でi以下となるインデクスを二分探索で求めてあげれば、ある色の辺だけについて重みの合計を求められる。
辺の数についても同様に求められる。
したがって、1つの問に対して、O(logN)程度で答えられるので、間に合う。
Euler Tourを使ったLCA
Euler Tourを作る際に、根からの深さを一緒に求めておく。
これを、RMQなどで、あるEuler Tourの範囲での最小の高さになっている辺(頂点)を求めてあげればよい。
ABC132 F. Small Products
問題
正の整数K個を一列に並べたもので、隣接するどの2つの整数の積もN以下であるようなものの個数を求めよ。
答えは10^9+7のあまりで求めよ。
制約
- 1 <= N <= 10^9
- 2 <= K <= 100
解放
計算量を無視して考えると、
dp[i][j] := i番目の整数がjだった場合の通り数
のように考えられる。
この遷移は、dp[i][j] = Σ_{1<=k<=N/j} dp[i-1][k]のようにして求めていける。
この計算量を減らすことを考える。
i番目が整数jと考えているときに、遷移のΣの「1<=k<=N/j」は、累積和を求めておけばO(1)で求められるので、O(K*N)になる。
さらに、この「N/j」に注目すると、例えばN=100に対し、j=98とj=99はどちらもN/jは1となっていることがわかる。
このように、N/jが同じになるjは遷移の右辺が同じになるので、まとめて計算することを考える。
N/jとしてありえる値は、j=1～√Nまでに対して、jとN/jを実際に出してみて、出てくる整数を考えれば良い。(setなどに入れておく)
この整数以外の、抜けてる整数は、個数がわかるので、出てくる整数のところにまとめて数え上げればよい。
したがって、全体でO(K*√N)程度で求められる。
yukicoder No.973 余興
問題
N個のシュークリームが一列に並べてあり、左からi番目のシュークリームはa_iキロカロリーである。
AさんとBさんは、Aさんから始めて交互に以下のいずれかの操作を繰り返す。
- 左側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを食べる
- 右側にあるシュークリームを含む、位置が連続した1個以上のシュークリームを食べる
ただし、一度に食べられるシュークリームの合計カロリーはXキロカロリー以下にしなければならない。
最後にシュークリームを食べた人が負けとする場合、どちらも勝利を目的に最適行動をした場合、どちらが勝者になるか判定せよ。
制約
- 1 <= N <= 5000
- 1 <= X <= 10^9
- 1 <= a_i <= X
解法
単純には、
dp[i][j] := 残っているシュークリームの左端がi番、右端がj番の時、この状態で取る人が勝てるか？
というものを考えると、dp[1][N]が答えになる。
しかし、これは、遷移がO(N)かかりうるため、全体ではO(N^3)で間に合わない。
ここで、dp表の形を考える。
(画像はN=5の場合)
このdp表を埋める場合の遷移は、
「右からいくつかシュークリームを食べる」場合は、マスの左側にあるマスで負マスがあれば、そこに遷移することで、相手に負けさせることができる。
「左からいくつかシュークリームを食べる」場合は、マスの下側にあるマスで負マスがあれば、そこに遷移することで、相手に負けさせることができる。
(遷移できる範囲はXによって決まっているので、各位置での遷移範囲はO(N^2)で前計算しておく。)
ここで、対角の赤矢印方向に順番に求めていけば、あるマスを考えるとき、左側または下側のマスはすでに計算済みとなる。
ここで、左側、下側に対して勝/負を1/0で表現した累積和をもつように一緒に計算していけば、O(1)で負マスがあるかどうかを判定できる。
これで全体をO(N^2)で計算できる。
また、累積和でなくてもBITなどでO(logN)で計算してもよい。
ABC152 F. Tree and Constraints
問題
N個の頂点からなる木が与えられる。この木の辺を白か黒で塗ることを考える。
M個の制約が与えられ、i番目の制約は「2つの頂点u_i, v_iのパス上の辺には黒色の辺が1つ以上存在しなければならない」となっている。
M個すべての制約を満たすような塗り方の通り数を答えよ。
制約
- 2 <= N <= 50
- 1 <= M <= min(20, N*(N-1)/2)
解法(辺に注目してbitDP)
各辺に注目すると、0個以上の制約に関連付いている。
辺を白に塗るか黒に塗るかで、すでに満たした条件かどうかの状態が変化していくので、これはbitDPで、
dp[i][j] := i番目までの辺で、すでに満たした場合bitが1になっているような条件の状態を表すjのときの通り数
として、dp[0][0] = 1からdp[i+1][j] += dp[i][j]かdp[i+1][j|mask] += dp[i][j](maskは辺iに関連する制約のbitマスク)で遷移させていけばよい。
解法(制約に注目して包除原理)
制約に注目すると、「制約をすべてを満たす」＝ U - 「制約を1つ以上満たさない集合」であり、「制約を1つ以上満たさない集合」は「各制約を満たさない集合」の和集合になっている。
したがって、この「各制約を満たさない集合の和集合」を求める。
これは、(制約1を満たさない集合) + (制約2を満たさない集合) - (制約1かつ制約2を満たさない集合)・・・のようになっており、包除原理で求められる。
また、制約を満たさない集合というのは、その制約すべてのパスの辺が白で塗られている場合なので、そのような塗り方は、白で塗る辺の数をxとして、「2^{N-1 - x}」で求められる。
うまく無駄な計算が発生しないようにしないとTLEするようなので、辺集合をbitで表現するなど無駄なループが発生しないよう気をつける。
(あと、解説放送で、途中計算がどこまで大きくなり得るか？が議論になってた)
ABC151 F. Enclose All
問題
平面上のN個の点が与えられる。
これらすべてを内部または周上に含む円の半径の最小値を求めよ。
制約
- 2 <= N <= 50
- 0 <= x_i, y_i <= 1000
- 与えられる点はすべて異なる
解法
いくつかの点を選び、それが円周上にあると仮定した場合の円を求めて、他のすべての点が含まれるか？をチェックする。
まず、凸包のある2点が周上にあると考えると、その2点の中点を中心にした2点間の距離の半分が候補の円となる。
次に、凸包のある3点が周上にあると考える。
鈍角三角形の場合は、鈍角ではない2点の中点を中心した2点間の距離の半分が候補の円となるが、上記の2点のときに列挙されているはずなのに無視してよい。
鋭角三角形の場合は、その3点を含む外心や半径はwikipediaの「外接円」のエントリで求め方が載っているので、それを参考に求めれば良い。
円に含まれるかのチェック時には、誤差を考慮して比較することを忘れない。
ABC150 D. Semi Common Multiple
問題
長さNの偶数の整数からなる正数列Aと整数Mが与えられる。
任意のk(1<=k<=N)に対して、以下の条件を満たす正の整数XをAの半公倍数と定義する。
X = A_k * (p + 0.5)を満たす負でない整数pが存在する
1以上M以下の整数のうち、Aの半公倍数の個数を求めよ。
制約
- 1 <= N <= 10^5
- 1 <= M <= 10^9
- 2 <= A_i <= 10^9
- A_iは偶数
解法
Xについて考える。
0.5を1/2として整理すると、
X = (A_k/2) * (2*p+1)
と書ける。
ここで右辺を見ると、(A_k/2)は任意の自然数、(2*p+1)は1以上の奇数になっている。
Xとしてあり得るものを考えると、
Xが奇数の場合、(A_k/2)もすべて奇数である必要があり、そうならば(A_k/2)の最小公倍数の奇数倍はすべて満たせる。
Xが偶数の場合、(2*p+1)が奇数なので、(A_k/2)もすべて偶数である必要がある。しかも、偶数であるだけでなく、Xを素因数分解してでてくる2^xのxと(A_k/2)を素因数分解してでてくる2^yのyは同じである必要がある。すべての(A_k/2)の素因数分解してでてくる2^xのxが等しいならば、Xは普通に(A_k/2)の最小公倍数の奇数倍はすべて満たせる。そうでなければXは存在しない。
M以下の(A_k/2)の最小公倍数の奇数倍の個数は、(A_k/2)の最小公倍数をLとすると、(M/L+1)/2で求められる。
また、最小公倍数はかなり大きくなり得るが、M以上になった時点で答えは0になるので、そこで打ち切って桁あふれしないようにする。
ABC131 F. Must Be Rectangular!
問題
2次元座標にN個の点が与えられる。
このとき、「座標(a,b),(a,d),(c,b),(c,d)のうちちょうど3箇所に点が存在するようなa,b,c,d(a!=c, b!=d)を選んで、残りの1箇所に点を追加する」という操作を繰り返す。
この操作回数の最大値を求めよ。
制約
- 1 <= N <= 10^5
- 1 <= x_i, y_i <= 10^5
- 与えられる各点に同じ位置のものはない
- 入力はすべて整数
解法
まず、答えとなる最終的な形を考える。
1回でも操作が行えるような頂点が存在する場合、そこに頂点を追加することで、長方形ができ、追加された頂点によってまた操作ができるようになって、これを繰り返すことで、巨大な格子が作れることがわかる。
したがって、この格子の形が求められれば、その格子の頂点からすでに存在する頂点を引けば操作回数の最大値がわかる。
格子を形成できる頂点は、同じx座標、または、y座標を共有しているはずなので、ある頂点から同じx座標、または、y座標になっている頂点を辿れる頂点すべてを見つければよく、これは、dfsで探すか、x座標とy座標それぞれを頂点とみなしてUnionFindで連結成分を見つけるようにすれば求められる。
あとは、各頂点のグループに対して、最大の操作回数を求めて合計すれば良い。
