AtCoder Heuristic Contestに初参加したよ(AHC 033)
先日初めてAtCoder Heuristic Contestに参加しました。ちなみに４月から始めたAlgorithmのレートは灰で、ちょくちょく茶パフォが出るかなってところです。だいたいケアレスミスでペナルティを喰らってます。D問題はたとえ解けても時間内にはできません。
今回緑パフォが出て喜びの舞を踊っています。みてこれ。
言語はJuliaです。逐次実行なのにめちゃくちゃ早いJuliaさんです。
問題とざっくりした解法
AHC 033に参加しました。問題はリンク先をご覧ください。
搬入口に一つずつ積まれる番号付きのコンテナを、一行目の搬出口に0,1,2,3,4の順番で、〜〜〜五行目の搬出口に20,21,22,23,24の順番で置いていきます。
自分のゴールを決める
最初に読んでみて感じたのは、求められていることを全て満たすようなクレーンの動かし方と自分ができるレベルを満たすような動かし方がずいぶん違いそうだということです。締め切り２日前に参加した時点で自分は小クレーンまで動かすことはできなそうだったので、最初から小クレーンを爆破して、大クレーンを動かすことだけを考えました(搬入口からフィールド全体にコンテナを引っ張り出して散らかす作業くらいには小クレーンを動員しても良かったかもしれません)。大クレーンだけを動かすときと両方動かすときでは大クレーンの動きがそこそこ違い、大部分を書き換えなければいけないという直感(∈Heuristic)があったので、これを早いうちに決断する必要がありました(実際のところはわかりません)。山登り法を意識して言い換えるなら、AHCという峰(山の連なりであり、山頂は局所解に相当する)があったとして、
登ろうとしている山は自分に合っているレベルなのか
もっと高い隣の山頂に行くとき、どれくらい下山しなければいけないか
を、登る前に上を向いて知っておくべきです。
大クレーンを使って正しい場所、順番で運ぶ
大クレーンはコンテナを持ちながらでも自由に移動できます。コンテナを置こうとしている場所に既にコンテナが存在していないかどうかだけ気をつければよいです。
手順はこうです。
小クレーンを爆破する
搬出する順番が来たコンテナがフィールド上にあれば運ぶ
なければ、順番が来たコンテナが溜まっているいる搬入口からコンテナを出して空いているところに置く
初めは無秩序にコンテナを取り出してフィールドに散らかしていたのですが、これだと0,5,10,15,20番のコンテナが全て搬入口の一番奥に配置されているとき、これらを搬出する前にフィールドが他のコンテナでいっぱいになってしまいます。なので順番が来たコンテナが積まれている搬入口から優先してコンテナを取り出します。
まずACだけを目指してから、一個ずつ実装していく(登山)
まず得点のことは考えないで、ACすることだけを目標に書きます。つまり、小クレーンを爆破して、搬入口にあるコンテナを大クレーンで上の搬出口から順番に搬出していきます。
それができたら、正しい場所から搬出する→正しい順番で搬出する という感じでステップアップしていきます。
さっきの話にかかってきますが、この方法でやると、「できるだけ早く搬出する」という目標はこの次に存在しません。早く搬出するには小クレーンを動かす必要があるので、これを目指す場合は初めのACを目指す時点から小クレーンを動かしてみたほうがいいです。
反省
余裕を持って参加する
焦って書いていると、同じことをしている部分を一つの関数にまとめることの優先順位が下がります。これは可読性を大きく損ねます。そのせいで今回のコードは最終的に420行くらいになってしまいました。やることはそこまで多くないのに……
コメントや簡単なフローチャートを書く
メモもコメントも書かないでいきなりコードを書き始めました。ABCのC問題まではだいたいこれでいけるのでそれが癖になっていました。420行分の処理を同時に覚えていられません。どこに何が書かれているかを一目でわかるようにすると、うまく動かなかったときに原因の仮説を立てやすくなります。そうしなかったせいで行単位での原因の把握ができず、運ぶべきコンテナを決定する処理を丸ごと書き直すはめになりました。
処理をひとかたまり書き終えたらできるだけ関数にする(モジュール化)
運ぶべきコンテナを検索するコードを90行くらい書きました。一応動くようになったということは、僕は別の処理を書き始めるでしょう。そのときこれらの90行のコードが持つべき情報は「運ぶべきコンテナを検索する」だけです。「フィールドを1マスずつ見てェ… コンテナの大小を比較してェ… 運ぶコンテナがなかったら搬入口のコンテナをォ…」という情報はしばらく見る必要がありません、というか見てはいけません。90行を、`find_container_to_carry()`という1行にします。
完走した(目標の山を登頂した)感想
楽しかった！！！！
マジで寝食を忘れて書いてました。最終日なんか大学の授業中も書いててほとんど授業の内容が頭に入ってません。初日からやっていればここまで根詰めてやらなくてもいいんですよね……
何より緑パフォが出たのが嬉しかったです。Algorithmでは出したことないです。
ただし、今回偶然自分がやりやすい問題が出ただけである可能性が大いにあります。これ以外のAHCの問題に取り組んだことがないので、今回の勝因を完全に把握できていないと思います。
今月も走ります。