AHC018参加記
概要
焼きナマステ～！ froriverです！
先日AtCoderで開かれました、
[RECRUIT 日本橋ハーフマラソン 2023冬( #AHC018 )]
に参加して来た記録を綴ったものになります。
759位でした！
初めてアルゴリズムっぽい解を出せたのが嬉しく、記事を書きました。
AtCoderとは
競技プログラミングサイトの1つで、
規定時間内で、早く、正確に問題の答えを出すアルゴリズム部門と、
今回のヒューリスティック部門があります。
1週間～1ヶ月など長めの期間で、
最適解を出すのが難しい問題に対し、
できるだけ良い解を作成するコンテスト
となります。
日本橋ハーフマラソンと私
2022年8月9日～16日にも、同様のコンテスト
RECRUIT 日本橋ハーフマラソン 2022夏
が開かれていました。
答えのない問いに試行錯誤する
思いついたアイデアをコードに落とす
自分の書いたコードで徐々にスコアが改善する
という面白さを知り、見事に心を奪われて、
以後見かける度にコンテストの開催を楽しみにしていました。
AHC018
コンテスト期間は
2023年2月18日(土)～2月26日(日)までですね。
開催中は紙を利用して、アイデアをまとめていましたが、
当時を思い出しながら時系列順に書きます。
反省点のまとめ
実装の蓄えが十分で無かった
時間配分のミス
問題文のCの意味の読み落とし
問題
ある硬さの岩盤で構成される土地をボーリング調査します。
岩盤を掘るためには体力を消費します。
できるだけ少ない消費体力で、水源から全ての家に水を引ければOKです。
掘るたびにプログラムとやり取りができます。
ただし、岩盤の硬さは不明で、完全に壊れたときしか分かりません。
N：土地サイズ (N=200)
W：水源の数 (1 ≦ W ≦ 4)
K ：家の数 (1 ≦ K ≦ 10)
C ：体力の消費値 (C = 1, 2, 4, 8, 16, 32, 64, 128)
S{ij}： 岩盤の硬さ (10 ≦ S{ij} ≦ 5000) ※これは与えられない
経過
初日
問題を読みます。
先輩コーダーは皆、「問題と制約をしっかり読む」ことを挙げています。
それでも読み落としが出てしまうので、
私は紙に一旦問題を書き写し、レジュメを作って理解しています。
あとはビジュアライザの使い方を確かめ、
準備して頂いているサンプルを提出し、中身を確認します。
今回のサンプルプログラムは綺麗にクラス分けされていて、
非常に読みやすく簡潔ですね。
こんなコードを書きたいものです。
入力もチェックします。
硬さはプログラムへの入力としては与えられませんが、
入力で数字として与えられるようです。
プログラムはインタラクティブ形式で、
こちらが破壊したい岩盤の座標と壊す強さを送ると、
-1 ： 不正な出力だった
0 ： 破壊できなかった
1 ： 当該岩盤は破壊できたが、まだ水が引かれていない家が存在
2 ： 全ての家に水が引かれた
という返答が逐次返ってくるようです。
インタラクティブ形式の問題に取り組むのも私は初めてです。
サンプルプログラムのおかげでかなり理解が進みました。
ただし、特に手は動かせず、問題を理解することで終わった1日でした。
2日目
問題へのアプローチを考えます。
硬さが小さそうな場所ばかりを通って、
家と水源を接続できれば良さそうです
しかし、肝心の硬さは掘ってみなければ分かりません。
けれども、インタラクティブ形式のため、1度掘ってしまうとそれが回答となり、掘り戻すようなことはできません。
全部を掘るのはコストが大き過ぎるので、
代表点を決めて掘るのが良さそうです。
一定間隔の格子点を代表点として採掘し、
代表点の周囲も、その硬さと近いと仮定して、
最短経路を出す方法を取ることにしました。
格子はP分割するものとして作り、とりあえずP=10に設定しました。
分割後の1つの格子サイズは19(0～19)または、20(20～)です。
座標にしたときに分かりやすくなるよう、望んでこの仕様を決めましたが、
結果的には、バグ多発地帯になってしまいました。
毎回の採掘をするパワーですが、
無駄のないように小さな値の方が良さそうです。
ただ、1にするとTLEしてしまいますので、良い値だった10に設定しました。
この日は、なんとか代表点を仮で掘るところまで実装しました。
3日目
代表点が掘れたら、今度は家や水源から、最寄りの代表点までを
結ぶ関数を作成しようとしました。
round関数を使って単純な四捨五入で実装しようとしましたが、
格子点は20離れているため、
136ー[140]ー144 145ー150ー154 155ー[160]ー164
の例では、代表点が140と160に対して、
roundは10刻みのため、145から154が150に丸め込まれてしまいます。
ですので、いったん全ての座標を10/(N / P)して、
68ー[70]ー72 72.5ー75ー77 77.5ー[80]ー82
roundをかけて、
65ー[70]ー74 75ー[80]ー84
(N/ P)/10倍して戻す
130ー [140]ー149 150ー [160]ー 169
という風にして、最寄りの代表点の座標を求めました。
4日目
小手先の操作ではありますが、
水源のうち、最も硬さが小さい水源から経路を形成する
そこで選んだ水源から最も近い順に家を並び替える
という処理も実装しました。
硬い山を越えないといけない場合は、
複数の水源からアプローチした方が良いかもしれないと思いましたが、
当面は、1水源から全ての家を繋ぐことを考えます。
5日目
6日目
とても悲しい2日間でした。
まずは幅優先探索(BFS)、深さ優先探索(DFS)を実装しようとしたものの、
結局、ゴール頂点を通ってもなお探索を続けてしまい、
全ての頂点を探索するバグが直せず、どちらも実装できませんでした つД｀)
グラフは(y, x) = 硬さの辞書という形で実装し、
アクセスを高速化しようとしたのですが、
そのために、例示されているアルゴリズムとの対応が取りにくかったのも一因かもしれません。
成果が出ず悲しいので、次の代表点をランダムに選ぶようにして
繋がせて、他の部分のテストをしていました。
当然スコアは上がらず、
サンプルプログラムよりもスコアが低い状態が続いていました。
サンプルプログラムの最初の壁がなかなか超えられません。
7日目
8日目
ここまでは、経路算出を自前で行うつもりで、
探索アルゴリズムを書いていたものの、
遷移可能な代表点の中から最小の代表点を選ぶだけなら、
ダイクストラ法で十分ではないか
と気付き、方向転換して、ダイクストラ法の実装を目指しました。
なんとか実装できました！動作を見てみます。
どん！
繋がった線を見たときは、思わず感動してしまいましたね。
この実装を境にサンプルプログラムを上回るスコアが得られました。
9日目
代表点の見積もりコストで採掘してもまだ掘り切れていない場合、
＝代表点と代表点の間に山の裾野がかかっている場合
そのポイントを横に避けて、斜めに迂回する
というプログラムを書こうとしましたが、割と難しそうで断念しました。
結局、いくつかのテストケースで良さそうなパラメータに調整して、
プログラム自体は8日目で作成したものを提出してフィニッシュです。
まとめ
1週間の試行錯誤、やっぱり楽しかったですね。
悔しかった点を挙げるとキリがないですが、
毎盤面で変化するCの意味に気付くべきでした。
岩盤の硬さを大きく超えて採掘するのが勿体ないと感じて、
できるだけ細かく採掘(S=10)していました。
ただ、コストは和のS+Cで計算されるので、
Cが大きいときは一気に削ってしまった方がよかったんですね。
(例)硬さ11をS=10, C=128で削ると、コストは2×(10+128)になる
割と勿体なかったポイントですので、次は気を付けます。
意味のないパラメータなんて用意しないですものね。
あとはやはり、実装力と言いますか、
代表的なアルゴリズムは自前でストックしておくべきですね。
バグの修正で他の方針を検討することができなかったので、
こちらも反省点です。
しばらくはアルゴリズム部門への対策を含め、
代表的なアルゴリズムの勉強に費やすことにします。
他の参加者さんもお疲れ様でした。
アップロードされた解説を読みながら、勉強させて頂きます。
主催と運営をしてくださった皆様に感謝します。
ありがとうございました。
焼きナマステ！