RCO presents 日本橋ハーフマラソン 予選

参加しました、結果からいうと予選通過で本選に出場することが決まりました
オンサイトコンテストに出場することは初めてなのでとても嬉しいです

A.783413
B.9605

RCO presents 日本橋ハーフマラソン 予選 - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

A - Multiple Pieces

2問で3時間、順位はAの順位とBの順位の合計で決まるとのことで、とりあえず2問解いてそれなりにいい結果を出すことを目標にしました。
とりあえずこの問題ですが、ある0でないマスから探索を初めて、上下左右を見て一番数字の大きいマスにつなげていって、8マスつながればそれを
ピースとして確定させるというシンプルな戦略を取ることにしました。ただしゼロはつなげても損するだけなので絶対繋げてはいけません。
どっから繋げていくかですが、最初なので適当に左上から見てつなげていくことにしました。あんまりよくなさそうですがとりあえず点数を取ることが大事だと思いました。
実際実装すると、同じマスを2回使ってしまうというバグが発生したりして困りました(dfsで繋いでいくときに訪問済みをチェックしなかったことが原因だった)

ともかく何とか作ってビジュアライザで見てみたらいい感じに出来たっぽいのでとりあえずそれを提出しました、ここで既に1時間です
点数は216548点とその時点ではそれなりに良く、順位的にも予選通過狙えそうだとモチベーションが上がったのを覚えています
Submission #1141010 - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

それなりに良い点が取れたので急いでB問題に移りました

B - Food Collector

Bは犬が餌を拾う奴ですね。こっちはあんまり良い戦略が思い付かなくて困りました。
犬の周辺5×5マスを見て値の大きいエサがあったらそれを取りに行くとかにしようかなとか思ったんですが障害物があって最短距離で行けないとき
どうしようとか思ってめんどくさそう(というか実装できなさそう)なので止めました
なので私が取った戦略は単純に上下左右見て餌があったら値の大きいのを取りに行く、無かったら適当に歩くというこれ以上無いシンプルな戦略でした。
(各マス目に訪問度みたいなのを記憶させて、出来るだけ訪問してないとこに進むみたいなことはしましたが、何かあんまりうまく機能しなかったっぽいです。)

しかし最初に提出したのはあまり点数が伸びず、原因がよく分かりませんでした。
それでビジュアライザを見てみると何か餌が赤くなってるんですよね……で、それを犬が取っていくと右上の点数が減っていきます。
これを見て「ああ、そうか、エサは0点で止まるんじゃなくて負の方向にドンドン大きくなっていくんだ」と気づきました。
問題文と例をちゃんと読んでいれば気づけたことですが、ともかくビジュアライザがあって助かりました。

でもそれを考慮してプログラムを変更しても、犬が負の値の餌をめちゃくちゃ取ってしまっているんですよね……。
このあたりで既に残り40分しかないという状況でかなり焦ってたことを覚えてます。
「もうこっちは諦めてAに戻ろうかな、でもAは既に競争が激化しているっぽいし……」とか考えてました。

それで必死にBのソースコードを見直していると、dx,dyの縦横を完全に逆にしていたことに気づきました……
なのでそれを直して提出すると10000点弱と、まあまあいい点数になりました。ここで何とか気を持ちなおし、Aの改善に戻ることにしました。

Submission #1142248 - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

A - Multiple Pieces(再)

それで戻ったものの、後30分しかないという状況だったので、大幅な変更は出来ません。そもそも1から戦略を作り直すのも難しいです。
なので既存のものを使って何とか点数を改善したいです。その1つの方法として「大きなブロックから優先して繋いでいくべきじゃないか?」ということを思いつきました。
点数は掛け算なので、できるだけ大きなマス目を余すことなく使っていきたいという発想です。
そのため、今まで左上から見て行ったのを変えて、最初に全マスを見て大きな値を持つマス目が先頭に来るようヒープにドンドン突っ込んでいってから、ヒープから取り出した順にdfsしていくことにしました。
これはちょっとした変更で出来ること(それでもバグらせました)でしたが、この影響が大きく一気に20万点→80万点弱と点数が跳ね上がりました。

Submission #1142583 - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

ここで確か30位くらいで予選通過できる!と一瞬舞い上がりましたが、後15分あったので気を抜いちゃいけないと思いました。
思っただけで実際はこれ以上残り時間で実行可能な改善案が思い付かず、何も出来ずにじれったかったです。

そしてそのままコンテストが終わりました。急いで順位を見ると52位でした。微妙な順位だなあと思いました。
15分前には30位だったのに一気にここですから、やっぱり皆最後の追い込みが凄いんですよね。

予選通過の結果が出るまでそわそわしてましたが、どうやら予選通過できたみたいです。とても嬉しいです。
本戦でどれくらい戦えるか分かりませんが、精一杯頑張りたいと思います。