かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

競技プログラミング 典型問題メモ

競技プログラミングにおける典型知識や問題を書いていきます.
AtCoderなどで出た問題で, 分からなかったり面白かったりしたものが多め.

全列挙できない場合は寄与分を考える

区間の和など, 列挙できない場合は寄与分を考える.
例えば, 長さ{N}の配列の{\frac{N(N-1)}{2}}個の区間においてその区間におけるある値の和を求める問題は愚直に実装すると{O(N^2)}になるが, ある値が何回足されるかを考えることで計算量を落とせる.

拡張ダイクストラ

距離と頂点だけを持つのではなく, 他の情報も持って行うダイクストラ

複数の頂点間の辺の張り方

https://www.slideshare.net/secret/r8gjH9xYxFR0Fu

部分列DP

全方位木DP

木のすべての頂点について, その頂点を根としたときの木DPを高速に行う.

桁DP

[桁][未満フラグ]を持ちながら行うDP

bitDP

集合を情報として持ちながら行うDP.
制約で分かる

箱根駅伝DP

条件を満たす順列を数え上げる問題で「どこまで見たか」,「割り当ててないものの数」とかをもってDPするやつ

挿入DP

箱根駅伝DPと同様に順列についての問題でよく使う手法.

区間DP

dp[l][r]という風に区間の端をもってDP

bitsetによる定数倍高速化

ナップサックDPなどはbitsetによって計算量が{\frac{1}{64}}くらい落ちる

経路復元

最短経路の復元はゴールから移動コスト分で戻れる部分にさかのぼっていけばいい.

式変形

条件式や求めたい式を変形することで簡単になることがある.

要素が多いときの{k}番目の要素

素数が非常に多いときに{k}番目の値を求めるには, 数を固定して, 固定した数以下の値がk個以上あるかどうかで二分探索をする.

木の性質

木とは連結かつ閉路のない単純グラフのこと.

以下の条件は同値である.

  1. グラフ{T}は頂点数{N}の木である.
  2. {T}は連結で,辺の数が{N-1}の単純グラフである.
  3. {T}は閉路がなく,辺の数が{N-1}の単純グラフである.
  4. {T}の任意の辺は橋である.
  5. {T}の任意の二点を結ぶパスは一つである.
  6. {T}の隣接していない二点を辺で結ぶとちょうど一つの閉路ができる.


複数の木からなるグラフを森と呼ぶ.

森の頂点数, 辺数, 連結成分数の間には以下のような関係がある.

頂点数{=}辺数{+}連結成分数

XOR(排他的論理和の)性質

XORには様々な性質がある.

  1. {x\oplus x=0}
  2. {x\oplus y=y\oplus x}
  3. {x}が偶数ならば{x\oplus (x+1)=1}
  4. {x+y=x\oplus y+2×(x \rm{and} y)}
  5. {x\oplus z=y\oplus z \Leftrightarrow x=y}
  6. {x\oplus z=y\Leftrightarrow x=y\oplus z}
  7. {x\oplus y+x \, {\rm{and}} \, y=x \,{\rm{or}}\, y}

包除原理

ゼータ変換・メビウス変換・アダマール変換

集合の上位/下位の集合に対しての和をとったり, それを戻したりするのを高速にして呉れるやつ. これを利用して畳み込みとかできる.

約数系

積の和の高速化

{\sum^{n}_{i=1}\sum^{m}_{j=1} (a_i×b_j)=(\sum^{n}_{i=1}a_i)(\sum^{m}_{j=1}b_j)}

DAGの最長路

左右からの累積演算による高速化

リストのある要素を除いた場合のリストの要素の総和は左右から累積和をもっておくことで高速に計算できる.
ただし和などの逆元が存在するものに関しては左右から取る必要はないが, gcdやminなど逆元が存在しない演算はこの高速化が有効である.
また,{\log}がついてしまうがセグメントツリーで脳死実装も可能

区間に対する演算

ある区間に対して演算(和など)を行うときには, 隣り合う要素の差を見ると区間の端に対しての操作のみ行えばよいことになるので高速化できることがある.

操作終了時点の状態を考える

ゲームやある操作を繰り返す問題では終了時点(行動不能時点)での状態はどのようになっているかを考えると特徴が見えてくることがある.

形式的冪級数

組み合わせを含めた様々な問題を機械的に解けるので強そう.

参考

ダブリング

1つ次のもの(状態)が簡単に求められるとき{K}つ先のものを高速に求める手法

不変量に注目する

ある操作を行うとき,操作前と操作後で変わらないものを見ると分かりやすく言い換えることができることがある.

Mo's algorithm

区間に関するオフラインクエリをいい感じに処理するやつ解説あり

期待値の線形性

ProjectSelectionProblem

選択にコストがあり,2つの選択の間にもコスト(制約)がある場合にうまくグラフを作ることで最小カットに帰着される.

その他

ABC201 E - Xor Distances

公式解説と同じになってしまいましたが,せっかく書いたので公開します.

問題はこちら

問題概要

{N}頂点の木の任意の{2}頂点{1\leq i < j\leq N}について{dist(i,j)}の総和を求めよ.ただし,{dist(i,j)}とは{i}から{j}への最短パスに含まれる辺全ての重み{w}のXORと定める.

{2\leq N\leq 2×10^5\\
0\leq w_{i,j} < 2^{60}}

解説

もちろん{dist(i,j)}をいちいち計算していたら{O(N^2)}かかるので間に合わない.

XORは{2}進法で桁ごとの演算であるので,ここでも桁ごとに考える.下から{k}桁目のみについて考えると,すべての辺の重みが{0}{1}である木になり,この問題の答えを{ans_k}とすると元の問題の答えは{\displaystyle\sum_{k=1}^{60}ans_k×2^{k-1}}となる.

入力例{1}での例:{1=01_{(2)}}{3=11_{(2)}}

f:id:kanpurin:20210515223509p:plain:w500

以下,すべての辺の重みが{0}{1}である木についての問題を解く.
この木をある頂点{r}を根とする根付き木として見る.各頂点{i}について{dist(r,i)}をDFSなどを用いて計算すると,任意の{i,j}について{dist(i,j)=dist(r,i)\oplus dist(r,j)}となる({\oplus}はXOR).{dist(i,j)}{0}{1}であるので,{dist(i,j)}{1}となるような{(i,j)}の数を数えられればいい.つまり,{dist(r,i)\neq dist(r,j)}となる{(i,j)}の数が知りたい.これは,{dist(r,i)=0}となる{i}の数と{dist(r,i)=1}となる{i}の数を持ちながらDFSすればよい.

提出プログラム

https://atcoder.jp/contests/abc201/submissions/22635722

感想

XORは桁ごとに考えるのは典型です.

ABC154 F - Many Many Paths

形式的冪級数を用いた解法です.

問題はこちら

問題概要

{2}次元グリッド上で{(0,0)}から{(r,c)}までの最短経路の個数を{f(r,c)}とする.{\displaystyle\sum_{r=r_1}^{r_2}\sum_{c=c_1}^{c_2}f(r,c)}を求めよ.

{1\leq r_1\leq r_2 \leq 10^6\\
1\leq c_1\leq c_2 \leq 10^6}

解説

{\displaystyle f(r,c)=\binom{r+c}{r}}である.これは高校数学なので,分からない場合は復習が必要.

{2}次元累積和の典型みたいに考えると{\displaystyle F(r,c)=\sum_{i=0}^{r}\sum_{j=0}^{c}f(i,j)}として{F(r_2,c_2)-F(r_1-1,c_2)-F(r_2,c_1-1)+F(r_1-1,c_1-1)}が答えなので{F(r,c)}を求める.

{\displaystyle F(r,c)=\sum_{i=0}^{r}\sum_{j=0}^{c}f(i,j)\\
=\displaystyle \sum_{i=0}^{r}\sum_{j=0}^{c}\binom{i+j}{i}}

{\displaystyle \sum_{j=0}^{c}\binom{i+j}{i}}{\displaystyle \sum_{j=0}^{\infty}\binom{i+j}{i}x^j}{0}から{c}次までの係数の和なので
{\displaystyle \sum_{j=0}^{c}\binom{i+j}{i}\\
=\displaystyle[x^c]\frac{\displaystyle\sum_{j=0}^{\infty}\binom{i+j}{i}x^j}{1-x}\\
=\displaystyle [x^c]\frac{1}{(1-x)^{i+2}}\\
=\displaystyle [x^c]\sum_{j=0}^{\infty}\binom{i+j+1}{i+1}x^j\\
=\displaystyle \binom{i+c+1}{i+1}}

よって,{\displaystyle F(r,c)=\sum_{i=0}^{r}\binom{i+c+1}{i+1}}
同様にして
{\displaystyle \sum_{i=0}^{r}\binom{i+c+1}{i+1}\\
=\displaystyle [x^r]\frac{\displaystyle\sum_{i=0}^{\infty}\binom{i+c+1}{i+1}x^i}{1-x}\\
=\displaystyle [x^{r+1}]\frac{\displaystyle\sum_{i=0}^{\infty}\binom{i+c+1}{i+1}x^{i+1}}{1-x}\\
=\displaystyle [x^{r+1}]\frac{1}{(1-x)^{c+2}}-\frac{1}{1-x}\\
=\displaystyle [x^{r+1}]\sum_{i=0}^{\infty}\binom{i+c+1}{i}x^i-\sum_{i=0}^{\infty}x^i\\
=\displaystyle\binom{r+c+2}{r+1}-1}

となり解ける.
{\displaystyle \sum_{j=0}^{c}\binom{i+j}{i}=[x^c]\frac{\displaystyle\sum_{j=0}^{\infty}\binom{i+j}{i}x^j}{1-x}}の変形が一番難しいのでここさえわかればいける.

{\displaystyle\frac{1}{(1-x)^{n+1}}=\sum_{i=0}^{\infty}\binom{n+i}{i}x^i}さえ知ってればすぐ思いつく.

提出プログラム

https://atcoder.jp/contests/abc154/submissions/22540407

感想

もっといい変形がありそう.

ABC200 D - Happy Birthday! 2

問題はこちら

問題概要

{N}個の正整数からなる数列{A}が与えられる.{1\leq B_i < B_{i+1}\leq N}{1\leq C_i < C_{i+1}\leq N}を満たす異なる数列{B,C}であって{\sum_{i=1}^{|B|}A_{B_i}\equiv \sum_{i=1}^{|C|}A_{C_i} \mod 200}を満たすものが存在するか判定し,存在するならば{1}つ出力せよ.

{2\leq N \leq 200\\
1\leq A_i\leq 10^9}

解説

{A}の要素を「{B}に振り分ける」,「{C}に振り分ける」,「どちらにも振り分ける」とすればいけそう.{\sum B-\sum C\mod 200}を管理するDPをすればいい.ただし,{3}つの振り分け方のうち少なくとも{2}つを行う必要がある.

結局,持つべき状態は「{A}の何番目を見てるか」「{\sum B-\sum C\mod 200}」「{3}つの振り分け方のどれを使用したか」.

経路復元も頑張ってする.経路復元の例

計算量は{M}をmodとして{O(NM)}

提出プログラム

https://atcoder.jp/contests/abc200/submissions/22448830

感想

Dにしてはむずい.デバッグめんどい.鳩ノ巣原理あたまいい.

ABC200 E - Patisserie ABC 2

問題はこちら

問題概要

全ての{1\leq i,j,k\leq N}の組{(i,j,k)}を以下のルールでソートしたときの{K}番目の値を求めよ.

上の方が優先度が高い.

  • {i+j+k}の昇順.
  • {i}の昇順.
  • {j}の昇順.

{2\leq N \leq 10^6\\
1\leq K\leq N^3}

解説

さすがに全部列挙するのは無理.

{i+j+k}の昇順に並んでいるので,全体は以下の図のようになっている.

f:id:kanpurin:20210509015852p:plain:w400

{i+j+k \leq L}となる{(i,j,k)}の数を{C_L}とする.{C_L}{K}以上となるような最小の{L}{K}番目の{(i,j,k)}{i+j+k}となる.
{f=(x+x^2+\cdots +x^N)}として,{\displaystyle C_L=[x^L]\frac{f^3}{1-x}}

{L}が求まったので,{i+j+k=L}となるものの中で{K-C_{L-1}}番目のものが答えになる.

{\downarrow}

同じように{i+j+k=L}かつ{i\leq B}となるような,{(i,j,k)}の数{D_B}を求める.上の{f}を用いると,{\displaystyle D_B=[x^{L-1}]\frac{f^2}{1-x}(1-x^B)}{D_B}{K-C_{L-1}}以上となるような最小の{B}{K}番目の{(i,j,k)}{i}となる.

{B}が求まったので,{i+j+k=L}かつ{i=B}となるものの中で{K-C_{L-1}-D_{B-1}}番目のものが答えになる.

{C_x}および{D_x}は単調なので二分探索を行うと{L,B}{O(\log N)}で求められる.

{C_x}および{D_x}は形式的冪級数で求めたが,組合せ的考えても多分解ける(形式的冪級数だと脳死で式変形するだけだから使った).

追記
包除原理で{O(1)}でいける.{N < i}の場合とかを引いていく感じのやつ.

形式的冪級数

{\displaystyle C_L=[x^L]\frac{f^3}{1-x}}を求める.

{\displaystyle C_L=[x^L]\frac{f^3}{1-x}\\
\displaystyle =[x^{L-3}]\frac{(1-x^N)^3}{(1-x)^4}\\
\displaystyle =[x^{L-3}]\sum_{i=0}^{\infty}\binom{i+3}{3}x^i(-x^{3N}+3x^{2N}-3x^N+1)}

よって,以下の提出プログラムのように計算すれば{O(1)}で求められる.

提出プログラム

https://atcoder.jp/contests/abc200/submissions/22446038 {O(\log N)}

感想

むずい

ABC155 F - Perils in Parallel

問題はこちら

問題概要

爆弾が{N}個あり,{i}番目の爆弾は座標{A_i}にあって{B_i=0}のときオフ,{B_i=1}のときオンになっている.{M}本のコードがあり,{j}番目のコードを切ると,座標が{L_j}以上{R_j}以下のすべての爆弾の電源のオン・オフが切り替わる.切るコードをうまく選ぶことですべての爆弾の電源をオフにすることができるか判定し,できるならばそのコードの組合せを一つ出力せよ.

{2\leq N \leq 10^5\\
1\leq A_i\leq 10^9\\
B_i\in \{0,1\}\\
1\leq M\leq 2×10^5\\
1\leq L_j\leq R_j\leq 10^9}

解説

公式解説が急にグラフを作り出してるので,自然な流れ重視で説明します.公式解説の前半に書かれてる処理はすでに行っているものとします.

隣り合う爆弾の状態のXOR(状態が違うなら{1},同じなら{0})を考える.{[l,r]}番目の爆弾を切り替えるとき,{l-1}番目と{l}番目の爆弾の状態のXOR(これを{X_{l-1}}とします),{r}番目と{r+1}番目の爆弾の状態のXOR({X_{r}})のみが切り替わります.便宜上{0}番目と{N+1}番目の状態{0}の爆弾があるとします.このように考えることで,区間を変更し{0}にする問題が2点({X_{l-1},X_r})を変更し{X_0}から{X_N}{0}にする問題になりました.

入力例{1}での例

f:id:kanpurin:20210503224214p:plain:w400

ここで上図を見ると,{X_2}を変更できるのは緑のコードだけです.{X_2=1}であることから緑のコードは必ず使うことになります.緑のコードを使うと次は{X_1}を変更できるのが青のコードだけになります.このとき{X_1=0}なので青のコードは使いません.このようにして変更できるコードが{1}つだけの{X_i}がある限り決めていけばいいです.

f:id:kanpurin:20210503233540p:plain:w300

この方法では上図の場合で出来なくなりますが,ある{1}つのコードは他のコードの組合せで表されるので適当なコードを消してもいいことがわかります(例えば赤のコードを使うのと青と緑のコードを使うのは同じこと).

このようにして使うコードを決めた後,すべての{X_i}{0}になってればOK.

これでも解けますが,もう少し言い換えるとある{1}つのコードは他のコードの組合せで表されるというのは{(X_{l-1},X_r)}の辺を張ったグラフ上で閉路を意味します.上の解法は閉路がある限りその閉路から辺を取り除くという操作に対応します.

提出プログラム

感想

隣り合う要素の差を見るのは典型なので,その発想が出なかった人は覚えておきましょう.

ZONeエナジープログラミングコンテスト C - MAD TEAM

問題はこちら

問題概要

{N}人に{A,B,C,D,E}{5}つの能力値がある.この中から3人選んだときの{\min{(\max{A},\max{B},\max{C},\max{D},\max{E})}}の最大値を求めよ.

{2\leq N \leq 3000\\
1\leq A_i,B_i,C_i,D_i,E_i\leq 10^9}

解説

最初に思いつくのは{3}人の選び方の全探索.これは{O(N^3)}なので間に合わない.

{2}人決めたときにもう{1}人を高速に決められたら解けそう.

決めた{2}人を{i,j}とすると,今のチーム総合力({S})は
{S=\min{(\max{(A_i,A_j)},\max{(B_i,B_j)},\max{(C_i,C_j)},\max{(D_i,D_j)},\max{(E_i,E_j)})}}であり,{\max{(X_i,X_j)}=S}となる{X\in\{A,B,C,D,E\}}が存在する.

(説明分かりづらいので追記します 05/02/05:00頃)
この{X}が総合力のネックになっているため,あと一人追加して{\max X}をできるだけ大きくしたい.({X}以外が大きい人をチームに入れても{X}が小さいままなので無駄)
(ここまで追記)

なので,{X}が一番大きい値をもつ人を選べばよさそう.ちゃんと実装すれば{O(N^2)}

たぶんこの解法は要素が{5}つだからできるけど,{6}つ以上だとできない?(知らんけど)
(本当っぽい)


提出プログラム

https://atcoder.jp/contests/zone2021/submissions/22237266

感想

ABC199 E - Permutation

別解です.ほぼ一緒なので丁寧には書きません.

問題はこちら

問題概要

{(1,2,3,\cdots,N)}を並び替えてできる数列{A}で,以下の条件を満たすものの数を求めよ.

  • {1\leq i\leq N}を満たす全ての数列{i}について,{A_1,A_2,A_2,\cdots,A_{X_i}}の中に{Y_i}以下の数は{Z_i}個以下しか存在しない.

{2\leq N \leq 18\\
0 \leq M \leq 100\\
1\leq X_i < N\\
1\leq Y_i < N\\
0\leq Z_i < N\\}

解説

公式解説では数列を左端から決めて,使った数を状態として持つDPをしていましたが,小さい数から位置を決めていくことを考えます.DPでは数列中の既に決まった位置を持っておきます.すると遷移は

  • {dp[\emptyset]=1}
  • {dp[S]=0} (条件を満たさない時)
  • {\displaystyle dp[S]=\sum_{a\in S}dp[S\backslash \{a\}]} (条件を満たすとき)

となります.条件を満たすかを見るときは{|S|=Y_i}となる条件のみを見ればいいです.この方針だと任意の区間(位置)の条件でも解くことができるはず(たぶん).

提出プログラム

https://atcoder.jp/contests/abc199/submissions/22139163

感想

制約がbitDP