RECRUIT 日本橋ハーフマラソン 2023冬 (AHC018) 参加日記
目次
最終解法
日記
最終結果
最終解法
最初に距離をもとに水源を含む最小全域木を求めて(初めにすべての水源を結んでおけば計算できる)、使われなかった水源はこれ以降使わないようにする
上の操作で残ったところから上下左右に掘っていき、固い部分が来たら方向を変えてまた掘っていく。というのを繰り返す
- 削るマスと今まで壊してきたマスとの距離が12未満の場合、削るのをやめるようにしてます
そのあと、2つの水源/家での最短距離を出してそれを使ってもう一度最小全域木を作る
辺が結ばれているところの頂点間を壊していく。現在から目標とする場所が右上にあったとき、一つ上と右のところを見てすぐ壊せそうな方向に進むようにする
岩盤を壊すパワーは、隣接しているところですでに壊れているときは、その場所を壊すのに使ったパワー*(3/5)で壊す(2回くらいで壊れるのを想定)、初めて壊すときは初期値を決めてだんだん倍にして壊れるまでやる
という感じです。あんまりいい解法ではないです
(提出コード：https://atcoder.jp/contests/ahc018/submissions/39207430)
日記
1,2日目
月と火にテストがあったので実装はせず考察だけやることにした
問題を見た感じの感想
初期の盤面が与えられない&壊れるか壊れないかしか判定できないのであんまり岩盤が固いところはいかないほうがよさそう
最初に盤面の全体を何個か削ってみて盤面を推測するとかもできそうだけど、削る回数がかなり増えてしまう
薄いところだけを行きたいけど、盤面を確認するために削りすぎるとダメそう
どれくらい周りを探索していいのかとか、どれくらい遠回りするべきなのかがまだよくわかってないのでSijがすべてわかった時でどうなるか確認したい
3日目
残り1日テストが残ってたんですが、コードを書いてしまいました...
Sijをを受け取って必ず1回で一つの岩盤を壊せるようにしてみた
上下に行くだけいって、左右に動いて目的地まで付くのをコストにして、kruskal法を使って求めてみる
もう一つ、Sijで各頂点の最短経路を求めてそのコストに応じてkruskal法を適用する
この解法でだいたい理論値がでるはず
seed0だと8倍くらいコストに差が出た(思ったより大きい)
少し色が濃い部分に入るだけで値が1000近くあったので、色が薄い部分だけをたどるような解法にしてみる
4日目
thunder本を買う
テストが終わって疲れて寝たので何も進んでないです
5日目
とりあえず、上下の移動から左右の移動をする、みたいな動作でやってみる
掘削の初期値はを決めて、壊すまでにある程度回数がかかるならパワーを2~4倍にする、1回で壊せるなら1/4~1/2倍にする、みたいなことをして、1ブロックを壊を1~3回くらいで壊せるようにしてみる
seed=0のとき、Cost=539798になった(visualizerの見た目は前のと同じなので省略)
Sijを知っている時がCost=511018だったので少し悪くなってるくらいになった
Sij込みの時のプログラムが残っていて、冗長な部分が多いです↓
提出コード(絶対スコアは11672399): https://atcoder.jp/contests/ahc018/submissions/39096621
通る場所が固定されているのでなるべく壊れやすいところだけを通れるようにしたい
それを一回、Dijkstraで適当に探索してみたところ、こんな感じになってしまったのでもう少し簡単な問題設定にして実装する(これで1日使った...)
上下左右の移動を回数を決めてなるべく壊れやすいところに移動するように探索してみる
が、あまりうまくいかず...
掘削回数が多く、Cが小さいときにスコアの改善があったのでひとつ前の解法と場合分けしてやってみると少し更新
2ケースだけTLEするが、ローカルでテストしても問題がないため原因がわからず...
6日目(木曜)
この日は実装はほとんどできず、考察だけした
いろいろ考えたけど、どれも具体的にどうやって実装すればいいのかわからなくて詰む
7日目(金曜)
一つ実装できそうな案があったのでそれを実装する。内容はこんな感じ
すぐ壊せるところだけ上下左右に壊していき、いけなくなったら方向を変えるというのをBFSみたいに繰り返す
これをすべての頂点について行う
そのあとに、kruskal法で伸ばしたところからの距離がなるべく小さくなるようなところ同士を結ぶように愚直に掘る
実装するとこんな感じになった(seed=0)
1~2個目を行うと、
こんな感じで、最後につなげると、
こんな感じになった
前回のコードのスコアが393390くらいだったのでだいぶ良くなった
まだ、冗長な部分が多いけど、いい感じに伸ばせてそう
提出 -> 16Gから14Gまで下がる...
少し訂正して何とか17Gまでは上がるが渋すぎる(実際は20G近く行くんじゃないかと思ってた)
8日目(土曜)
17.3Gからちょっとしたことを改善して少しだけ上げて、17.6G（絶対スコアは9.3M）
伸びなさ過ぎて気力を失くす
9日目(日曜)
これ以上何やればいいかわからなかったので、一番良かったコードを最終提出する
最終結果
暫定で380位、システス後の最終結果は374位でした...
今回の敗因は、思いついた案を実装して確認せずに、考察の時点でやめてしまったところな気がする
thunder本を読みこんで、次のAHCでいい結果残せるように頑張ります
