AtCoder Regular Contest-- 229 B問題 B - Halving Subtraction
操作を言い換えて、後ろから見た時、xをと
のいずれかに置き換えることができる。
Aのi番目に注目する。
必要な操作の回数を、j回目の操作で引かれる数を
とする。
このとき、
つまり、操作を選ぶタイミングにかかわらず、になるとき、
から引かれる数は当然
であり、
から引かれる数の幅は、
の操作を選んだ回数に依る。
答えを二分探索する。
コーナーケースに注意が必要。
0回を特別扱いして、少なくとも一回以上操作が必要なことに注意する。
さらに、「2x +1 を選んだ回数」をcとして。
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の最小値から更新されるようにした）。
Codeforces Round 998 (Div. 3) F. Multiplicative Arrays
条件を満たすリストはが並んでいるの中に、一部が約数になっている。
例：k=6のとき
1 , 1 , ... , 1 , 2 , 1 , ... , 1 , 3 , 1 , ... ,1
1を除いた約数を使って積がKになるリストを考える。
このときリストの長さは以下になる。
この値は小さいのでDPによって「積がKになる長さが(最大)Lのリストの場合の数」を求めることができる。
DPの遷移は、
dp[i+1][k] += dp[i][ ] (a|k ,
)
（計算量はよくわからないけど、約数から、約数の約数に遷移するので、かなり早い）
このDPを1からKまで実行することができる。
1がN個並んだ列から「約数列の長さL」個を約数に変更する箇所を選ぶので、 。
問題の答えは各k(=1..K)について、
リストの長さnを1..N
約数列の長さlを1..L
の組み合わせの和なので、立式すると、
dpは求めてあって、Lは小さいので残りの問題はNが大きことになる。
ここで、式を展開すると明らかに規則性がある。
調べると二項係数の性質として、ホッケースティック恒等式として知られている。
ホッケースティック恒等式 :
よってホッケースティック恒等式を用いて、
Nは大きいけど、Lは小さいので、素直に計算すれば良い。
以上を実装してAC。
Codeforces Round 995 (Div. 3) G. Snakes
ヘビは伸び縮みしながら右方向にしか移動できず、他のヘビを追い抜くことはできない。
よって順番を決めれば最適解は一意に定まる。
隣り合うヘビをどれだけ離すべきかは二分探索で求めることができるため、ヘビの並び順を全通り試すことを考える(dist[from][to])。
しかし、全通りは試せないので、bitDPを考える。
dp[s][i] = ヘビの集合sを決定済みで、最後のヘビがiの場合の最小コスト
で間に合うかと思ったんだけど、TLE。
原因はdistの計算が重いことなので、二分探索ではなく、貪欲に距離を求めてO()に改善する
1. 二匹のヘビが並んだ状態からスタートしてシミュレートする
2. ヘビが重なったら、右のヘビを一歩ずらす
3. ずらした回数が求める距離になる
以上でAC。
1回の操作で、人iから見て 右にある料理は近づき、左にある料理 は遠ざかります。
よって、人iから料理iへの最短距離を右方向・左方向でそれぞれ right と left の配列に分けたとき、答えは以下のように表せます。
操作を1回行うと、右にあるものの距離は1ずつ減少し、左にあるものの距離は1ずつ増加するため、
right = right.map(x => x - 1); left = left.map(x => x + 1);
と更新します。
また、right の要素で0になったものは left へ、left の要素で になったものは
right へ移動させます。
このようなシミュレーションを行いながら、最小値を求めることで AC が可能です。
全体に +1 や -1 の操作を愚直に行うと計算量が大きくなるため、効率化が必要です。
具体的には、right と left を ソート済みの両端キューとして管理し、それぞれの合計と操作回数を参照することで高速に処理します。
全体に +1 や -1 を加える処理はスキップし、合計の処理を以下のようにシミュレートします。
sum_right -= len(right); sum_left -= len(left);
これにより、答えは
答え = sum_right + sum_left
として求められます。
現在の値は
right.pop_front() - 操作回数n
として計算し、必要に応じて left へ移動させます。その際にsumも適切に再計算します。
leftについても同様に処理します。
(ChatGPTで推敲済み)
