Codeforcesプチまとめ 25年8月
DPは二次元配列で考えたほうがわかりやすい。
遷移については具体的に手を動かすと、i%K -> i%K+1への遷移しかなくて、i%K +2 のようにスキップすることはないとわかる。
答えが正しく求まるからといって、Kが大きい場合をケアしないと、DPテーブルが確保できず、TLEやMLEになると思われる。
各iについて、
・b[i]=1ならa[i]+K+中央値
・b[i]=0ならa[i]+「a[i]を除いた配列に操作を施してできる中央値の最大値」
のmaxが答え。
なんだけど、indexの扱いがめんどくさくてものすごくバグった。
D1も含めて、操作が0回でも良いことに注意。
素因数分解して、不足する素因数、余る素因数を求める。
それぞれ合成数にしたあと、約数列挙する。約数を用いてDPをして、最小手数を求める。
DPをしないと（たとえば大きい数から割っていけばいいみたいな）貪欲では正しい答えが求まらない。
頂点ごとに連結する頂点の色とコストをmapで持ち、クエリごとに自分自身と親の状態を更新して、差分計算する。
自分自身の状態を更新するのに必要な状態が多く必要でややこしかった。
自分の実装では、「最後に自分を更新したときの親の色」を持つことでうまくいった。
スターグラフになっている部分を別計算みたいな方針ではうまくいかなかった。
グラフの橋を求める。
頂点1からNまでのルートを一つ求める。
このルートは1からNまで移動するときに使わなければならない橋すべてを通る。
ルートに含まれる橋の端点すべてを始点として、各頂点への最短距離をもとめる。
答えは橋の辺のIDなので、始点でつかった辺のIDを持ちながら更新していく。
答えは辺のIDの最小値なので、距離が等しいときも、答えの辺のIDが更新される可能性があることに注意（コーナーケースがあるかわからなかったので候補をpriority_queueにいれて辺のIDの最小値から更新されるようにした）。
