# AHC034 短期

https://atcoder.jp/contests/ahc034

## 注意
visualizeの要否を見極める(手元で遊ぶの大事)
DFSの手を忘れない
全乱択でもいいから回す

## 所感
整地する問題。
土砂を積む、降ろす、運ぶそれぞれに対してコスト。
文脈は強そう。ビーム系？

総和0が保証されているとのこと。
基本は全部平らに。

移動に以下のコストがかかるので積みまくりはNG

- ダンプカーに積まれた土砂が d のとき、この操作は 100+d のコストが発生する。

ステージはいい感じに起伏が分布していて、ランダムじゃなさそう。

あんまり行き来したくないので、ルートを決め打って余分な土を拾いつつ撒きつつがいいか。
土が大量に溜まってきたら、未来の訪問先に一旦捨てにいくのあり。
最後は下ろして終わるので、終点はマイナスにするの大事。

常に土砂がマイナスにならないのが理想だが。マイナスになっても後から持って行くでいい。

一旦グルグルまわって、diff=0にできるようにした。
このあとはルートの選び方かな。

提出、現在30位。
6,412,186,844点、149 ms。→今更だけど、制限時間は2s。
1位が以下の点。まぁ行けるんじゃない？
7,732,810,292点

ルートをどう選ぶか。
→土砂のプラマイの量で矩形に区切るのが良さそう。
→山の頂点を起点に矩形を区切るか。
→矩形の中をグルグルかジグザクか、色々回り方はある。

とりあえず貪欲で色んなパターンの周りができるようにする。
比較のためのコスト計算

ぐるぐるを時計と反時計、
じぐざぐを横と縦、
それぞれ入れて提出
7,393,895,841点。31位。まぁまぁ。
1位がyosupoさん
9,393,418,419点。

> 0=1.00 s= 109292 N/M/K=20/0/0
1=1.00 s= 116986 N/M/K=20/0/0
2=1.00 s= 112983 N/M/K=20/0/0
3=1.00 s= 160552 N/M/K=20/0/0
4=1.00 s= 143964 N/M/K=20/0/0
5=1.00 s= 152246 N/M/K=20/0/0
6=1.00 s= 157244 N/M/K=20/0/0
7=1.00 s= 133414 N/M/K=20/0/0
8=1.00 s= 127493 N/M/K=20/0/0
9=1.00 s= 126444 N/M/K=20/0/0
TSum=1340618.0
Ave=134061.8
RAve=1.0

> 0=0.94 s= 109292 N/M/K=20/0/0
1=1.00 s= 117184 N/M/K=20/0/0
2=0.99 s= 112983 N/M/K=20/0/0
3=1.00 s= 160552 N/M/K=20/0/0
4=0.98 s= 121516 N/M/K=20/0/0
5=0.89 s= 152246 N/M/K=20/0/0
6=0.95 s= 157244 N/M/K=20/0/0
7=0.98 s= 133414 N/M/K=20/0/0
8=0.87 s= 127493 N/M/K=20/0/0
9=0.98 s= 126444 N/M/K=20/0/0
TSum=1318368.0
Ave=131836.8
RAve=0.9582280629608008

> 10=1.00 s= 141501 N/M/K=20/0/0
11=1.00 s= 113100 N/M/K=20/0/0
12=1.00 s= 123241 N/M/K=20/0/0
13=1.00 s= 141174 N/M/K=20/0/0
14=1.00 s= 113675 N/M/K=20/0/0
15=1.00 s= 135066 N/M/K=20/0/0
16=1.00 s= 111029 N/M/K=20/0/0
17=1.00 s= 141467 N/M/K=20/0/0
18=1.00 s= 155653 N/M/K=20/0/0
19=1.00 s= 131228 N/M/K=20/0/0
TSum=1307134.0
Ave=130713.4
RAve=1.0

> 0=0.94 s= 109292 N/M/K=20/0/0
1=1.00 s= 117184 N/M/K=20/0/0
2=0.99 s= 112983 N/M/K=20/0/0
3=1.00 s= 160552 N/M/K=20/0/0
4=0.98 s= 121516 N/M/K=20/0/0
5=0.89 s= 152246 N/M/K=20/0/0
6=0.95 s= 157244 N/M/K=20/0/0
7=0.98 s= 133414 N/M/K=20/0/0
8=0.87 s= 127493 N/M/K=20/0/0
9=0.98 s= 126444 N/M/K=20/0/0
TSum=1318368.0
Ave=131836.8
RAve=0.9582280629608008

> 0=0.98 s= 105564 N/M/K=20/0/0
1=0.99 s= 116614 N/M/K=20/0/0
2=1.00 s= 112171 N/M/K=20/0/0
3=0.99 s= 159622 N/M/K=20/0/0
4=0.99 s= 120022 N/M/K=20/0/0
5=0.90 s= 150316 N/M/K=20/0/0
6=0.95 s= 156024 N/M/K=20/0/0
7=1.00 s= 128620 N/M/K=20/0/0
8=0.87 s= 127099 N/M/K=20/0/0
9=0.98 s= 123796 N/M/K=20/0/0
TSum=1299848.0
Ave=129984.8
RAve=0.9663492982758953

> TSum=1.3306139E7
Ave=133061.39
RAve=0.9957034293812703

終了
7,764,359,595点。50位かな？→53位っぽい。

## 反省
時間を使えてないのはよくない。が、適当にぶらすのも難しかった。
途中、積んでる土砂の量に応じていい感じに置きに行けると良かったが。。。

wataさんの、なるほどなー。
https://x.com/wata_orz/status/1802280760331903075

4位のsquareさんもこの方針っぽい。
5位のkotamanegiさんもだった。

1位のyosupoさんはちょっと別格だな。
上下左右にいって、適度に積み降ろしするのか。
→経路決め打ちしたら最小費用流で最適解が決まるらしい。
https://x.com/yosupot/status/1802281518133555699

6位のnrvtさん、ちょっとおもしろい。
規定のルートだけど、多分積み降ろしを必要分しかやってないから、移動コストが最適になっているのか。
https://x.com/nrvkpr/status/1802288040918020133

IHaさんの、これは延長線上の解だ。ここまでは頑張りたかったな。
貪欲の折り返しを乱択にするのも、思いつかないといけなかった。
https://x.com/IHa_ProCon/status/1802288532247249007

2位の物理好きさんの解説。わかりやすい。
https://physics0523.hatenablog.com/entry/2024/06/16/214158

学びとして、どこかにペナルティを押し付けられるなら、まとめた方が強い。

基本テクとしてこれ覚えておきたい。
https://x.com/chokudai/status/1802294101762810306

kiriさんのフローのupsovle。
https://x.com/kiri8128/status/1802392043072970938

今回の評価
・移動コスト高めだから、パターン決め打ちが強そう：◯
・マイナスになった所は後から持って行く：✕→事前に必要分を借金
・ルートが決め打ちだから、乱択貪欲ができない：✕→折り返しのみ乱択したらよい。