なんかネットの調子が悪くて問題のページに行くまで30秒近くかかった。今回はドキドキしたり体が熱くなったりしなかった。
C - 2D Plane 2N Points
最初に浮かぶイメージは斜めの線／だけど、ある点とペアになれる相手がいる範囲を真面目に図示すると直角Γになる。1次元の場合を考えてみる。○○●○●●みたいな図を描き、ソートして貪欲で行けそうだ。しかし2次元だとちょっとどうしようも。400点とはいえC問題でこれか。D問題も見て、0完が頭をよぎった。
よく覚えてないけど、フローに思い至りDから戻ってきた。自分の中のフローのイメージは「あちらを立てればこちらが立たぬ」であり、それがフローを選択肢とするための入り口となっている。まさにそういう状況だったため、フローを思いつくことができた。
ド典型フローなら400点だ。ただおそらくはちゃんとした解法が存在しているので後ろめたさはあった。まあフローで解けることを証明できていたらそれが正義だ。サンプル通ったらACも当然という思いだった。一発ACで人権を得てDへ。
このときは「なぜフローにすぐ気づかない」と思ったが、後から考えればこうしてフローに辿り着けたことがすごい。
D - Two Sequences
まず1問を解くビジョンが見えない中、Dをやることにした。xorの500点だし、Dのみ1完みたいなのを目指していく。つまり頑張れば解けると思っていたのだが、色々考えても全然糸口に辿り着かない。そうそう使うことはないと思っていた、a+b=(a^b)+((a&b)<<1) を必死に思い出した。使えるかどうかはわからない。使うかどうかに関係なく、考えるきっかけにはなる。
さて、Cは通したがDの思考時間と合わせて30分も使ってしまったのでDを通さないとパフォーマンスが不当に（不当ではない）低くなる。できればDのACが欲しいところ。
既に計算が完了しているとき、あるb[i]に1を足したらどうなるかを考えたが、繰り上がりがよくわからない。各kについてk bit目が立っているaが何個あるか数えておく方針だったが、数だけでは（情報が）足りない。まともに足し算すると繰り上がりが不規則にずっと続くので無理っぽい。最終的にxorがわかればいいから、例えばNが奇数なら表の1列のあるbit位置が全部反転したら答えのそのbitも反転する。しかし、あるb[i]のbitを変化させたとき、それより上のbit位置の変化の個数の偶奇がわからない。addとxorの違いがもろに出ていてつらい展開だ。
繰り上がりが厄介ということで、まず最下位bitのみを求める問題だと思ってみる。こういうところから糸口がつかめることもある。そんな簡単な問題がわかったってどうせダメだろうと思えば足どりも重くなるが、とにかくやってみる。これは、a,bの最下位bitについて、0の数と1の数がわかればいい。今までN*Nの表で考えていたが、2*2の表でよくなった。なんか掛け算すれば、N*Nの表の中に最下位bitの1が何個あるかわかり、その偶奇が答えだ。
じゃあ次のbitも求まらないか。繰り上がりの情報を入れるととりあえず4*4の表でいけそう。ひょっとしてk bit目はO(k^2)で行けるか！？と思ったけどO(2^k)でしょこれが現実。
桁毎に考える。答えの、あるbit位置だけを求める。繰り上がりが起こる条件は、そのbitより下が、例えば両方1なら繰り上がる。しかし、1111と0001とかでも繰り上がるので、O(1)bitだけ見ればいいというわけにもいかない。単に足せばいいか。ソートすればしゃくとり法みたいにして繰り上がりが何個あるかO(N)でわかる。
解法に辿り着けた。しかし、あれほど厄介だった繰り上がりの問題が解決しているという現実を受け入れられない。不安の中で複雑な実装を進めた。1文字変数名の限界を露呈した（これは地味に課題かも）。しゃくとり法みたいなのをすんなり書けたのがすごいと思った（苦手意識あり）。そのbit位置の0の数1の数、そのabの組み合わせそれぞれでそのbitへの繰り上がりがあったものの数。そういうのは求まったがそれを具体的にどう使って答えを出すかでもう一山。
最下位bitしか関係ないとわかってはいるが、チキンなので何個の1があるか数えるのにint64_tを使う。まあデバッグとかでなにかと必要になることもあるので。
N*Nの表の中で、そのbitが1であるもの、たとえばaが0でbが1で下位からの繰り上がりがないもの。まあ掛け算して足し引きすれば出るのであとはサンプルで適当に。なんか逆にしたら通ったので提出してみたらAC。要検討。
（追記）途中、最下位bitしか関係ないはずなのにint64_tをintにすると結果が変わるという現象があって、これは配列の範囲外アクセスとかだと思ったけど原因がわからないままACした。原因は、変数（配列）を初期化せずにインクリメントして数えてたからだった。提出したコードでは初期化の必要がない形になっていて大丈夫だった。範囲外アクセスだと思った？残念、未初期化でした！
逆にすると通るのは、繰り上がりが「起こらない」ケースを数えてたからだった（このバグを見つけるのはすごく大変だった）。あと、デバッグで2進法出力したかったけど、cout << bitset<32>(x) とすればよかった。
E - Both Sides Merger
20分しかなかったので軽く考えただけ。3 -1 -1 4 というサンプルを作り考える。トーナメントみたいになった。思ったより使える数の制限がきつい。全然わからないけど解ける可能性はありそうないつものE。
