https://csacademy.com/contest/round-10/summary/
$N$行$M$列のグリッド状に干し草の山が2つある。2つの山の座標が与えられるので、2つの山への距離が同じであるような座標の数を出力せよ。
すべての座標について、2つの山への距離が等しいかどうか調べればよい。
自力AC。愚直。
$N$匹のポケモンと、$M$個のアメがある。ポケモンを進化させるためには$X$個のアメが必要であり、まだ進化していないポケモンを$Y$個のアメと引き換えに売ることもできる。進化させることのできるポケモンの最大数を出力せよ。
進化させるポケモンの数を決めたとき、それが可能かどうかはO(1)で判定できるので、進化させるポケモンの数を二分探索すれば全体でO($\log N$)となる。
自力AC。典型的な問題。
サイズ$N$の正方行列が与えられる。この行列に対して以下の操作を好きな回数行うことができる。
操作後の行列の対角成分の和の最大値を出力せよ。
どのように操作を行っても、要素どうしの相対的な位置関係を変更することはできない。また、適切に操作を行えば任意の要素を行列の左上に移動させることができるので、すべての要素から右下に向かって$N$個の要素を足し合わせた数を計算し、その最大値を出力すればよい。
自力AC。解説によるとすべての対角線を調べるO($N^2$)の解法が想定だったようだが、制約の関係でO($N^3$)の愚直解が通る。
サイズ$N$の順列が与えられるので、奇数長の連続な部分列すべてについて中央値を計算し、各区間[$i, j$]について$i*j*median$の和を出力せよ。
偶数長の区間では中央値となりうる要素が2つ存在するが、ここでは便宜的に小さい方を中央値と定めることにする。すべての要素を含む区間[$1, N$]について、その中央値は$\lceil \frac N2\rceil$である。ここから1つずつ要素を削除していく操作を考える。要素を削除したとき、中央値は変わらないか、まだ削除されていない要素の中で現在の中央値よりも1つだけ大きい / 小さい要素へと変わる。
現在削除されていない要素のなかで、ある要素よりも1つ大きい/小さい要素を管理することは双方向連結リストを使えば可能である。これを利用して、ある要素を左端とした区間すべてについての中央値をO($N$)で計算することができる。たとえば左端のindexが$l$であるような区間であれば、区間[$l,N$]を表す双方向連結リストから右側の要素を順に削除し、中央値の移動をシミュレートすればよい。最大区間[$1, N$]を表す双方向連結リストは簡単に作れるので、そこから左端を順に削除していけば[$l, N$]についても簡単に作ることができる。これを行い、区間の長さが奇数である場合のみ$i*j*median$を足し合わせれば答えとなる。
解説AC。左端を固定した全探索は考えていたが、双方向連結リストは普段あまり使わないデータ構造なので選択肢として挙げることができなかった。知識自体はあったので思いつかなかったのが悔しい。
$N$個の整数が与えられる。この整数の集合が以下のような性質をもつために追加しなくてはならない整数の個数の最小値を出力せよ。
集合にいくつかの整数を加えてxor演算について閉じるためには、与えられた$N$個の整数同士をxor演算して作れる整数をすべて集合に加えることが少なくとも必要であることがわかる。ここで、64bit整数を64次元0/1ベクトルと考える。これらのベクトルの中で1次独立であるようなベクトルが最大で$r$個とれるとき、その$r$個のベクトルが張るベクトル空間は与えられた$N$個の整数をxor演算して作れる整数の集合と同じであり、ベクトル空間の性質から、$N$個の整数で作れる整数すべてを集合に加えれば十分であることがわかる。
以上から、最終的な集合の要素数は$2^r$となることがわかる。ここで、$r$は与えられた$N$個のベクトルを行ベクトルとして縦に並べた行列のrankに等しいから、これは掃き出し法で求めることができて、答えは$2^r-N$である。
自力AC。線形代数は全然身についていないと思っていたが思ったより覚えているのかもしれない。
以下のような方法によって作られる$N$頂点の木を考える。
できた木のコストを$\sum_{i=0}^{N-1} degree^2$とするとき、コストの期待値を求めよ。
$DP[i][j]=$サイズ$i$の木について、次数が$j$であるような頂点の数の期待値
で表せるDPを考える。ここで、初期状態は$DP[2][1]=2$であり、頂点が増えるたびに$DP[i][1]\text{+=}1$、$i$番目の頂点から伸びる辺は自分より番号の小さい$i-1$個の頂点にランダムに接続されることから、DPの遷移は $$DP[i][j]\text{+=}DP[i-1][j]+\frac{DP[i-1][j-1]}{i-1}-\frac{DP[i-1][j]}{i-1}$$ であり、答えは$\sum_{j=1}^{N} (DP[N][j]*j^2)$となる。
上記の遷移はO($N^2$)なので、$N\leq 10^6$で明らかに間に合わない。しかし、次数が大きいノードの数の期待値は十分に小さいので、$j$の大きい状態を無視してもよい。絶対誤差は$10^{-6}$まで許容されるので、$j\leq 50$程度まで計算しておけば十分である。(ちなみに$$DP[10^6][50]*50^2=0.00000000005694104450$$である)。メモリが足りないので、適当に節約すると通る。
解説AC。許容される絶対誤差以上にならない部分の計算をサボることで計算量を減らすタイプの問題はAtCoderではあまり見ないので、なるほどなと思った。
$N$頂点の根付き木が与えられ、根は頂点1である。この木の辺には重みが設定されていて、頂点は値をもっている。以下の$Q$個の操作を処理せよ。
$Q$個の操作を$\sqrt{Q}$個ずつに分割して実行することを考える(クエリ平方分割)。ここで、取り出した$\sqrt{Q}$個の操作はクエリと更新が混ざったものであるが、これらの操作の$v$として指定されている$\sqrt{Q}$個の頂点(+根)だけを使った木を新たに構築することができる。ここで、$v$どうしの間にあるpathは、そのpathに含まれる最小の辺と同じ重みをもつ1つの辺に置き換えてよい。この操作はO($N$)で行うことができて、以降この木を小さい木と呼ぶ。
取り出した$\sqrt{Q}$個の操作のなかから、クエリのみを先に処理することができる。これは簡単で、小さい木に対して愚直に更新を行い、クエリで指定された頂点の値を読み取れば良い。この操作は$O(\sqrt{Q}\times \sqrt{Q})=O(Q)$で可能である。
クエリを先に処理する段階では$v$として指定された頂点の値だけが分かればよいが、その他の頂点も含めた更新操作は当然行っておく必要がある。ここで、$\sqrt{Q}$個の操作の中に含まれる更新操作をまとめて高速に行うことを考える。
与えられた木から小さい木を作る過程で約$N-\sqrt{Q}$個の頂点が省略されているが、これらの頂点は$v$(小さい木に存在する頂点)のなかで直上のものに付属していると考える。さらに、各$v$について、付属している頂点を「(その頂点が属する)$v$からのpathに含まれる最小の辺の重み」で降順にソートしておく。ここで、各更新操作がどの$v$に影響を及ぼすかは小さい木を使ってDFSすれば$O(\sqrt{Q})$でわかるから、各$v$について、関係のある更新をリストアップして$y$の降順でソートしておく。各$v$について、各更新操作がどの付属頂点までに影響するかは尺取り法の要領で計算できて、imos法を使えば更新操作は全体で$O(N)$程度となる。
以上の操作を全体で$\sqrt{Q}$回行うから、時間計算量は(おおざっぱに)$O((N+Q)\sqrt{Q})$程度となり、間に合う。
解説AC。難しいが面白い問題。クエリ平方分割なので、Moのアルゴリズムと似た雰囲気を感じた。実際には小さい木の構築が重いようで、きちんと平方に分割すると間に合わなかったが、操作を$10\sqrt{Q}$個ずつに分割してバッチの数を減らすとうまくいった。