AHC034 お疲れさまでした!
最近 H レーティング全然上がらね~~~って出るの躊躇していて、問題は見るけど提出しないみたいなことが続いてしまっていました。
結果的に半年くらいぶりに参加することになりました。
その結果とても良い順位が出たので、せっかくなので記録として残したいと思います。
わかりづらい点があったら提出コードを参照してください
問題概要
マスあって、各マスには初期高さが決まっている。
コストを小さくマスの高さを 0 に整地してね。
マスの初期高さの総和は 0 だよ。
やったこと
うーん... DP すればいいんじゃね??
ということで DP で解きました。
上位の方々はみんな焼きなましとかビームサーチとか最小費用流している印象なので、かなり珍しい解法だったのではないかと思います。
まったくヒューリスティック的手法は用いていません。
詳細を書きます。
DP 配列を とします。
マスの高さを 0 としたとき・ にいるときの状態を表します。
保持しておく値は、 (コスト, ダンプカーに積まれた土砂の量, 前にいた位置, すでに 0 に整地したマスを管理する bitset) の 4 値 tuple です。
bitset は ビットで、 64 倍高速化されることになるので、計算量の話では無視します。
遷移としては、 から に移動する、 を 0 に整地するといった遷移です。
各マスについて中途半端な値に整地するということは考えていません。
遷移しないのは、
- すでに整地した場所
- 高さがマイナスで、土砂の量が足りない
のケースで、それ以外の遷移できるケースなら高さを 0 に整地して、コストを加算します。
このとき、ダンプカーに積まれた土砂の量を保持しているので、マンハッタン距離を用いてコストが計算できます。
コストが最小となるように遷移を行っていきます。
の小さい順に遷移を行っているため、 には順番に決めていったときの各マスの最小コストが保持されることになります (たぶん)。
DP の状態数は であり、各マスからの遷移先は 通り、各遷移の計算が です。
全体で です。
こうして計算した後、 の最小値を答えとします。
この解の遷移を復元して、解を得ます。
少し不安だったので bitset 高速化以外にも、 array を使うようにしたり、 の値を constexpr
化したりしました。
コードテストで試してみたところ、 100ms くらいで終了したので、これを提出しました。
提出 #54634686: 7732810292 点
するとなんと、開始から 80 分くらい経過していたにもかかわらず、提出時点で 1 位でした!
とても想定していない結果だったので、驚いて震えていました...。
First Sub が 1 位とかいくらなんでも面白すぎる、今終わってくれ~
実行時間に余裕があったので、スコア計算について、運搬している土砂の量・マスの高さの寄与量の重みを変えてみたりしました。
- 提出 #54636202: 重みを 1 - 3 で試してみる。 7940486648 点。
- 提出 #54636749: 重みを決め打ち。 7974393661 点。
- 提出 #54639166: さらに調整。 7988936621 点。
それほど変わりませんでした。
最後に、上位 5 個かの解を保持しておくようにしてみましたが、これもあまり変わりませんでした。
提出 #54641862: 7942002492 点
そして終了です。
結果と感想
AHC034 お疲れさまでした~ 33 位! かな? First Sub が提出時 1 位をとってしまいびっくり でも 1 ページ目死守できず... パラメータ調整うまくやったらもうちょい点数上がったかなぁ... やったこと: † ただの DP † ヒューリスティック的なことはほぼ何もやってない...w atcoder.jp/contests/ahc03…
A/H 初の橙 perf!やった~!! a01sa01toさんのトヨタ自動車プログラミングコンテスト2024#6(AtCoder Heuristic Contest 034)での成績:36位 パフォーマンス:2403相当 レーティング:1723→1873 (+150) :) Highestを更新し、1 級になりました! #AtCoder #AHC034 atcoder.jp/users/a01sa01t…
最終 36 位でした! 初の橙 perf!!
ここまでいい結果になるとは思っていなかったので、とても嬉しいです!
1 ページ目を保持できるかな~と思っていたんですが、みなさんの最後の追い上げがすごかったです...。
時間があれば中途半端な高さに整地するとか考えてみたかったですが、なんも思いつきませんでした...。
ヒューリスティック的な手法を使わずに上位に入れてびっくりです。
最小費用流は全然使ったことないので思いつかなかったのが残念ですが、 DP で解けたので満足です。