ABC117を反省する（主にD問題） - いろはすの競プロ反省会

結論から言えば、自分の中ではかなり力が出せたコンテストだったと思う。少し手間取ったところもあったがA~Cまではほぼ順調にACし、残り５０分強を残してD問題に進むことが出来た。時間としてはかなりあったが、やはり今の自分の実力では最後のD問題を通すには至らず、３完に終わった。反省すべき点もあるが、今まで苦戦することも多かったC問題も落ち着いて考察して一発ACすることができたし、タイムも自分の中ではかなり良い方だった。 D問題も、ACには時間的に遠く及ばなかったがキーとなる部分の考察は出来ていたので、自分としては満足な出来であった。

まあ感想はこの辺にして、本題となるD問題の反省に入ろうと思う。コンテスト終了後、自分こといろはすは書きかけだったD問題のコードを仕上げ、提出した。するとなんと一発ACで、今日はなんて調子の良い日なんだと小躍りした。しかし、これでめでたしではなかった。

実は、そのとき自分が通した解法は嘘解法だったのである。本来は桁DPで解かねばならないところを、自分は貪欲で解いていたのだ。この「貪欲嘘解法」は、Twitter上でかなり話題に登ったので知っている人（または自分もやったという人）は多いであろう。自分はこの騒ぎをPCの前で眺めながら、「へえ〜、Dは嘘解法があったのか」などと呑気なことを思っていた。そして「本来は桁DPで解かねばならない」という文章を見てさえも、「へえ、これ（自分の解法）が桁DPかあ」とか思っていた。本当にどこまで天然なんだいろはす。[ちなみに、それからしばらくして「あれ、よく考えたらこの（僕の）解法貪欲じゃね！？」と気づいた]

まあそんな訳で、Dについては今日一日がかりで正解法で通したわけだが、そこに至るまでの自分の思考の道筋を初めから記録していこうと思う。

問題文はこちら

コンテスト中〜コンテスト後の考察（貪欲嘘解法）

とりあえず、最初のサンプルで実際に数値を代入してf(1), f(2), f(3),...と計算してみた。そこから法則性のようなものを掴もうとしたのだが、これ自体にはそれほど意味はなかった。 XORの計算に慣れたところで次に、数列の各項を２進数表記して縦に並べてみた。これがかなり効果的だった。

$1 = 0 0 1$

$3 = 0 1 1$

$6 = 1 1 0$

こうすると、f(X)を最大化する方法がひと目で分かるからである。 XORの性質から、なるべく多くの項を寄与させるためには、２進数表記したときのXの対応する桁において

0が多い→1

1が多い→0

とすればよいことが分かる。

問題は「X≦K」という制約だが、これは左の桁から順番に見ていって、XがKを超えない限りにおいて上の指針に従うという風にすればよいであろう（とそのときのいろはすは考えた）。 これが「貪欲」の部分であり、間違っている部分である。

このような考え方に従って提出したコードが以下のコードである。

https://atcoder.jp/contests/abc117/submissions/4168980

なお、各桁において立っているビットの個数を数えるのにlower_bound()を使うというちょっとテクニカルなことをしているが、これは当時の僕がテンパっていて「ループを回して数えたのでは間に合わない！」（※間に合います）などと思ったせいである。まあかっこいいからいいか。

あと、これを通す前に $2^i$ を1<<iとか書いてハマってた。 iが大きいときは1LL<<iとかしなければならないことを恥ずかしながら初めて知った。まあ、今後は安全のため自分で実装したpow()関数を使うことにしよう。

さて、上のリンクだが、見れば分かるとおり実際これで全てのテストケースが通っている。しかし、実際間違った答えを返す簡単な例を作ることができる。例えば、 $n=3, k=2, A_1=2, A_2=A_3=0$ の場合である。このケースに対し、上のコードが返す答えは4だが、実際の答えは5である。これは一個ずつ手で計算するか、愚直解を実装するかすればすぐに分かるだろう。