AtCoder Beginner Contest 197 反省

あたたまれてよかった。UTPCを５時間もやって脳みそ破滅していたかと思いきや、良いウォーミングアップになっていたようだ。

結果を鑑みて

2100(1) 80:38

基本的に考察はすんなりと進む問題セットだった。得意回ということになるわけだが、得意回なら60分以内に全完したかったところ。pythonの定数倍関連での知見が増えたのでよしとする。

A - Rotate

１文字目と末尾を交換する問題だと思っていて少し時間かかった。rotateって書いてあるだろうが。

B - Visibility

こういうグリッド上の上下左右探索がABCで出るのは3回目くらい？B問題としては難しいと思った。読んですぐに解法はわかったが、実装には少し手間取った。5分かけてfor文を4個書いてAC。

C - ORXOR

題意が少し取りづらかったけれど（読解力さん？）制約をみるとbit全探索で、解法はすぐに生えた。仕切りの位置の組み合わせを全探索してAC。5分ほどで終わった。

この時点で順位表を見て、そこまで悪くはなかったので特に焦ることはなかった。

D - Opposite

第一感として、正多角形ならば外心を使うことができることに気付いた。最初は外接円半径を出そうとしたが、よく考えると外心を中心としてp0を回転させるだけなのでwikipediaの回転行列公式をググってなんとかACした。そこまで悩んだ印象はなかったが7分かかった。

ABCで300点以上のO(1)数学が出たのは久しぶりな気がする。これで誤差ゲーだったらブチ切れてAtCoder引退をしていたかもしれない。

この時点では順位もいい感じだったのでいい気分で先に進むことができた。

E - Traveler

パッと見た感じ、色ごとにまとめて色の昇順に見るのが良さそうで、右端行ってから左端行くのと左端行ってから右端行くのでは移動距離が変わる場合があって、これが貪慾性をもたらすように思えたが、よく考えるとこれが次の色に取り掛かる時にも影響を及ぼしているので単純な貪慾ではなさそうだった。無限場合分けかなと思ったが、その色の右端で終わるか左端で終わるのが流石に移動距離的には正しそうなのでこれを持ってdpすることにした。ほぼお気持ち証明だったが、なんと正しかった。

13分ほどでACでき、順位も上々だった。精神的には安定していて、橙パフォあるかも〜とか思っていた。

F - Construct a Palindrome

第一感として、回文なら両側から同時に歩を進めれば良いだろうというアイデアになった。最初、N≦10^5だと思っていたので解法は特に思いつかなかったが、制約のN≦1000を見ると直積グラフを作ってDFSするだけの計算量的余裕があることに気付いた。すぐさまDFSを組み、サンプルをチェックすると正しい答えが得られた。

ここで提出する前に一呼吸おいてN=1000の一直線なグラフについてテストするとなんといつまで経っても処理が終わらず、PyPyでさえN=200で5secかかるなどえらいことになっていた。ここから20分ほどかけて定数倍高速化をして、PyPyでN=200で3secまで縮めたがあまりにも遅くてびっくりした。

最後の希望としてDFSにつかっていたスタックをlistからqueue.Queueに変えた。これをするとなんとN=1000でも0.6secほどのスピードで進んだ。驚きすぎてうっかりテスト用の入力を残したまま提出して1WA、その後ACできた。

listよりqueueモジュールの方が速いという話は聞いていたが、これで橙パフォがおしゃかになったと思うと全完後は辛い気分になった。

ところで、コンテスト終了後に外を走っていた時にふと気付いたことだが、queue.Queueは"FIFOキュー"である。つまるところ、気付かないうちにDFSではなくBFSになっていたことになる。この問題の本質は直積グラフの最短経路問題なので、DFSは不適でBFSを使うべきシーンであった。

なんと、考察の大詰めでしくじっていておまけに運でACしていたということである。この事実に気付いた時、あまりの不甲斐なさに私は膝から崩れ落ちて目の前が真っ暗になってしまった。

総括

queueモジュールについて理解を深める必要があること、直積グラフは想像しづらいので最短経路問題であることにすら気付けなかったことなど色々と課題が見つかった。

コンテストのムーブとしてはA~Eまでは大変良かったと思う。Fは知らない！