かんプリンの学習記録

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

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

競技プログラミングにおける典型知識や問題を書いていきます.
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

AlienDP

位置と操作回数をもつようなDPだと{O(N^2)}かかるが,これがある性質を満たすなら二分探索を用いて{O(N\log{N})}なるというもの.Alien Trickとも言ったりする. 参考1 参考2

bitsetによる定数倍高速化

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

経路復元

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

木の性質

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

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

  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}

包除原理

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

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

約数系

DAGの最長路

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

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

区間に対する演算

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

形式的冪級数

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

参考

ダブリング

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

不変量に注目する

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

Mo's algorithm

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

部分木はオイラーツアー

パスはhttps://codeforces.com/blog/entry/43230 rollbackできれば挿入だけでいい

期待値の線形性

ProjectSelectionProblem

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

2-SAT

充足可能性問題の特殊な場合. 複数の2択とその選択の間に不可能という関係があるような問題を解くときに使ったりする. ProjectSelectionProblemのコストない版

Subset Convolution

全ての{S}に対して,{h(S)=\sum_{T\subseteq S}f(T)g(S\backslash T)}{O(N^{2}2^{N})}で計算する.

逆元の前計算ができない二項係数

mod3とかmod合成数とかではフェルマーの小定理を用いた階乗の逆元の前計算による二項係数の計算ができない.その場合,modの素因数ごとに数をカウントしていく. 例としてmod10の場合を考える.{\frac{100\cdot 99\cdot 98\cdot 97\cdot 96}{5\cdot 4\cdot 3\cdot 2\cdot 1}}の分子は{(2,5)}{(8,2)}回割り切れ,分母は{(3,1)}回割り切れる.すべての素因数で(分子)>(分母)となっている場合,mod10で0になる.そうでない場合普通に計算する.

他にも,Lucasの定理を使えば実装が簡単になる.

Slope Trick

https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8

Weighted-Union Heuristic

マージテクとも呼ばれるやつ.データを何回もマージするときに小さい方を大きい方に入れると各要素{O(\log n)}回の移動で済む.

その他

ARC126 C - Maximize GCD

問題はこちら

問題概要

長さ{N}の数列{A}が与えられる.この数列の要素を一つ選び{1}を加えるという操作を{K}回まで行うことができるとき,{A}の全要素のgcdの最大値を求めよ.

{2\leq N\leq 3×10^5\\
1\leq K\leq 10^{18}\\
1\leq A_i\leq 3×10^5}

解説

{G=\gcd{(A_1,A_2,\cdots ,A_N)}}となるための最小操作回数が{K}以下であるかが分かればいい(そのような{G}で最大のものが答え).最大のものさえ見つけられればいいので「{G=\gcd{(A_1,A_2,\cdots ,A_N)}}」を「{G|\gcd{(A_1,A_2,\cdots ,A_N)}}」としてもいい.

{G|\gcd{(A_1,A_2,\cdots ,A_N)}\Leftrightarrow G|A_1\land G|A_2\land\cdots \land G|A_N}
であるから,各{i}について{G|A_i}となるための最小操作回数が分かればいい.これは{\lceil A_i/G \rceil\times G-A_i}であるので{\sum_{i=1}^{N}\lceil A_i/G \rceil\times G-A_i}が操作回数となる.これをすべての{G}について求めればいいが,{G}の取り得る範囲が大きいので間に合わない.

{A_{\max} < G}のとき,{\lceil A_i/G \rceil=1}であるので{\sum_{i=1}^{N}G-A_i\leq K \Leftrightarrow G\leq (K+\sum_{i=1}^{N}A_i)/N}より{G=\lfloor  (K+\sum_{i=1}^{N}A_i)/N\rfloor}が答え.ただし{A_{\max}\leq\lfloor  (K+\sum_{i=1}^{N}A_i)/N\rfloor}でないなら{A_{\max}\leq G}の範囲に答えはない.

{A_{\max}\geq G}のとき,{\lceil A_i/G \rceil}が同じ値である{A_i}の数を計算すればいい.{\lceil A_i/G \rceil = k}であるのは{(k-1)G < A_i\leq kG}の範囲にあるものである.これは累積和を用いれば1つの範囲につき{O(1)}で求められる.
{\sum_{G=1}^{A_{\max}}\lceil A_{\max}/G \rceil = O(A_{\max}\log{A_{\max}})}であるので全体で{O(N+A_{\max}\log{A_{\max}})}となる.

提出プログラム

https://atcoder.jp/contests/arc126/submissions/26012713

感想

{A_{\max} < G}のとき簡単に分かることさえ気づけばすぐ.

グリッドの最短経路の数え上げまとめ

グリッドの最短経路の数え上げの例を解説していきます.よくある書き込み(動的計画法)による解法は扱いません.

目次

最短経路の数え上げとは

最短経路の数え上げは,以下のようなグリッド上で左下から右上への最短経路の数を数え上げる問題です.最短経路の例として以下の赤,青の経路があります.

f:id:kanpurin:20210902112107p:plain:w300

一般的な最短経路

例として,以下の縦{4}区画,横{6}区画のグリッド上の最短経路を考えます.

f:id:kanpurin:20210902112152p:plain:w300

どの最短経路でも上方向に{4}回,右方向に{6}回移動する必要があります.最短経路の数は「{\uparrow}{4}つ,「{\rightarrow}{6}つを並べる方法の数に等しいです.例えば上の赤の経路は{(\rightarrow,\uparrow,\rightarrow,\rightarrow,\uparrow,\rightarrow,\uparrow,\rightarrow,\rightarrow,\uparrow)}に対応しています.これは同じものを含む順列の数え上げに等しく,{\displaystyle\binom{10}{4}=210}が答えとなります.ここで,{\displaystyle\binom{n}{r}}とは{\displaystyle\frac{n!}{r!(n-r)!}}のことです.

ある点を通る最短経路

グリッド上の最短経路のうち,ある点{P}を通るようなものの数は,(左下から点{P}までの最短経路の数)×(点{P}から右上までの最短経路の数)となります.

例えば以下のグリッドの左下から右上への最短経路のうち,赤の点を通るよううなものの数は,{\displaystyle\binom{6}{3}\binom{4}{1}=80}です.

f:id:kanpurin:20210902112830p:plain:w300

{P}が辺上にあっても数え方は同じで,その辺の両端の点を通るような経路の数を数えればよいです.以下の例で赤の点を通るような物の数は,{\displaystyle\binom{5}{2}\binom{4}{2}=60}です.

f:id:kanpurin:20210902112930p:plain:w300

ある長方形領域を通らない最短経路

以下のようにグリッド上に左上から右下にかけてのオレンジの破線上の点を考えます.このグリッド上の左下から右上への最短経路は必ずオレンジの点を通ります.さらに,異なる2つのオレンジの点を通る最短経路は存在しないため,各オレンジの点を通る最短経路数の総和は,全体の最短経路数と一致します.

f:id:kanpurin:20210902113449p:plain:w300

以下のようなグリッド上の長方形領域が通れないときの最短経路を数えます.先ほどのように直線を引き,その直線上の各点を通る最短経路数を足せばよいです.

f:id:kanpurin:20210902120307p:plain:w300

また,このままでは上から2番目のオレンジの点は数えにくいので以下のように直線をずらしてみます.

f:id:kanpurin:20210902120702p:plain:w300

「異なる2つのオレンジの点を通る最短経路は存在しない」,「各点を通る最短経路数の総和は,全体の最短経路数と一致する」を満たすため,このように変形しても問題ないです.

この場合の最短経路数は{\displaystyle\binom{4}{4}\binom{6}{0}+\binom{4}{3}\binom{6}{1}+\binom{5}{1}\binom{5}{3}+\binom{5}{0}\binom{5}{4}=80}となります.

一般に,長方形領域が通れない場合,その長方形の頂点から引いた直線を引くとこのように求めることができます.

ある直線を通らない最短経路

以下のようなグリッド上の直線上の点を通らない最短経路の数を数えます.

f:id:kanpurin:20210902164458p:plain:w300

このグリッドを直線で折り返すと以下のようになります.数えたいものは黒点から赤点までオレンジの点を通らずに行く最短経路数です.これは「黒点から赤点までの最短経路数」から「黒点から赤点まででオレンジの点を通るような最短経路数」を引けば良いです.ここで,「黒点から赤点まででオレンジの点を通るような最短経路数」というのは「黒点から青点までの最短経路数」と等しいです.なぜならば,「黒点から青点までの最短経路」は必ず1度はオレンジの点を通り,そのうち初めに通ったオレンジの点以降の経路を直線で折り返すと「黒点から赤点まででオレンジの点を通るような最短経路」と1対1対応するからです.

f:id:kanpurin:20210902165329p:plain:w300

例えば以下の赤の経路と青の経路が対応します.

f:id:kanpurin:20210902171032p:plain:w300

この場合の最短経路数は{\displaystyle\binom{10}{4}-\binom{10}{3}=90}となります.

一般に,縦{N}区画,横{M}区画のグリッドの上から{K}区画にかけて以下のように直線がある場合,その直線上の点を通らない最短経路の数は,{\displaystyle\binom{N+M}{N}-\binom{N+M}{K}}となります.

f:id:kanpurin:20210909144424p:plain:w350

特に,{M=N, K=N-1}の場合,この値はカタラン数と呼ばれ,{\displaystyle C_N=\binom{2N}{N}-\binom{2N}{N-1}=\frac{1}{N+1}\binom{2N}{N}}と表されます.

また,下図のように複数の直線があっても複数回折り返すことで同じように解くことができます.

f:id:kanpurin:20210911135735p:plain:w300

(黒{\rightarrow}赤){-}(黒{\rightarrow}青){-}(黒{\rightarrow}黄){+}(黒{\rightarrow}緑)が答えとなります.ただし,直線の位置によっては多くの回数折り返す必要がある場合があります.

f:id:kanpurin:20210911141101p:plain:w400

対角線上を{K}回通る最短経路

縦横{N}区画のグリッドの左下から右上への最短経路のうち,グリッドの対角線上の(始点と終点を除く)点ををちょうど{K}回通るものの数を数えます.例えば以下の最短経路は対角線上の点を{3}回通っています.

f:id:kanpurin:20210910142906p:plain:w300

対角線上の点のうち通るものを決めると,点と点の間は「対角線上の(始点と終点を除く)点を通らない最短経路数を求めよ.」という複数の部分問題に分割できます.下図のうち,オレンジの点が通る点,青の枠が部分問題になっています.

f:id:kanpurin:20210910163136p:plain:w300

「縦横{t}区画のグリッドの左下から右上への最短経路のうち,グリッドの対角線上の(始点と終点を除く)点を通らないものの数を求めよ.」という部分問題の解を求めます.これは簡単で,下図において,左下の赤(青)点から右上の赤(青)点まで対角線(オレンジ)を通らない最短経路の数を求めればよいです.ある直線を通らない最短経路で紹介したカタラン数を用いて{2C_{t-1}}と表すことができます.

f:id:kanpurin:20210910164656p:plain:w300

あとは,サイズの和が{N}になるような部分問題の積の和を求めればよいです(畳み込み).

{\displaystyle\sum_{t_1,t_2,\cdots ,t_{K+1}=N}(2C_{t_1-1})(2C_{t_2-1})\cdots (2C_{t_{K+1}-1})\\
=\displaystyle 2^{K+1}\sum_{t_1,t_2,\cdots ,t_{K+1}=N}C_{t_1-1}C_{t_2-1}\cdots C_{t_{K+1}-1}}

{\displaystyle\sum_{t_1,t_2,\cdots ,t_{K+1}=N}C_{t_1-1}C_{t_2-1}\cdots C_{t_{K+1}-1}}はカタラン数の畳み込みになっていて,この値は

{\displaystyle\binom{2N-K-2}{N-1}-\binom{2N-K-2}{N}=\frac{K+1}{2N-K-1}\binom{2N-K-1}{N}}

であることが知られています.*1*2

したがって,{\displaystyle \frac{2^{K+1}(K+1)}{2N-K-1}\binom{2N-K-1}{N}}となります.

対角線の下側しか通れないという制約が付いても,部分問題の解が{C_{t-1}}となるだけなので{\displaystyle\frac{K+1}{2N-K-1}\binom{2N-K-1}{N}}です.

この制約が付いた数え上げ問題ははカタラン数の畳み込みに帰着させる方法の他にも,下図のある直線を通らない最短経路と一対一の対応をさせることでも求めることができます.ただし,「ある直線を通らない最短経路」で説明したような直感的で簡潔な証明が分からないので省略します.

f:id:kanpurin:20210910191041p:plain:w400

複数の最短経路数の和

複数の点間の最短経路数の和は一つずつ求めずとも簡単に求まる場合があります.ここでは,そのような例について見ていきます.

対角線上の点までの最短経路

下図のような縦横{N}区画のグリッドがあり,左下の点(黒)から対角線上の各点(オレンジ)までの最短経路数の総和を求めます.下図は{N=6}の例です.

f:id:kanpurin:20210911163608p:plain:w300

この例では,最短経路数は左上の点から順に{\displaystyle\binom{6}{0},\binom{6}{1},\binom{6}{2},\binom{6}{3},\binom{6}{4},\binom{6}{5},\binom{6}{6}}なので答えは{64}です.

一般に,二項定理より{\displaystyle (1+1)^N=\sum_{i=0}^{N}\binom{N}{i}}であるので,総和は{2^N}になります.

グリッドの端の点までの最短経路

下図のような縦{N}区画,横{M}区画のグリッドがあり,左下の点(黒)からグリッドの端の各点(オレンジ)までの最短経路数の総和を求めます.下図は{N=4,M=6}の例です.

f:id:kanpurin:20210915183338p:plain:w300

ここでグリッドの区画を右に増やします.そして各点を右の辺上に移動させます.このグリッドでの左下の点(黒)から各点(オレンジ)までの最短経路数の総和は元のグリッドでの最短経路数の総和と同じです.さらに,左下の点から右上の点(黒)への最短経路は必ずオレンジの点をただ一つ通るので,求める最短経路数の総和はこのグリッドでの左下の点から右上の点への最短経路数の総和と一致します.したがって,{\displaystyle\binom{N+M+1}{N}}が答えとなります.

f:id:kanpurin:20210915200418p:plain:w300

問題例

ABC218 F - Blocked Roads

公式解説より効率の良いアルゴリズムの説明です.

問題はこちら

問題概要

{N}頂点{M}辺の有向グラフが与えられる.各{i(1\leq i\leq M)}について,辺{i}のみ通れないときの頂点{1}から頂点{N}までの最短距離を求めよ.

{2\leq N\leq 400\\
1\leq M\leq N(N-1)}

解説

頂点{1}から頂点{N}までの最短経路を一つ求めます.明らかに,その最短経路上にない辺を消すときの答えは元のグラフの頂点{1}から頂点{N}までの最短距離と一致します.
例えば,下図のグラフにおいて,ある黒の辺を消しても赤の辺からなる最短経路が通れるままなので答えは元のグラフの最短距離になります.
最短経路に含まれる辺の数は高々{N-1}本なので,そのような辺ごとにその辺を消したグラフにおける最短距離を求めればいいです.一つの辺につきBFSで{O(N+M)}かかるので全体で{O(N(N+M))}でかかります.

f:id:kanpurin:20210913204907p:plain:w300

最短経路上のある辺{(u,v)}を消したグラフの最短距離は下図のような位置関係にある頂点{t}で「頂点{1}から頂点{t}を通って頂点{N}に行くまでの最短距離」のうち最小のものが答えとなります.

f:id:kanpurin:20210913222037p:plain:w300

このとき,{1\rightarrow L_t\rightarrow t\rightarrow R_t\rightarrow N}の順で通るとします.{L_t,R_t}{1\rightarrow L_t}{R_t\rightarrow N}は元のグラフの最短経路上の辺を通り,{L_t\rightarrow t\rightarrow R_t}は元のグラフの最短経路上の辺を通らないような頂点とします.各頂点{t}に対して{L_t,R_t}を計算しておくとこの問題は以下のような問題になります.

{O(N)}個の座標{T_i}および,{O(N)}個の区間{[L_j,R_j)}とその区間の重み{W_j}が与えられるので,各{T_i}に対して,{T_i}を含む区間の重みの最小値を求めよ.

これはSegment Treeやstd::setをを用いれば{O(N\log{N})}で解けます.

関連問題

重み変更クエリの問題https://codeforces.com/contest/1163/problem/F

ABC217 D - Cutting Woods

問題はこちら

問題概要

長さ{L}の木材がある.以下の{Q}個のクエリを処理せよ.{i}番目のクエリは{(c_i,x_i)}で与えられる.

  • {c_i=1}のとき:木材の左端から{x_i}の地点で木材を切る.
  • {c_i=2}のとき:木材の左端から{x_i}の地点を含む木材の長さを出力する.

{1\leq L\leq 10^9\\
1\leq Q\leq 2×10^5\\
c_i = 1,2\\
1\leq x_i\leq L-1}

解説

現在の木材の区間を管理します.{[0,L)}を初期状態とし,{[l,r)}の木材を{x(l < x < r)}の地点で切ると,{[l,x)}{[x,r)}の木材になります.
C++のstd::setで{0,L}および切れ目を管理することで,{x}の地点を含む木材の値が両端が取得できます.

具体的にはそれぞれのクエリで以下の操作を行います.

  • クエリ1:{x_i}をsetに入れる.
  • クエリ2:setの{x_i}以上の最小の要素{A}{x_i}以下の最大の要素{B}を取得し,{A-B}を出力する.

Pythonでの解法

C++にはstd::setというデータ構造があり,クエリ1がinsert,クエリ2がlower_boundで実現できるのですが,PythonにはSTLにsetのようなものがない(Pythonよくわかってないのでもしかしたらある?)ので公式解説にあるようにSegment Tree / Fenwick TreeやUnion-Findで解くのですが,これだと座標圧縮やその他setに比べて考えることが増えて,やるだけのC++に比べて時間がかかってしまうので,やっぱりPythonでもsetのようなものが欲しくなります.
結局,以下の操作が高速に行えるようなものが欲しいです.

  • {x}を挿入
  • {x}以上の最小要素の取得
  • {x}以下の最大要素の取得

これらの操作が行えるデータ構造としてBinaryTrieがあります.

以下の記事が分かりやすいです.BinaryTrieはXOR関連の操作も可能ですが今回は使いません.

kazuma8128.hatenablog.com

必要なものを実装すると以下の様になります.計算量は{O(Q\log\max{x})}です.

class BinaryTrie:
    def __init__(self, max_query=2*10**5, bitlen=30):
        n = max_query * bitlen
        self.nodes = [-1] * (2 * n)
        self.cnt = [0] * n
        self.id = 0
        self.bitlen = bitlen
 
    # xの挿入
    def insert(self,x):
        pt = 0
        for i in range(self.bitlen-1,-1,-1):
            y = x>>i&1
            if self.nodes[2*pt+y] == -1:
                self.id += 1
                self.nodes[2*pt+y] = self.id
            self.cnt[pt] += 1
            pt = self.nodes[2*pt+y]
        self.cnt[pt] += 1
 
    # 昇順x番目の値
    def kth_elm(self,x):
        pt, ans = 0, 0
        for i in range(self.bitlen-1,-1,-1):
            ans <<= 1
            if self.nodes[2*pt] != -1 and self.cnt[self.nodes[2*pt]] > 0:
                if self.cnt[self.nodes[2*pt]] >= x:
                    pt = self.nodes[2*pt]
                else:
                    x -= self.cnt[self.nodes[2*pt]]
                    pt = self.nodes[2*pt+1]
                    ans += 1
            else:
                pt = self.nodes[2*pt+1]
                ans += 1
        return ans

    # x以上の最小要素が昇順何番目か
    def lower_bound(self,x):
        pt, ans = 0, 1
        for i in range(self.bitlen-1,-1,-1):
            if pt == -1: break
            if x>>i&1 and self.nodes[2*pt] != -1:
                ans += self.cnt[self.nodes[2*pt]]
            pt = self.nodes[2*pt+(x>>i&1)]
        return ans
 
bt = BinaryTrie()
L,Q = map(int,input().split())
bt.insert(0)
bt.insert(L)
for _ in range(Q):
    c,x = map(int,input().split())
    if c == 1:
        bt.insert(x)
    else:
        p = bt.lower_bound(x)
        print(bt.kth_elm(p)-bt.kth_elm(p-1))

また,以下のプログラムもなぜか通る.計算量は{O(Q^2)}のはず.arrayのinsertが速いらしい(未検証).

import bisect
import array
l,q=map(int,input().split())
a=array.array('i',[0,l])
for _ in range(q):
    c,x=map(int,input().split())
    y = bisect.bisect(a,x)
    if c==1:
        a.insert(y,x)
    else:
        print(a[y]-a[y-1])

感想

データ構造ゲーなのでpython初心者にはキツかったかも.
前もって準備できるのは準備すべきなのでC++STLの有名なやつやACLにあるやつはpythonで使い方とともにメモしておいた方がいいですね.

ABC217 G - Groups

問題はこちら

問題概要

{1}以上{N}以下の{k}について以下の問題を解け.

  • {1}から{N}まで番号が付いた人を空でない{k}個の集合に分ける.{M}で割った余りが等しい人は同じ集合に含まれないような分け方の総数を求めよ.

{2\leq N\leq 5000\\
2\leq M\leq N}

解説

包除原理

集合も区別して考え,最後に{k!}で割ります.

{M}で割った余りが{i}であるような番号の人を{k}個の集合に分けます.このとき,1つの集合には高々1人含まれる(1人もいない集合があってもいい).この分け方の数は,{n_i}{M}で割った余りが{i}であるような番号の人の数として,{{}_{k}{\rm{P}}_{n_i}}となります.

すべての{0\leq i < M}に対してこの値の積を求めると,満たすべき条件のうち「集合は空でない」以外の条件を満たすような分け方の数が分かります.以下,「分け方」を「集合は空でない」以外の条件を満たすような分け方のこととします.

後は包除原理で解けます.

{X_i}を「{i}番目の集合が空でないような分け方」の集合とします.
{|X_1\cap X_2\cap\cdots\cap X_k|}が求めるものです.

{|X_1\cap X_2\cap\cdots\cap X_k|\\
=\left\lvert\overline{\overline{X_1}\cup \overline{X_2}\cup\cdots\cup \overline{X_k}}\right\rvert\\
=\displaystyle\sum_{T\subseteq \{1,2,\cdots ,k\}}(-1)^{|T|}\left|\bigcap_{i\in T}\overline{X_i}\right|}

{|T|}が同じなら{\displaystyle\left|\bigcap_{i\in T}\overline{X_i}\right|}の値は同じであり,{|T|=m}のとき,{\displaystyle\left|\bigcap_{i\in T}\overline{X_i}\right|=\prod_{i=0}^{M-1}{}_{k-m}{\rm{P}}_{n_i}}であるので

{=\displaystyle\sum_{m=0}^{k}{}_{k}{\rm{C}}_{m}(-1)^{m}\prod_{i=0}^{M-1}{}_{k-m}{\rm{P}}_{n_i}}となります.

{k!}で割ったものが答えとなります.{\displaystyle\prod_{i=0}^{M-1}{}_{k-m}{\rm{P}}_{n_i}}を前計算しておくと{O(N^2)}

qiita.com

さらなる高速化

{\displaystyle\frac{1}{k!}\sum_{m=0}^{k}{}_{k}{\rm{C}}_{m}(-1)^{m}\prod_{i=0}^{M-1}{}_{k-m}{\rm{P}}_{n_i}\\
=\displaystyle\frac{1}{k!}\sum_{m=0}^{k}\frac{k!}{m!(k-m)!}(-1)^{m}\prod_{i=0}^{M-1}\frac{(k-m)!}{(k-m-n_i)!}\\
=\displaystyle\sum_{m=0}^{k}\frac{(-1)^{m}(k-m)!^{M}}{m!(k-m)!}\prod_{i=0}^{M-1}\frac{1}{(k-m-n_i)!}}
{\displaystyle f(x)=\prod_{i=0}^{M-1}\frac{1}{(x-n_i)!}}とすると
{=\displaystyle\sum_{m=0}^{k}\frac{(-1)^{m}(k-m)!^{M-1}}{m!}f(k-m)\\
=\displaystyle\sum_{s+t=k}\left(s!^{M-1}f(s)\right)\left(\frac{(-1)^t}{t!}\right)}

となります.
{
n_i=
\left\{
\begin{array}{ll}
\left\lfloor\frac{N}{M}\right\rfloor +1 & (1\leq i\leq N\% M) \\
\left\lfloor\frac{N}{M}\right\rfloor & (otherwise)
\end{array}
\right.
}
であるので,{f(x)}{O(\log{M})}で求まります.
したがって,高速な畳み込みを行えば{O(N\log{N})}で解けます.

提出プログラム

https://atcoder.jp/contests/abc217/submissions/25589928 {O(N^2)}
https://atcoder.jp/contests/abc217/submissions/25616429 {O(N\log{N})}

感想

ぱっと見包除原理だった.

ABC216 D - Pair of Balls

問題はこちら

問題概要

{2N}個のボールがあり,各ボールには{1}から{N}以下の整数が書かれたボールはちょうど2個ずつ存在する.{M}本の筒があり,各筒にはボールが{k_i}個入っている.異なる{2}本の筒の一番上にあるボールの色が同じ場合それらを取り出せる.すべての筒を空にできるか判定せよ.

{1\leq N\leq 2×10^5\\
2\leq M\leq 2×10^5\\
1\leq k_i\\
1\leq a_{i,j}\leq N\\
\sum_{i=1}^{M}=2N}

解説

頂点{a_{i,j}}から頂点{a_{i,j+1}}に辺を張ったグラフを考えます.
このグラフに閉路があるなら答えはNo. 閉路がなければYesとなります.
なぜならば,{a_{i,j+1}}を出すためには{a_{i,j}}を出す必要があり,グラフに閉路があるということはデッドロックのような状況になっているということなのでその頂点を取り出すことはできないからです.逆に,閉路がなければトポロジカル順に取り出すことができます.

提出プログラム

https://atcoder.jp/contests/abc216/submissions/25449130
https://atcoder.jp/contests/abc216/submissions/25451462 ACL

感想

ABC215 D - Coprime 2

問題はこちら

問題概要

長さ{N}の正整数列{A}が与えられる.以下の条件を満たす{1\leq k\leq M}をすべて求めよ.

  • すべての{1\leq i\leq N}を満たす整数{i}について,{\gcd(A_i,k)=1}である.

{1\leq N,M\leq 10^5\\
1\leq A_i\leq 10^5}

解説1

{\gcd(A_i,k)=1}となるのは,{k}{A_i}の任意の素因数を持たないことと同じです.{A}のすべての素因数を求めて,その素因数を持たない{1}以上{M}以下の整数を求められれば良いです.
エラトステネスの篩を用いて,{1}以上{\max A}以下の素数{p}であって,{p}を素因数に持つような{A_i}が存在するようなものを{O(\max A\log\log\max A)}で求めます.この素数{p}に対して,{1}以上{M}以下であって{p}の倍数であるような数を,同じくエラトステネスの篩の要領で消していけば残った数が答えとなります.全体の計算量は{O(N+\max A\log\log\max A+M\log\log M)}となります.

kanpurin.hatenablog.com

N,M = map(int,input().split())
A = list(map(int,input().split()))
maxA = max(max(A),M)

k = [True] * (maxA+1) # iが条件を満たすkか(iが使えるか)
isprime = [True] * (maxA+1) # iが素数か
prime = [] # Aの素因数(使えない素数)
# Aの要素は使えない
for a in A: 
    k[a] = False
# エラトステネスの篩
for i in range(2,maxA+1):
    if not isprime[i]:
        continue
    for j in range(i*2,maxA+1,i):
        isprime[j] = False
        # iはjの素因数
        # jがAの要素ならiは使えない素数
        k[i] = k[i] and k[j]
    if not k[i]:
        prime.append(i)
# 使えない素数pに対して, pの倍数を使えなくする
for p in prime:
    for j in range(p*2,M+1,p):
        k[j] = k[j] and k[p]
# 使える数をansに入れる
ans = [1]
for i in range(2,M+1):
    if k[i]:
        ans.append(i)
# 出力
print(len(ans))
for i in ans:
    print(i)

解説2

線形篩を用いることで{O(N+M+\max A)}でも解けます.
{A_i}の素因数{p}を求め,{p}の倍数を消す,という流れは同じです.

{\downarrow}詳しくは実装や以下の記事を参照{\downarrow}

kanpurin.hatenablog.com

計算量は線形篩の方がいいですが,エラトステネスの篩の方が定数倍が軽く実速度は高速です.

提出プログラム

後でpython版も載せます.
載せました.

https://atcoder.jp/contests/abc215/submissions/25244813 C++ エラトステネスの篩
https://atcoder.jp/contests/abc215/submissions/25253885 C++ 線形篩
https://atcoder.jp/contests/abc215/submissions/25247004 python エラトステネスの篩

感想

公式解説の不穏な計算量でも通るんだ.