解けたらいいな
ARC 092: D – Two Sequences (500) トケタ！
始めてABCに出た時Dで出て解けなかった、思い出の問題。当時はうまく計算できるのかなと数オリ脳が消えず沈没した模様。もちろんその気持ちも大事なんだけど、今回は普通に計算できます。
XORは毎にbitが何個立つかの偶奇が分かればよいので、「桁ごとに考察しよう」というのが初手。典型的な考え方だけど、定義に戻れば当たり前なので典型以前の問題か。
k桁目(0-indexed)に1が立つのは、もともと1があるケースと、繰り上がるケース。両方あるケースは別で足しても偶奇は変わらないのでそうする (例：k=2で6+3=11で立たないけど、これはもともとある6の1個と、繰り上がりの1個を足したと考えられる)。
もともと1があるケースとしては、a,bでそれぞれca個、cb個とすると、N^2個の中にca*(N-ca)+cb*(N-ca)個できる。mod2だとN*(ca+cb)個。これを献上する。
繰り上がるケースは、a,bのk桁目以上を消せば、片方の列をソートすることでO(NlogN)でカウントできる。kが大きい方から、ちょっとずつ消してカウントすればよい。
以上でO(N * logN * log(max(a,b)))で計算できた。これでギリ間に合います。
解答では繰り上がりを考慮せず、べたっと二分探索している様子。たしかにそれで十分問題ないな。
CODE FESTIVAL 2016 予選 B: C – Gr-idian MST (500) トケタ！
グリッド型のグラフ上で最小全域木を求める問題。コスト最小の辺を入れないと明確に損なので、全部入れたい。すると、頂点を併合することで小さい問題になる。よって順に最小の辺を追加していくとよい。コストをソートしてシミュレーションすることで、ソート分のO(N log N)で解ける。
考察も実装もうまくいった。こういうの好き。
SoundHound Programming Contest 2018 Masters Tournament 本戦: B – Neutralize(400) ようやくトケタ
組合せ論の問題のように、いいアルゴリズムを求めようとしてダメだったけど、冷静にDPをすれば解けた。解説は確かにあってるけどかなり不親切だと思う...
1からi番目までの最大を出すのに単純にやるだけではだめで、捨てた後の次の項は自由に取れるので (K連続以上なら問題ない)、そういう制約でもう一種類dpをする。そちらの更新にはもとのルールのdpも必須なので、同時に更新していくことになる。漸化式を2本立てる感じ。2本目がわかりづらいが、「前の結果を利用する」のは素直なので、割と自然に思いつくべきだった。分かれば遷移は簡単なので実装は楽。
とにかくDPしよう！ 全探索の次にDPを考えた方がいいと思いました。
