252

1年以上かかって、ようやく、252問完答。
最後に残った問題は、Problem 198、Problem 241、Problem 252 でした。どれも手強かった。

• Problem 198：やっぱり最難問題。Stern–Brocot tree を使おうと思ったけど、速い実装が書けなかったり、微妙な勘違いがあったりして、拡張ユークリッド互除法で。フォーラムにもあったけど、例解が欲しい。
• Problem 241：探索だと思うのだけど、枝刈りの加減が難しい。2^5*3^3*5 みたいな解を漏らさないようにするのに苦労しました。
• Problem 252：どう解いたらよいか分からず、2^50の空間を枝刈りしながら全探索。速度の保証はなかったけど、点がそこそこ密なので、そんなに大きな答えにならないんじゃないかと踏んだ。答えは求まったけど、フォーラムには O(n^3) とか書いてあったりしたので、ちゃんと確認しないと。あと、例解を解いてからが大変だった。

来週末にはもう新しい問題が公開されるので、束の間の夏休みです。