---
# System prepended metadata

title: AHC034 短期

---

# AHC034 短期

https://atcoder.jp/contests/ahc034

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

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

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

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

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

ステージはいい感じに起伏が分布していて、ランダムじゃなさそう。
![image](https://hackmd.io/_uploads/ByLtWZ3BA.png)
![image](https://hackmd.io/_uploads/BJ0cWW2rA.png)

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

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

一旦グルグルまわって、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
![image](https://hackmd.io/_uploads/ryyzqEnBC.png)

4位のsquareさんもこの方針っぽい。
![image](https://hackmd.io/_uploads/BJbAcE2rR.png)
5位のkotamanegiさんもだった。
![image](https://hackmd.io/_uploads/S1KxsE2SA.png)

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

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

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

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

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

基本テクとしてこれ覚えておきたい。
https://x.com/chokudai/status/1802294101762810306
![image](https://hackmd.io/_uploads/r1NbIHhSR.png)

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

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