ラテ、AHCに初参戦してみたらしいです。 - 茶処・まっちゃら亭の一休みばしょ

お久しぶりです、まっちゃラテです。
なんと私、プログラミング歴3,4年で、初のAHC(AtCoder Heuristic Contest)に参加してみました。
その備忘録として、なんか何をしたかどうかを、ここに記しておきます。初心者なので参考にできることもあれば参考にもならんほど当たり前なことを言ってるかもしれません。なのでそんな真剣に見ないで、ジェットコースターに乗ってる最中に見ておく程度でお願いします。

では、早速書きます。
お楽しみください。

※ストレスやばすぎるのでなんかよくわからん部分もあると思われますが、溶岩のような温かい目で届けてください

1日目(参加初日)

何もわからん。

とりあえずBFSで最短距離を計算。でも水路の境界線のやり方で詰み。得点は取れず。

バイト、大変でした。英語でオーダー初めてなんだもの！！！！

2日目

やっと境界線探索のバグを発見、(といってもif文条件式をがちゃがちゃしただけ)修正した。やっと動いた...
そして初めて SampleCode の存在を知る。見てみた。なんだこのコード！！！わからん！！！

とりあえず見様見真似で、自分が実装したGrid探索以外のコードを書いてみた。書いてみると、そんな難しくないのね...
で、SampleCodeを出してみた。 $143000$ pt。これが...みんな最初にやるやつなのね。じゃあ自分社会性なかったわごめんなさい。

※以下 $n$ は、 $k$ がindex同不順で $k_1,k_2,...,k_n$ の $n$ 個のみを植える作物として採用させる個数とします。

$n\le\min(K,10)$ の $10$ をいじくってみると、 $n\le K$ のままだと TLE、 $n\le\min(K,40)$ でぎり $200$ msに収まるくらい。へぇ～...。面白いじゃん。
自分の実装したコード+templateコードの局所的参考で $\min(K,40)$ に変えて提出。結果は $572000$ pt。今回 $100$ 万は行きたいな...頑張ろう。

計算時間がかなり長いことを知った。線形時間×線形時間...なるほど $K$ じゃ間に合わないわけだ。知らんけど。
そこで思いついた最初の探索高速化の方針、

それは迷路を $\text{UnionFind}$ で管理するということ。

巷ではアッカーマンの逆関数がかなり定数としてみなせることができるといわれている。

これで管理すれば、かなり高速化できるので、 $n\le\min(K,200)$ くらいは行けそう $O(nHWT)=8.0\times10^7$ まで、十分間に合いそうではある。
他にも考えた方針はあって、余った土地は活用したいのでDFSの帰りがけ順で $S_k$ が大きい順に埋めていくといったことである。これも...むずそう。

ただ is_valid_move 関数を使えば楽に判定できそう。
3日目も頑張る。

3日目

AHCのことしか頭になかった(正直)。ということで実装開始。
昨日はtemplateの存在を初めて知ったので、そこから派生させようと考えた。

1日目で気づいた方針を活用することに決めた。
それは、BFSで計算した各マスと $(i_0,0)$ からの最短距離から、 $D_k$ が遅い順に、かつ最短距離がより長いマスを採用することを考えた。

そうして実装し、templateも参考にしながら変更を加え、提出。得点は $743050$ pt。前回より $20$ 万も上がってるので、まぁよし！

templateでは、 $n\le\min(K,10)$ 個の作物を植えているが、 $n\le\min(K,30)$ でも時間に間に合ったことが分かった。なのでこの性質を使ってみる。

templateは愚直DFS、かつ毎度 $O(HW)$ まで回しているので、かなり遅いことが分かった。
そこでさっきも言ったBFSの計算テーブルを利用して、最短距離の $MAX$ 値 $mx$ から $mx-1,mx-2,...,0$ としてどんどん計算してみた。このときはtemplateと同じ感じで、空いているマスがあったらそこを採用する。この方法で提出してみると、得点は $2564050$ pt。初期に比べてみたらかなり上がってきた。超うれしい。

ビジュアライザを見てみると、作物 $k=1,2,...K$ として1つずつ丁寧にマスを探索していたので、余分なマスがかなり多かった。

なので $k=1,2,...,K$ ではなく、 $k$ ごと回しながら空いているマスを採用する、といった方法で実装してみた。提出すると、得点は $6991225$ pt。さっきの1ずつ回すのに比べて $400$ 万pt上昇。かなりよくなったし、X (a.k.a Twitter) で見る天才な方々の過去のビジュアライザを見てみると、なんだか似ているような気がして、もっと嬉しくなった。

やっと "H" の楽しさを噛み始めた。
ただまだまだ改良の余地しかないことは自分でもわかっているので、もっと頑張ろうと思う。

4日目

やっぱり朝からAHCだよね！！になってしまった完全に脳内が(完全なる倒置法)。
3日目に気になっていたスコア上昇法、 $X_k=D_k-S_k+1$ が大きいほど加算されるスコアも増えることに気づいていたので、 $D_k-S_k$ の大きい順にソートできないかと思っていた。
でもバグが何なのかわからなくてあきらめかけた。なので、まずはコード全体のリファクタリングを行った。

すると、変数 d が重複していることに気づいた。for文のカウンタ変数と同じ名前だったのだ。

というのも、3日目に $\text{TIME_LIMIT}$ まで許す限り解を見つけ出すといった方法を用いていた。そのとき計測時間も d だったのだ。
d がかなり変な動きをするので、不安だった。しかしなぜか $n\le\min(K,475)$ が間に合ったので、そのまま変数だけ変えてあとは放っておいた。

d を time にして、もう一度実行。
ん、ちょっと待って。スコア減ってない？

不安の気持ちいっぱいで提出してみた。得点は... $6981800$ pt。ええ、減りました。しかも $9000$ ptだけ。この誤差、命取りです。

そしてもう一度、あの $D_k-K_k$ ソートを考えてみた。
templateを見直したり、デバッグしたり。すると、思っていた通りのバグを発見した。
(3日目ももちろん思ったけど、何もわからなかった)

indexが間違っていました。大変申し訳ございませんでした。
そしてそのバグを直し、いざソート。うまくいきました。
そしてビジュアライザを片手に実行。 $\text{seed}=0$ ケースで [text:20] 万を超えました。
これは...いける？

提出してみた。得点は、なんと $13955525$ pt！！

生まれて初めての H で $1000$ 万の大台を達成！！！！！
思わずガッツポーズをかましました。ああ、神様ぁ...
AHC、ガチ楽しい。

(ちなみになんかソートの単調性があり $S_k$ がほどよく大きい、といった性質から、ソート済の配列で10番からの要素を探索してみましたが $40000$ pt減少しましたありがとうございましたおはようございます)

5日目

もう何もわからない！！撤退したい！！！！でもしない！！！楽しいから！！！

ソートの評価関数を $D_k-S_k$ が等しいときは $S_k$ が速い方にする、にしてみて提出。得点は $13944450$ pt。減りました。ありがとうございました。

とりあえず、plant・harvestの採用リストを無駄に再計算していたので、それを1回で判別できるようにした。でもそんな変わらなかった。。。
なのでやけくそで $\text{TIME_LIMIT}$ の上限を上げて提出。結果は $14304175$ pt。これが俗にいう、微増か.....

6日目

バイト行く前に方針を考えてみた。
もしかして、各月の盤面は $t=S,D$ にのみに依存する...？全部T=0,1,2,...調べなくていい？

ということで実装してみた。

バグりまくった。

バグりました。

さようならみなさん。私は雨の一部になります。

悔し紛れにplanだけで表してみて、提出。少しスコア伸びた。得点は $14945700$ pt。 $500000$ 伸びただけでもだいぶましでしょ！！！

7日目

うーんと、まぁ...バイトの時間もあるし？某精進鯖からBANされるのを回避するための緑問解く時間もあるし？なんなら明日のゴルフの準備もあるし？？

...いや無理！！！時間がない！！！！皆さん、対戦ありがとうございました。私は雲の上で寝ます。

後悔と反省

初めてAHCに参加してみましたが、めっちゃおもろい！！！！
こうやって現実とリンクできるような問題を解くと、本当にいいな～と思いました。
というかこういう社会に生かせるようなコンテスト(ABCもそうですがAHCもかなり生かせる)に参加して、自分で解を編み出すの、めちゃくちゃ楽しい...

でもそのためにはやっぱりABCをやりまくる必要があるんだなと思いました。そりゃそうだよね～...
他の天才たちの解法を見てみると、私の親友(?)のUnionFindくんでなんかやってる～感動友達になってくれてありがとうと思いました(めちゃ上から目線ですすみませｎ)
ただ、やっぱり $S_k$ と $D_k$ のみに依存する、って方針実装し切れたらよかったな～と思いました。
まあ時間がなかったので...仕方なかったです。方針が完全にあってるのかどうかも確信がなかったので、結局実装しなくてよかったのかな～とも思いました。