人間だけど競プロやる

解けなかった問題を理解できたら記事を投稿します。日本語の解説が見つからなかったもの中心。

Codeforcesプチまとめ 25年8月

Codeforces

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

Codeforces

Codeforces Round 998 (Div. 3) F. Multiplicative Arrays

解の構造

条件を満たすリストは1が並んでいるの中に、一部が約数になっている。
例：k=6のとき
1 , 1 , ... , 1 , 2 , 1 , ... , 1 , 3 , 1 , ... ,1

1を除いたリストの場合の数を考える

1を除いた約数を使って積がKになるリストを考える。
このときリストの長さはlog_2{K} +1以下になる。
この値は小さいのでDPによって「積がKになる長さが(最大)Lのリストの場合の数」を求めることができる。
DPの遷移は、
dp[i+1][k] += dp[i][ \frac{k}{a} ] (a|k , a \neq 1 )
（計算量はよくわからないけど、約数から、約数の約数に遷移するので、かなり早い）
このDPを1からKまで実行することができる。

リストの長さをNにする

1がN個並んだ列から「約数列の長さL」個を約数に変更する箇所を選ぶので、{}_N C_L 。

問題の答えを考える

問題の答えは各k(=1..K)について、
リストの長さnを1..N
約数列の長さlを1..L
の組み合わせの和なので、立式すると、

\displaystyle{ \sum_{l=1}^L\sum_{n=l}^N{}_n C_l \times {dp[l][k]} }

（リストの長さがl未満は明らかに0なので除外した。そのためにシグマの順番を変えた。）

dpは求めてあって、Lは小さいので残りの問題はNが大きことになる。
ここで、式を展開すると明らかに規則性がある。
調べると二項係数の性質として、ホッケースティック恒等式として知られている。

ホッケースティック恒等式 :

\displaystyle{\sum_{a=B}^A{}_a C_B = {}_{A+1} C_{B+1}}


よってホッケースティック恒等式を用いて、

\displaystyle{ \sum_{l=1}^L\sum_{n=l}^N{}_n C_l \times {dp[l][k]} }
\displaystyle{= \sum_{l=1}^L {}_{N+1} C_{l+1} \times {dp[l][k]} }

Combinationを求める

Nは大きいけど、Lは小さいので、素直に計算すれば良い。


以上を実装してAC。

Codeforces Round 995 (Div. 3) G. Snakes

Codeforces

Codeforces Round 995 (Div. 3) G. Snakes


ヘビは伸び縮みしながら右方向にしか移動できず、他のヘビを追い抜くことはできない。
よって順番を決めれば最適解は一意に定まる。
隣り合うヘビをどれだけ離すべきかは二分探索で求めることができるため、ヘビの並び順を全通り試すことを考える(dist[from][to])。



しかし、全通りは試せないので、bitDPを考える。
dp[s][i] = ヘビの集合sを決定済みで、最後のヘビがiの場合の最小コスト

  • ヘビiからjへの遷移:
    • dp[s|1<<j][j] = min(dp[s|1<<j][j], dp[s][j]+dist[i][j])
  • 計算量:
    • distの計算に O(N^2Q\log Q)
    • dpに O(2^NN^2)


で間に合うかと思ったんだけど、TLE。


原因はdistの計算が重いことなので、二分探索ではなく、貪欲に距離を求めてO(N^2Q)に改善する
1. 二匹のヘビが並んだ状態からスタートしてシミュレートする
2. ヘビが重なったら、右のヘビを一歩ずらす
3. ずらした回数が求める距離になる




以上でAC。

AtCoder ARC268 E問題: Chinese Restaurant (Three-Star Version)

AtCoder

1回の操作で、人iから見て 右にある料理は近づき、左にある料理 は遠ざかります。
よって、人iから料理iへの最短距離を右方向・左方向でそれぞれ right と left の配列に分けたとき、答えは以下のように表せます。

\displaystyle{ \text{答え} = \sum(\text{right}) + \sum(\text{left}) }

操作を1回行うと、右にあるものの距離は1ずつ減少し、左にあるものの距離は1ずつ増加するため、

right = right.map(x => x - 1);
left = left.map(x => x + 1);

と更新します。

また、right の要素で0になったものは left へ、left の要素で \frac{N}{2} になったものは 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で推敲済み)

Codeforces Educational Codeforces Round 162 (Rated for Div. 2) E. Count Paths

Codeforces

計算量がなぜ間に合うのか自信がない。

fig.1
fig.2

ある頂点P（色c）に注目したとき、パスをつくれる頂点は図のようになる。
DFSで戻るときにパスの数を計算しながら、部分木の色のヒストグラムをマージしていく。
（色c以外は合計して、色cは1にする。）


深さが最悪ケースではマージテクをつかうことで計算量を抑えることができる。
逆にマージする色のヒストグラムが大きいときは、二分木が最悪ケースで、深さがlogNに抑えられる。
以上から実行時間が間に合う、のだと思う。


実装時はサイズが大きいヒストグラムをコピーしないよこうに注意する。
作れるパスの数の計算の仕方は図にかいた通り。

codeforces Educational Codeforces Round 162 (Rated for Div. 2) B. Monsters Attack!

Codeforces

公式解説は、インデックス1まで移動してきた敵を一気に倒す。
使わずに余った弾丸は次のターンに持ち越すことにしても結果は変わらない。
というもの。
気づかずに少しめんどくさい解法をつかったのでメモしておく。


敵を攻撃し始めないと間に合わない締め切りを求める。
締切は X[i] - \lceil \frac{A[i]}{K} \rceil 。
これをpriority queueにいれて。締切が早い順に処理していく。
各ターンで、残弾がある限り、もっとも締切が近いものを、1ターン締切を伸ばすように処理してpriority queueに入れなおす。
締め切りを伸ばすのに必要なダメージは A[i]\bmod K (ただし0のときはK) で求める。
締め切りが現ターンより小さければNOを出力。
（締め切りが近いものからKダメージをフルに使うとWAなので注意）