ARC 098

いつもはvmware+linux+vscodeで出ていたんだけど,今回はwindows+wsl+clionで参加(したかった)

F

お金を配りながら移動していく,ただし移動するときには頂点ごとにしきい値がある
→サンプル1を書いてみて想像をする
 →どうやらお金はありすぎて困ることはない
  →二分探索?

二分探索できるのでとりあえず二分探索してみる(logは定数なため)
→最初のお金Zが決まるから可能か?を求める
 →お金を配ると結局どうなる?
  →移動可能範囲が狭まっていく
   →移動可能な範囲が狭まっていくなか,うまく全部の頂点を辿れるか?
    →ものがstrictに減っていく時は逆から考えると良い(一般に減らしていくより増やしていくほうが簡単なため)

ゴールから考えるとどうなる?
→最初のお金が決まっているため最後のお金も当然決まる
 →お金を頂点から回収していって,だんだん移動可能範囲が増えていく
  →どうやら多項式にはなった(TLEだけど)

どうやらゴール位置が重要っぽい
→例えばゴール位置を決め打つと簡単に計算できるか?
 →priority_queueとか使って探索していくとうまくやると行けそう
  →じゃあどうやって複数のゴール位置についてやる?
   →ゴール位置が複数あると,複数位置からじわじわ探索が広がっていって,衝突したらmergeみたいな雰囲気がありそう
    →データ構造をマージする一般的なテク?

制約もそれっぽいし,解法はデータ構造をマージする一般的なテクだろうと想像がつく
→log 3個?
 →流石にデマパートはlog 2個からは落とせなそう(なんか隣のやつをsortして持っておくみたいな操作が必要そう),じゃあ二分探索やめるしかない?
  →二分探索やめるか

二分探索をやめる
→最初に持っている額を決め打てない
 →最初は0円スタートで,足りなくなるたびに適時無からお金を生成する感じで

まとめる
→ゴールから考える
→最初は0円スタート
→それぞれの頂点について,「もしこの頂点がゴールだったら?」を並列にシミュレーションする感じ
 →シミュレーションそれぞれについて,できる限り進めて,進まなくなったら「無からお金をいくら生成すればシミュレーション進みます」を計算してpriority_queueに突っ込む,それが最小の額だけ無からお金を生成して,シミュレーションを進める
  →これを繰り返せばなんとかなりそう,色々大変だけど計算量もなんとかなる?
   →AC

C

累積和流行ってる?

D

0いるか?僕はいらないと思います

E

えー全然わからない,おわりです →よく考える
 →最大と最小の両方に自由度があるのなに?
  →よくみるとN=2000
   →最大か最小どっちか固定して,それぞれO(N)に違いない,自由度1ならなんとかなるだろ

どっちを固定したい?
→最大固定はよくわからないけど,最小固定はうれしさがある(部分列にいくつかの要素を含められないという条件になるため)

最小を固定してみる
→いくつかの要素が取れなくなる
 →要するに数列が分解される
  →いくつかの数列が与えられる,取り除いたやつの最大値を最小化

可能かどうかの判定は?
→数列の要素数から簡単にわかる

最大値の最小化は?
→そもそも最小値は絶対取り除けるんだから,最大値の最小化もクソもなくないか?
 →[1], [100, 100, 100, 100]とかになると1を取れなくなるのか
  →連結成分ごとに取り除ける個数が決まっていて,そのなかではかなり自由?(APC Dを思い出すなあ(唐突な宣伝))
   →正しそう