[AtCoder 参加感想] 2020/06/28:Introduction to Heuristics Contest

	A	B	C
問題文	■	■	■
自分の提出	■	■	■
結果	AC	AC	AC

全完です（ドヤッ）

あ、この形式、Heuristic Contest だとイマイチですよね（笑）

74576292 点、586 位でした。

全体感想

全体感想

アルゴリズムで競うところまで行けなかったのが残念です。でも、面白いしスキルアップにもなると思うので、今後もがんばります。

いつも以上に個人的な覚え書きなので、解説は期待しないでください。

0点 AC

まずは、入出力形式などの確認も兼ねて、あんまり頑張らない適当な解法を提出しようと思ったのですが、AC かつ 0 点のスコアが出てしばらく苦しみました。「AC とは出ているけど、入力によっては変な値が出るのかな？」「RE や TLE も AC と表示されるのかな？」などという疑念が生まれて、これの対処にかなりの時間をつかってしまいました。

提出制限があるので、「いろいろ提出してみて観察する」のは待機時間が多い
はやめに、入力生成器、スコア計算器、などで手元テストするべきだった。提出制限があるので、提出せずに色々確認できる恩恵は無視できない。

とはいえ、0点 AC は出題側としても望んでいた状態ではなかったようなので、次回以降は「0点ACに対する疑念に時間を溶かす」心配は不要かもしれません。

max(0, score + 下駄)にしたらACだけど0点が頻発してしまい、参加者を混乱させたようで申し訳ない。max(1, score + 下駄)にするべきだった
— Yoichi Iwata (@wata_orz) June 28, 2020

入門者向けのガイド付き小問(B, C)

B, C のガイドが役に立ちました。解説や次回以降も楽しみにしています。
— maspy (@maspy_stars) June 28, 2020

役に立ちました。こういうのを実装するのは、毎回のコンテストの基本ルーチンに組み込もうねという話ですよね。参考になります。

また、「B → C → Aの第一解法」順で取り組んだのですが、「B → Aの第一解法 → C」で取り組む手もあるのかな？と思いました。また、C が、「ランダム 1 点更新」「2 点スワップ」の両方に対応できるところもすこし感心しました。シンプルな操作に対する計算になっていると、後から思いつくかもしれないもの操作広く対応できるということですね。

最適解の構造の見積もり

制約内の乱数なので、ある程度のゲーム性は計算できそうです。はじめは、ランダムに $t_1, \ldots, t_D$ を出力するとどうなるかを考えました（実装はしていないです）。

はじめ、次のように考えていました。「$S_{d,i}$ からは日ごとにおおよそ $10000$ 点ずつ獲得する」「$C[i]$ は、だいたい $26$ 日おきなので、1 コンテスト $26$ 日あたり $26 \times C[i]$ 程度の減点。全コンテスト 1 日あたりだと平均 $1300$ 点程度」「スケールを比べると、$S_{d,i}$ の影響の方が $8$ 倍くらい強い」

このことから、はじめは最も単純な貪欲戦略として、各日に「$S_{d,i}$ が最強の $i$ を出力する」を考えました。→ 0 点。

この時点でひどい考察力でした。$26$ 日ごとに開催する場合、 $C[i]$ の寄与は $26$ 日間で $1+2+\cdots+26$ くらいの減点です。それが $26$ コンテストあるので、1日あたり $\frac{26^2}{2}$ 倍程度での減点が乗ります。$26\times C[i]$ と考察していたところを $338\times C[i]$ とすると、$C[i]$ の方が $S_{d,i}$ よりも大きなスケールで解に関係してきそうだと分かりました。これに気づいて、ようやく正の得点になりました。

「$C[i]$ が優先ならば、おおよそ $20 ～ 30$ 日おきに全部並ぶような状態を維持して探索していくことになりそう」と思い。これは、ある程度良い方向の思考ではあったようです。

ところで、時系列順に見て、その瞬間での得点を最大化する貪欲法が第一歩としては良かったという考え方も。

まぁ、ロジックが本当にほとんど全く不要な解でとりあえず正の得点にしたかったという気持ちもあり、第一提出でこの貪欲は考えなかったです…。

実装の反省点

この辺は、普段のコンテストでは大きく可視化されないだけで、よくやらかしているように思う。

0-based index か、1-based index かで迷った。
日付を $0$ から始めて、$d$ 日目に開催した場合に値 $d+1$ を配列に入れるみたいな実装にしてしまう。2時間も1問に向き合うと、やはり何度か思考のロスになっていた。
開催なしのものを $-1$ で埋める or 日付を $1$ で始めるのが良かった。
S[d,i] と last[i,d] という順番で添字を使っていた。何度か確認しに戻る羽目に。どちらでも良いから統一しておこうね…。

必要なスキル

貪欲だ、山登りだ、焼きなましだ、…というアルゴリズム力もあるのですが、

すこし長く、要素数も多い問題文を正確に読み解き、頭を素早くなじませる
ひとつひとつのロジックを、素早く確実に実装する。
提出に頼らずに機能の正しさを素早くテストする。

といった能力は通常コンテスト以上に問われるように感じました。このへん、私が苦手としているところです。次回はアルゴリズム手法よりも、この辺を意識して参加したいと思います。

解きなおし・過去問の取り組み

どうしようかなぁ…。「本番 n 位スコア以上で埋める」とかを目指したいけど。$n=100$ とかはどのくらい大変なのだろう。もう何回かは無対策で参加しつつ、様子見。