ながめも

競技プログラミングについて

トップ > AHC > AHC011に参加しました

AHC011に参加しました

AHC マラソン

173位でした。

gitのコミットを見て時系列で振り返っていきます。

5/28（1日目）

問題文を読む。グリッドで操作も簡単な好みな問題だと感じ、力を入れて参加することを決意。

コミットを読むに、タイルクラスを追加したり、ジャッジを実装してた。 深夜まで実装してます、この人。

5/29（2日目）

ツイートにも履歴がないため何もしてないですね。昼まで寝てた気がします。移動が多かったかな？

5/30（3日目）

だそうです。

5/31（4日目）

かわいそう。でも腰が痛いのに取り組んでますね、えらい。

この日の夜は、最終状態を何かしらの方法で探したいと思っていました。 dfsで探そうとしたんですが、何を思ったのか、一本道を構成するdfsを書いていました。疲れていたんでしょうね。「dfs ダメ」と残したままmasterブランチを捨てています。

6/1（5日目）

通勤電車の中で考察してました。

前日に謎のDFSを書いていた私ですが、朝になって冷静になり、みんなのseed=0の共有画像を見比べながら、多様だしランダムにやっても意外と枝刈りのおかげで木ができるんじゃないか？と妄想してました。

夜になったので実装しようとします

6/2（6日目）

寝落ちしたそうです。大変そうですね。

仕事の後は空を眺めてました。

この日も疲れて何もできてなさそうです。

6/3（7日目）

この日も仕事です。

6/4（8日目）

土曜日なのでお休みです。お昼ごろから取り組みます。

ねてたそうです

頑張ってください

残り2日しかないので頑張って実装します。

木の構築

まずは2点swapの山登りで木を構築しました。 それなりに強めの枝刈りを入れると100 msくらいで見つかったりもするみたいです。運が悪いと1.5 secでも見つからなかったりしますが、諦めました。

行ごとに揃える

右の2列と下の2行以外を揃えるコードを書きました。動かしていいところがこれだけあると直感的な操作でマスを自在に動かせることを確認しました。

残ったところは山登りして、この時点で1.9M。結構いい。

6/5（9日目）

よく考えると最右端を残して揃えられるんじゃ？と思い実装したらできました。

列ごとに揃えていくと、最後2行は残ってしまうので、やっぱり手軽なランダム山登り。2.3Mに伸びました。

この後はREが起きたときにファイルに出力するようにしてデバッグを早くしてました。本当は最後の2行も解くための方法は思いついていたんですが、実装が重すぎて間に合わず。

皆さんの解法を見て、ビームサーチやchokudaiサーチも試してみたい気持ちになってます。

これが最終解答の動画です。

最後に

前回のマラソンの解説放送のときにwataさんが天才発想を披露していて、そんなの問題固有の話じゃ・・・とか思っていた私ですが、そのときの話を応用して今回楽しめたので、意外とこういうアドホックな部分が大事なんだろうなー思ったりしました。アドホックをアドホックとして終わらせないというか・・・

いかがでしたか？マラソンは楽しいので、みんなもやろう！