長期AHCでの時間配分 - MON.T+α Programming Room

はじめに

　皆さん初めまして（お久しぶりです）。この記事では自身の長期AHCにおける時間配分について書き連ねています。なお、この内容が参考になるかといえばかなり怪しいので、その点についてはあらかじめ断っておきます。

　前記事というのはこちら。こちらのほうがまだ参考にできる可能性が高いです。

montplusa.hatenablog.com

長期AHCの流れ

以下は自分の場合の例であり、他の人にとって適切な流れはもちろん違うことに注意されたい。

（おそらく、ほかの方の参加期やツイートを見るに自分の時間配分はだいぶ「実装力<分析力」型っぽい）

もちろん、24時間AHCをやっているわけではないので、期間の表記はかなりゆるく見てほしい。

問題読み込み期（1日）

　AHC序盤の問題読み込みタイム。長期AHCは問題の内容を頭の中でかみ砕く必要があり、それなりに時間がかかる。ここで問題を勘違いしたまま考察に入るとかなり引きずるので少し慎重に。最後に、問題で基本となりそうな（とても）単純な解を確認テストとして提出する。たまにここで楽しくなって単純な解を改造して再提出したりするが、雰囲気がわかればいったん理性でこらえる。

解法検討期（1~4日）

　AHCの問題を無事理解したら、解法の検討に入る。長期AHCの問題はシンプルな定式化でそのまま良い解が得られるような問題ではないことがほとんどなので、問題の捉えなおしを何回も行う。とらえなおして解法を考えるたびに、解法の将来性などを考えて棄却する。解法に関する自分の感覚云々については気になる方は前記事へ。コンテストに出るたびにこのあたりの引き出しが増えることで安定してきてそう。

　コンテスト外での話として、このタイミングでコンテスト終盤に期限のあるタスクは済ませておくとよい（諸手続きや買い出し、料理の作り置きなど）。この期間は日常生活中にも頭に居座ることがあり厄介であるが、逆に日常のいろいろな場面で考えることができるとひらめきも多い気がする。

重実装逃避期（2~7日）

　コンテスト中で最もいらない時期（日数は現実逃避日込み）。解法を思いついてうまくいきそうなことまで確認できたのは良いとしても、プログラムを書き始めるときに非常に大きなエネルギーを要する。実装が重いとこの必要エネルギーも大きく、エネルギーが足りず撃沈した回もある。不思議なことに、完成した後に振り返ると「これくらいならもっと早く書いておけばよかった」となることが多い。この段階で完成させるつもりはなくて、ここでは解法の芯を作るようなイメージ。（今後の自分へ：ここでパラメータ調整してあそぶとかはやめてね）

バグ修正＆成長期（2~4日）

　一番楽しいとき。バグは楽しくないが、重実装逃避期にゆっくり気を付けながらやってもらうとあまりバグらなくなる（経験が増えて慣れてきた説もある）。ここからの改善パートは発案→実装がこれ以前に比べ圧倒的に短く何サイクルも行えるので、順調に点が伸びる。最初はバグ回避のためやらなかった高速化などを入れられると世界が変わることも。

限界期(1~3日)

　パラメータもある程度適切になって工夫点ももう見つからなくなってしまった状態。あるいは、いろいろ思いついたがいざ試してみるとどれも改善しなくて自分の解法がある種局所最適に陥っている状態。かなり苦しい。マラソンの最後なので大きな変更案を試せないというのも原因としてありそう。

　短期コンの場合これらの所要時間を短期コンの期間に合わせてスケールしてもあまりうまくいかない。実装速度によるが、短期コンはもっとも筋が良い解法を吟味していると時間が足りなくなりがちなので、ある程度自信が持てたら実装してしまったほうが良い気がする。最後の限界期も自分の実装速度が5倍くらいにでもならない限り訪れないと思う。

解法選択・改善のパターン

　流れとはちょっと違う話になるが、AHCへの解法選択・改善にはいくつかの型があるように思われる。これらにはそれぞれ得意とするところ、苦手とするところがあるので、自分の特性にあわせて組み合わせられるといいかも？

　以下もすべて自分の所感なので異論は認める。

山登り型

簡単な解法を試した後に、評価関数を変更したり新しい要素を加えたりして、平均的によくなっていれば採用するパターン。基本的なやつ。

メリット

・改善の労力が小さい・改善にかかる時間が短い

デメリット

・低いところで解法が頭打ちになりやすい

この型に向いている人

・AHCの経験がまだ少ない人

・早い段階から順位表に乗りたい人

以下の二つの型は上の山登り型より良いように思われる。この二つについてのメリット・デメリットは他方と比較して書いている。

複数実装型

複数の解法・改善案を考え、それらの簡単な実装を行い、結果からどれが良いかを見極めるパターン。

メリット

・要求される考察が少なめ

・「一見厳しそうだが実は良い解法」を発掘しやすい

デメリット

・コード記述量が多め

・バグから誤った直感を得る危険性がある

この型に向いている人

・実装速度に自信のある人

・実装の精度に自信のある人

事前組み立て型

複数の解法・改善案を考え、それらの良さを見積もることで実装する前から解法・改善の方向性を決めるパターン。

メリット

・コード記述量が少なめ

・バグから誤った直感を得る危険性が低い

デメリット

・要求される考察が多め

・「一見厳しそうだが実は良い解法」を発掘しにくい

この型に向いている人

・問題の考察をするのが好きな人

・自分の考察の正確さに自信がある人

自分の場合は、途中までは事前組み立て型で終盤の限界期は山登り型だったりします。

過去のAHCでの配分

ここから下はほぼほぼ自身の振り返りです。

過去のコンテストの提出記録・githubの履歴から自身の時間配分と結果の振り返りを行う。

AHC014

これは長期コンの中でも長いタイプのコンテスト。調べてみた結果

・問題読み込み期(4日)←このタイミングで現実逃避してた

・解法検討期&重実装逃避期(並行で2日)

・バグ修正＆成長期(1日)

・限界期(7日)

コンテスト終了後までバグが残っていたりずっと限界を感じていたりと散々である。解法の吟味の前に実装を始めてしまい、その後パラメータチューニングまで軽く済ませてしまっために別解法へ行けなかったようだ。このときはどちらかというと山登り型だったかも？

AHC016

調べてみた結果

・問題読み込み期(1日)

・解法検討期(3日)

・重実装逃避期(0日)

・バグ修正＆成長期(3日)

・限界期(2日)

といった具合。なんか重実装自体を避ける結論になってた。このころは精力的に参加期を書いて振り返っていたのでAHC014の反省を生かして軽実装の当たり方針を3日検討してます。最初の読み込み期では、何回かサンプルプログラムを改変して提出していて、後のいい考察につなげられていそう。このときもどちらかというと山登り型だったかも？

最終的な順位は前より上がっているわけではないものの、この問題に関しては知識不足だったことを考えると良い流れ。

AHC018

調べてみた結果

・問題読み込み期(1日)

・解法検討期(1日)

・重実装逃避期(3日)

・バグ修正＆成長期(3日)

・限界期(1日)

といった具合。ちょっと解法検討が短そう。たしか「マップが広すぎるので縮小して扱おう！」みたいな発想だったと思うんですが、たぶん妥当性のことあんまり考えてないです。実装してみたら当たっていたという感じのコンテストで、ちょっと危険な思考だった気も。基本の実装が終わってから「掘る」というアクションの強さについて考察を始めていて、これが検討期にできていればもう少し安心して渡れた橋かもしれない。

結果は当時自己最高パフォで、うれしかった記憶があります。

AHC023

調べてみた結果

・問題読み込み期(1日)

・解法検討期(2日)

・重実装逃避期(3日)

・バグ修正＆成長期(--)

・限界期(--)

といった具合。結果は前よりも良くなかった。解法検討期に良い解法が思いつかなかったことも大きいが、解法検討・重実装逃避期が長引いた結果妥協案の小手先改善が採用されてしまった点が決定的だったかもしれない。重実装逃避はほどほどに、早めに取り掛かろうね・・・。

AHC025

調べてみた結果

・問題読み込み期(1日)

・解法検討期(1日)

・重実装逃避期(1日)

・バグ修正＆成長期(5日)

・限界期(1日)

といった具合。解法検討期に熟考して「これだ！」と思う解法がすぐ思いついたのと、その裏付けが考えられたので安心して書くことができた。実装が小分けにできたので、段階的に実装していくことで重実装逃避期を回避できたのもよかった。今後、実装をより段階的にできないかは考えてみてもいいのかも？

AHC027

調べてみた結果

・問題読み込み期(1日)

・解法検討期(3日)

・重実装逃避期(--日)

・バグ修正＆成長期(1日)

・限界期(4日)

といった具合。焼きなまし想定の回に貪欲で取り組んだ新鮮な回。焼きなましを十分高速・効果的に行う方法を模索していて検討期が少し長め。最終的に難しいという結論に至り貪欲を使うという結果に。理想な形についての考察であったり、貪欲の過去改変であったりと貪欲法でも戦えるようにするための構想を検討期に考えておいたことにより結果は悪くなかった。コンテスト後に明らかになったことではあるが、実際焼きなましの難度はかなり高く、焼きなましで成功していた参加者はかなり限られていた。

AHC029

中期（？）コンなので日数で書くほど期間はなかった。実装は確か初日から始めているので、あえて書くなら

・問題読み込み期・解法検討期(1日)

・重実装逃避期(2日)

・バグ修正＆成長期(2日)

・限界期(--日)

といった具合。期間の短さの割に成功できたのは、問題を見た段階でモンテカルロ法でほぼ決まりだと感じて貪欲を利用したプレイアウトの方針が一瞬で決まったことが大きいと思う。モンテカルロ法は実装経験が少なく、コンテスト終了まで改善を続けることができた。今後実装経験を増やしていくとこのあたりの改善スピードが速くなって期間内に取り組める内容が増えるのかな・・・？

以下はまだ書けてないです