2021-08-15

ABC214 H - Collecting

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 頂点 ${M}$ 辺の有向グラフがあり， ${K}$ 人が ${1}$ 人ずつ頂点 ${1}$ から辺を辿って任意の回数繰り返す．人が ${1}$ 人以上通った頂点 ${v}$ の ${X_v}$ の値の総和の最大値を求めよ．

${2\leq N\leq 2×10^5\\ 1\leq M\leq 2×10^5\\ 1\leq K\leq 10\\ 1\leq X_i\leq 10^9}$

解説

ある強連結成分を通るときはその強連結成分の全頂点を通るべきなので強連結成分分解してDAGにする．以降はDAGで解く．
各頂点から新たに作った頂点 ${T}$ に有向辺を張る．このグラフにおける頂点 ${1}$ から頂点 ${T}$ への ${K}$ 本のパスに含まれる頂点の ${X_v}$ の和の最大値が答え．
問題が最小費用流っぽい．最大化だったり，頂点にコストがあったりするが実は最小費用流のアルゴリズムで解ける．

最大化を最小化にするために ${X_i}$ を ${-X_i}$ にする．負のコストをもつ辺ができるが，これは後で処理する．

頂点のコストは，頂点毎に以下のように頂点を2つ作る．この頂点を通るフローは必ず下図の2頂点の間の辺を通るのでこのように辺のコストに変換することができる．

f:id:kanpurin:20210815100618p:plain:w300

複数回頂点を通っても最初の ${1}$ 回しかコストが発生しない．これは上記の2頂点間に「容量 ${1}$ ，コスト ${-X_v}$ の辺」と「容量 ${\infty}$ (実装では ${K-1}$ でいい)，コスト ${0}$ の辺」を張ることで実現できる．優先的にコスト ${-X_v}$ の辺から使われるのでこの方法でよい．

こうしてできたグラフの頂点 ${1}$ から頂点 ${T}$ へ流量 ${K}$ を流すときの最小コストが答えとなるが，負のコストをもつ辺があるので非負コストの辺のみからなるグラフの最小費用流に言い換える必要がある．

snuke.hatenablog.com

辺に適切に定数を足す．
あらかじめ負のコストを持つ辺に最大までフローを流す．
最短距離を求めるアルゴリズムを用いてポテンシャルを初期化する(アリ本に説明アリ)．

1は公式解説の方法であり，問題ごとに考える必要がある(ライブラリ化難しそう？)．2は今回の問題だと全頂点に負のコストがあるので流すフローが多くなり間に合わない．3は負のコストがあるグラフの最短距離を求めるアルゴリズムであるBellman-Fordを用いると ${O(NM)}$ かかり間に合わないが，グラフがDAGであることを利用してトポロジカル順にDPすることで最短距離が ${O(N+M)}$ で求められる．

提出プログラム

https://atcoder.jp/contests/abc214/submissions/25067496

感想

Gより典型度高い．
最小費用流の負辺除去は1の方法でやろうとするとこんがらがる．

2021-08-14

ABC214 C - Distribution

ABC データ構造典型競技プログラミング解説

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 人が円周上に並んでいる． ${i}$ 番目の人は時刻 ${t}$ に宝石をもらうと ${S_i}$ 時間後にその宝石を ${(i+1)}$ 番目の人に渡す．ただし， ${(N+1)=1}$ とする．また，高橋君は時刻 ${T_i}$ に ${i}$ 番目の人に宝石を渡す．すべての ${i}$ について， ${i}$ 番目の人が初めて宝石をもらう時刻を求めよ．

${1\leq N\leq 2×10^5\\ 1\leq S_i,T_i\leq 10^9}$

解説

優先度付きキューを用います．

最初に優先度付きキューに ${(T_i,i)}$ を入れます(人 ${i}$ が時刻 ${T_i}$ に宝石をもらった)．キュー内の最小値 ${(t,i)}$ を取り出し，まだ人 ${i}$ が宝石をもらったことが無いならその ${t}$ が答えです．その後， ${(t+S_i,i+1)}$ をキューに入れます．これを繰り返すことですべての答えを求めることができます．

キューの内部は常にすべての宝石がいつどこにあるかという情報が入っています．

kyopro_friendsさんの公式解説と本質は同じです．

提出プログラム

https://atcoder.jp/contests/abc214/submissions/25064992

感想

これ灰diffですか？w

2021-08-14

【競プロ】数学メモ

競技プログラミングメモ典型数論

競プロにおける数学(ほぼ数論)関連のメモ．
コンテスト中に確認できるように，細かい証明とかはせず，重要な部分だけ書く．

オイラーのΦ関数
エラトステネスの篩
線形篩
メビウス関数
二項係数
床関数/天井関数

オイラーのΦ関数

概要

正整数 ${n}$ に対して， ${n}$ と互いに素である ${n}$ 以下の自然数の個数を ${\phi(n)}$ とする．

性質

オイラーのΦ関数には以下のような性質がある．

${\phi(mn)=\phi(m)\phi(n)}$ ( ${m,n}$ は互いに素)
${\phi(pn)=p\phi(n)}$ ( ${n}$ は素数 ${p}$ を素因数に持つ)
${\phi(p^n)=p^n-p^{n-1}}$ ( ${p}$ は素数, ${1\leq n}$ )
${\displaystyle\phi(n)=n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)}$ ( ${p_i}$ は ${n}$ の異なる素因数)
${a^{\phi(n)}\equiv 1\mod n}$ ( ${n,a}$ は互いに素)
${n}$ と互いに素である ${n}$ 以下の自然数の和は ${\displaystyle\frac{n\phi(n)}{2}}$ ( ${2\leq n}$ )
${\displaystyle\sum_{d|n}\phi(d)=n}$
${n}$ の任意の約数を ${d}$ として， ${\gcd(x,n)=d}$ となる ${1\leq x\leq n}$ の個数は ${\phi(\frac{n}{d})}$
${\displaystyle\sum_{d|n}d\phi(d)=\prod_{i=1}^{k}\frac{1-(-p_i)^{2e_i+1}}{1+p_i}}$ $\left(n=\prod_{i=1}^{k}p_i^{e_i}\right)$
$S_{\phi}(n)=\frac{1}{2}n(n+1)-\sum_{i=2}^{n}S_{\phi}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ ${\displaystyle\left(S_{\phi}(n)=\sum_{i=1}^{n}\phi(i)\right)}$
${\displaystyle\sum_{d|n}\frac{\mu^2(d)}{\phi(d)}=\frac{n}{\phi(n)}}$ ( ${\mu}$ ：メビウス関数)

例題

問題1

${N}$ 以下の任意の自然数と ${N}$ の最小公倍数の総和を求めよ．
すなわち ${\displaystyle\sum_{i=1}^{N}\mathrm{lcm}(i,N)}$ を求めよ．
制約
・ ${1\leq N\leq 10^{12}}$

解答

${\displaystyle\sum_{i=1}^{N}\mathrm{lcm}(i,N)}$
${=\displaystyle N\sum_{i=1}^{N}\frac{i}{\gcd(i,N)}}$
${\gcd(i,N)=d}$ となる ${i}$ をまとめると
${=\displaystyle N\sum_{d|N}\sum_{\gcd(i,N)=d,1\leq i\leq N}\frac{i}{d}}$
${=\displaystyle N\left(1+\sum_{d|N,d\neq N}\frac{\frac{N}{d}\phi(\frac{N}{d})}{2}\right)}$
${=\displaystyle N\left(\frac{1}{2}+\sum_{d|N}\frac{\frac{N}{d}\phi(\frac{N}{d})}{2}\right)}$
${=\displaystyle \frac{N}{2}\left(1+\sum_{d|N}d\phi(d)\right)}$
よって ${N}$ を素因数分解すれば ${O(\sqrt{N})}$ で解ける．

問題2

${x}$ 座標と ${y}$ 座標がそれぞれ ${1}$ 以上 ${N}$ 以下となるような座標平面上の格子点のうち，原点 ${(0,0)}$ と線分で結んだとき他の格子点を通らないようなものの数を求めよ．
制約
・ ${1\leq N\leq 10^9}$

解答

${x}$ 座標と ${y}$ 座標が互いに素であれば条件を満たす．したがって， ${gcd(x,y)=1, (1\leq x,y\leq N)}$ である ${(x,y)}$ の数を求めればよい． ${x\geq y}$ を仮定した場合の答えが求められれば元の問題も求まるので以降これを仮定する．
${x}$ を固定すると ${\gcd(x,y)=1}$ となる ${y}$ の数は ${\phi(x)}$ となるので ${\sum_{x=1}^{N}\phi(x)}$ を求めればよい．
$S_{\phi}(n)=\frac{1}{2}n(n+1)-\sum_{i=2}^{n}S_{\phi}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ が成り立つため， ${S_{\phi}(n)}$ を再帰的に求めていけばよい． ${\lfloor\frac{N}{i}\rfloor}$ としてあり得る値の集合を ${V}$ とすると， ${V}$ の要素は ${O(\sqrt{N})}$ 個しかないため，値ごとにまとめて計算すれば1回の再帰で ${O(\sqrt{N})}$ で計算できる． ${\lfloor\frac{\lfloor\frac{N}{s}\rfloor}{t}\rfloor=\lfloor\frac{N}{st}\rfloor}$ であるため，いくら再帰しても使用する値は ${V}$ のいずれかとなる(保存しておく値は ${V}$ だけでよい)．全体の計算量は ${O(\sum_{i=1}^{\sqrt{N}}\sqrt{i})+O(\sum_{i=1}^{\sqrt{N}}\sqrt{\frac{N}{i}})=O(N^{\frac{3}{4}})}$ となり解ける．
また，最初の ${N^{\frac{2}{3}}}$ 要素を線形篩などで先に計算しておくことで ${O(N^{\frac{2}{3}})}$ で解ける．*1

エラトステネスの篩

概要

${N}$ 以下の素数を ${O(N\log\log{N})}$ で列挙できるアルゴリズムとしてエラトステネスの篩がある．
アルゴリズムは以下の通り．

${2}$ から ${N}$ までの整数を用意する．

${p=2}$ から昇順に ${N}$ (実際は ${\sqrt{N}}$ でいい)を越えるまで3を繰り返す．

${p}$ が消されてないなら，残っている整数のうち ${p}$ より大きい ${p}$ の倍数をすべて消す(実際は ${p^2}$ 以上の ${p}$ の倍数でいい)．

残った整数が素数．

計算量

このアルゴリズムの計算量は ${N}$ 以下の各素数 ${p}$ について倍数は ${\frac{N}{p}}$ 個あるので，全体の計算量は ${O(\sum_{p\leq N, p:素数}\frac{N}{p})}$ となるがメルテンスの第二定理を用いると ${O(N\log\log{N})}$ となる．

応用

このアルゴリズムの重要な点は， ${2}$ 以上 ${N}$ 以下の整数 ${x}$ に対して， ${x}$ の素因数すべてが1度ずつ ${x}$ を篩に掛ける点である．例えば， ${x=60=2^2×3×5}$ なら ${2,3,5}$ が1度ずつ ${x}$ を篩に掛ける．
つまり，このアルゴリズムは ${N}$ 以下の自然数 ${x}$ に対して， ${x}$ の素因数を取得できるアルゴリズムであると捉えることができる．素数列挙というのは単に ${x}$ の素因数が ${x}$ のみであるような ${x}$ を列挙しているに過ぎない．

例題

問題1

${2\leq x\leq N}$ のすべての整数 ${x}$ について， ${x}$ の最大素因数を求めよ．
制約
・ ${2\leq N\leq 10^5}$

解答

取得した素因数の中で最大のものを求めればよい．

N = int(input())
ans = list(range(N+1))
for i in range(2,N+1):
    # 素数ならans[i]=iとなっている
    if ans[i] != i:
        continue
    for j in range(i*2,N+1,i):
        ans[j] = i
print(ans[2:])

この問題は高速な素因数分解のために用いられたりもする．

問題2

${2\leq x\leq N}$ のすべての整数 ${x}$ について， ${x}$ の素因数の数(例えば ${60}$ の素因数の数は ${2,3,5}$ の ${3}$ 個)を求めよ．
制約
・ ${2\leq N\leq 10^5}$

解答

篩に掛けるたびにカウントすればよい．

N = int(input())
ans = [0]*(N+1)
for i in range(2,N+1):
    if ans[i] != 0:
        continue
    for j in range(i,N+1,i):
        ans[j] += 1
print(ans[2:])

問題3

${2\leq x\leq N}$ のすべての整数 ${x}$ について，「 ${x}$ と互いに素である ${x}$ 以下の自然数の個数」を求めよ．
制約
・ ${2\leq N\leq 10^5}$

解答

${\displaystyle\phi(n)=n\prod_{i=1}^{k}\left(1-\frac{1}{p_i}\right)}$ ( ${p_i}$ は ${n}$ の異なる素因数)という性質を用いればよい．

N = int(input())
ans = list(range(N+1))
for i in range(2,N+1):
    if ans[i] != i:
        continue
    for j in range(i,N+1,i):
        ans[j] = ans[j] // i * (i-1)
print(ans[2:])

線形篩

概要

エラトステネスの篩では，各合成数について，その素因数の数だけ篩に掛けていた．各合成数について，その最小の素因数だけで篩に掛けることができれば ${O(N)}$ で素数が列挙できる．*2
${spf(n)}$ を ${n}$ の最小の素因数とする． ${n=spf(n)m}$ と表すことができ， ${n}$ が合成数なら ${spf(n)\leq spf(m)}$ となる． ${m}$ の昇順に， ${spf(m)}$ が既に求まっているなら，すでに求めた素数 ${p(\leq spf(m))}$ について ${spf(pm)=p}$ ， ${spf(m)}$ が求まっていないなら ${m}$ は素数であり， ${spf(m)=m}$ として同様の計算を行っていけば素数が列挙できる．

spf = [0] * (N+1)
prime = []
for m in range(2,N+1):
    if spf[m] == 0:
        spf[m] = m
        prime.append(m)
    for p in prime:
        if p > spf[m] or p*m > N:
            break
        spf[p*m] = p

上で説明したエラトステネスの篩と同様に，このアルゴリズムは素数列挙のアルゴリズムではなく ${N}$ 以下の自然数 ${x}$ に対して， ${x}$ の最小の素因数を取得できるアルゴリズムであると捉えることができる．さらに，このアルゴリズムの嬉しい点は任意の ${2\leq n\leq N}$ に対して， ${n}$ を篩に掛けるときに ${n=spf(n)m}$ と表される ${m}$ が(合成数ならば)既に篩に掛けられている点である． ${N}$ 以下の自然数 ${n(=spf(n)m)}$ に対して， ${f(n)}$ が ${spf(n)}$ や ${m}$ や ${f(m)}$ から高速に計算できるなら，このアルゴリズムで高速に求めることができる．

乗法的関数

完全乗法的関数

任意の自然数 ${m,n}$ に対して ${f(mn)=f(m)f(n)}$ が成り立つとき， ${f}$ を完全乗法的関数という． ${f}$ が完全乗法的関数ならば， ${f(n)=f(spf(n)m)=f(spf(n))f(m)}$ であるので ${n}$ が合成数のとき，すでに計算された ${f(spf(n)),f(m)}$ から ${f(n)}$ が計算できる( ${spf(n)}$ は ${m}$ 以下の素数なので ${f(spf(n))}$ は計算されている)． ${n}$ が素数のときに ${f(n)}$ が高速に計算できさえすれば， ${N}$ 以下の自然数 ${n}$ に対する ${f(n)}$ の値が高速に計算できる．

乗法的関数

互いに素な自然数 ${m,n}$ に対して ${f(mn)=f(m)f(n)}$ が成り立つとき， ${f}$ を乗法的関数という． ${f}$ が乗法的関数ならば， ${f(n)=f(spf(n)^{e_n}m)=f(spf(n)^{e_n})f(m)}$ ( ${e_n}$ は ${spf(n)}$ が ${n}$ を割り切る最大の回数)であるので ${e_n}$ を高速に計算できれば完全乗法的関数と同様にして解ける．
${ e_n= \left\{ \begin{array}{ll} e_{n/spf(n)}+1 & (spf(n)=spf(n/spf(n))) \\ 1 & (otherwise) \end{array} \right. }$
とすれば，同様のアルゴリズムで ${e_n}$ や ${spf(n)^{e_n}}$ を求めることができる．*3

性質

${f(x)}$ と ${g(x)}$ が乗法的関数ならば ${h(x)=f(x)g(x)}$ も乗法的関数．
${f(x)}$ と ${g(x)}$ が乗法的関数ならば ${h(x)=\sum_{d|x}f(d)g(x/d)}$ も乗法的関数．特に， ${f(x)}$ が乗法的関数ならば ${h(x)=\sum_{d|x}f(d)}$ も乗法的関数．*4

例題

問題1

${2\leq x\leq N}$ のすべての整数 ${x}$ について，「 ${x}$ と互いに素である ${x}$ 以下の自然数の個数」を求めよ．
制約
・ ${2\leq N\leq 10^5}$

解答

${p}$ を ${n(\geq 2)}$ の最小素因数とする． ${n}$ が ${p^2}$ で割り切れるなら ${\phi(n)=p\phi(n/p)}$ であり，割り切れないなら ${\phi(n)=(p-1)\phi(n/p)}$ であるから線形篩のアルゴリズムを用いることで ${O(N)}$ で求められる．

spf = [0] * (N+1)
phi = [0] * (N+1)
prime = []
for m in range(2,N+1):
    if spf[m] == 0:
        spf[m] = m
        phi[m] = m-1
        prime.append(m)
    for p in prime:
        if p > spf[m] or p*m > N:
            break
        spf[p*m] = p
        if m%p == 0:
            phi[p*m] = p*phi[m]
        else:
            phi[p*m] = (p-1)*phi[m]
print(phi[2:])

メビウス関数

概要

メビウス関数 ${\mu(n)}$ とは以下のように ${1}$ 以上の整数に対して定義される関数である．
${ \mu(n)= \left\{ \begin{array}{ll} 0 & (nが1以外の平方数で割り切れるとき) \\ (-1)^k & (nが異なるk個の素数の積であるとき) \end{array} \right. }$

性質

メビウス関数には以下のような性質がある．

${\mu(mn)=\mu(m)\mu(n)}$ ( ${m,n}$ は互いに素)
${\displaystyle\sum_{d|n}\mu(d)=\left\{\begin{array}{ll}1 & (n=1) \\0 & (n > 1)\end{array}\right.}$
$S_{\mu}(n)=1-\sum_{i=2}^{n}S_{\mu}\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ ${\displaystyle\left(S_{\mu}(n)=\sum_{i=1}^{n}\mu(i)\right)}$
$f(n)=\sum_{d|n}g(d)\Leftrightarrow g(n)=\sum_{d|n}\mu(n/d)f(d)$

例題

問題1

長さ ${N}$ の数列 ${A}$ が与えられる． ${1\leq i < j < k\leq N}$ かつ ${\gcd(A_i,A_j,A_k)=1}$ となる ${(i,j,k)}$ の数を求めよ．
制約
・ ${1\leq N,A_i\leq 10^6}$

解答

${ [P]= \left\{ \begin{array}{ll} 1 & (Pが真) \\ 0 & (Pが偽) \end{array} \right. }$
とする．求める値は ${\displaystyle\sum_{1\leq i < j < k\leq N}[\gcd(A_i,A_j,A_k)=1]}$ であり， ${\displaystyle[n=1]=\sum_{d|n}\mu(d)}$ であるので
${\displaystyle\sum_{1\leq i < j < k\leq N}\sum_{d|\gcd(A_i,A_j,A_k)}\mu(d)\\ =\displaystyle\sum_{1\leq i < j < k\leq N}\sum_{d=1}^{A_{\max}}[d|\gcd(A_i,A_j,A_k)]\mu(d)}$
${d|\gcd(A_i,A_j,A_k)\Leftrightarrow d|A_i\land d|A_j\land d|A_k}$ より
${=\displaystyle\sum_{1\leq i < j < k\leq N}\sum_{d=1}^{A_{\max}}[d|A_i\land d|A_j\land d|A_k]\mu(d)\\ =\displaystyle\sum_{d=1}^{A_{\max}}\mu(d)\sum_{1\leq i < j < k\leq N}[d|A_i\land d|A_j\land d|A_k]}$
${\displaystyle\sum_{1\leq i < j < k\leq N}[d|A_i\land d|A_j\land d|A_k]}$ は ${A}$ から異なる ${d}$ の倍数を ${3}$ つ選ぶ方法の数であるので ${\displaystyle\binom{cnt(d)}{3}}$ となる．ただし， ${cnt(d)}$ は ${A}$ にある ${d}$ の倍数の数．これは高速ゼータ変換により ${O(A_{\max}\log\log{A_{\max}})}$ で計算できる．また， ${\mu(d)}$ もエラトステネスの篩により ${O(A_{\max}\log\log{A_{\max}})}$ で計算でき，線形篩なら ${O(A_{\max})}$ で計算できる．

二項係数

概要

二項係数 ${\displaystyle\binom{n}{k}(0\leq k\leq n)}$ は ${(1+x)^n}$ の二項展開における ${x^k}$ の項の係数．
${\displaystyle\binom{n}{k}=\frac{n!}{k!(n-k)!}}$ である．

性質

二項係数には以下のような性質がある．自明な下位互換は書いてない．
ただし， ${n < k}$ なら ${\displaystyle\binom{n}{k}=0}$ とする．

${\displaystyle\sum_{k=0}^{n}\binom{n}{k}p^{k}q^{n-k}=(p+q)^{n}}$
${\displaystyle\binom{n}{k}=\binom{n}{n-k}}$
${\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}}$
${\displaystyle\sum_{k=m}^{n}\binom{k}{m}=\binom{n+1}{m+1}}$
${\displaystyle\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{n-1}}$
${\displaystyle\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}=F_{n+1}}$ ( ${F_n}$ は ${n}$ 番目のフィボナッチ数)
${\displaystyle\sum_{k=0}^{n}\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}}$
${\displaystyle\sum_{k=0}^{n}\binom{p+k}{k}\binom{q-k}{n-k}=\binom{p+q+1}{n}}$
${\displaystyle\sum_{k=m}^{n}\binom{n}{k}\binom{k}{m}=2^{n-m}\binom{n}{m}}$
${\displaystyle\sum_{k=-a}^{a}(-1)^{k}\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}=\frac{(a+b+c)!}{a!b!c!}}$
${\displaystyle\binom{n}{k}\equiv\prod_{i=1}^{m}\binom{n_i}{k_i}\bmod{p}}$ ( ${p}$ は素数． ${n_i,k_i}$ は ${n,k}$ の ${p}$ 進表記の下 ${i}$ 桁目)

例題

問題1

${\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2}$ を求めよ．

解答

${\displaystyle\sum_{k=0}^{n}\binom{p}{k}\binom{q}{n-k}=\binom{p+q}{n}}$ で ${p=q=n}$ とすれば
${\displaystyle\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}}$

床関数/天井関数

実数 ${x}$ に対して床関数 ${\lfloor x\rfloor}$ は ${x}$ 以下の最大の整数と定義される．
実数 ${x}$ に対して天井関数 ${\lceil x\rceil}$ は ${x}$ 以上の最小の整数と定義される．

性質

${x,y}$ は実数， ${m,n,a,b}$ は整数であるとする．

${x-1 < \lfloor x\rfloor\leq x}$
${x \leq \lceil x\rceil < x+1}$
${\lfloor x\rfloor = -\lceil -x\rceil}$
${\lfloor n+x\rfloor = n+\lfloor x\rfloor}$
${\lfloor x+y\rfloor \geq \lfloor x\rfloor+\lfloor y\rfloor}$
${\left\lfloor \dfrac{m}{n}\right\rfloor = \dfrac{m-m\bmod{n}}{n}}$
${\left\lfloor\dfrac{n}{2}\right\rfloor+\left\lceil \dfrac{n}{2}\right\rceil = n}$
${\left\lfloor\dfrac{y}{x}\right\rfloor\geq\dfrac{y}{x}-\dfrac{x-1}{x}}$ ( ${x,y > 0}$ )
${\displaystyle\sum_{i=1}^{n-1}\left\lfloor\frac{im}{n}\right\rfloor = \frac{(m-1)(n-1)}{2}}$ ( ${m,n}$ は互いに素)
${\displaystyle\lfloor nx\rfloor = \sum_{k=0}^{n-1}\left\lfloor x+\frac{k}{n}\right\rfloor}$
${\left\lfloor\dfrac{\lfloor x\rfloor}{n}\right\rfloor =\left\lfloor\dfrac{x}{n}\right\rfloor}$
${\left\lfloor\dfrac{n}{k}\right\rfloor (1\leq k\leq n)}$ の値の種類は ${O(\sqrt{n})}$ 個
${\left\lfloor\dfrac{n}{k}\right\rfloor = m (m\geq 1)}$ となる整数 ${k}$ の範囲は ${\left\lfloor\dfrac{n}{m+1}\right\rfloor +1\leq k\leq \left\lfloor\dfrac{n}{m}\right\rfloor}$
床関数の和
$f(a,b,m,n)=\sum_{i=0}^{n}\left\lfloor\frac{ai+b}{m}\right\rfloor$ は
- ${a\geq m}$ または ${b\geq m}$ のとき
${\dfrac{n(n+1)}{2}\left\lfloor\dfrac{a}{m}\right\rfloor +(n+1)\left\lfloor\dfrac{b}{m}\right\rfloor + f(a\bmod{m},b\bmod{m},m,n)}$
- ${a < m}$ かつ ${b < m}$ のとき
${n\left\lfloor\dfrac{an+b}{m}\right\rfloor -f(m,m-b-1,a,\left\lfloor\dfrac{an+b}{m}\right\rfloor -1)}$

もで解ける．*5

床関数の性質に性質3を適用することで天井関数の性質に変えることができる．

例題

問題1

${\displaystyle\sum_{i=1}^{N}\left\lfloor\dfrac{N}{i}\right\rfloor}$ を求めよ．
制約
・ ${1\leq N\leq 10^{12}}$

解答

${\lfloor N/i\rfloor =M}$ となる ${i}$ の範囲が ${[L,R]}$ であるとする． ${M=\lfloor N/L\rfloor}$ であるので ${R=\lfloor N/M\rfloor=\lfloor N/\lfloor N/L\rfloor\rfloor}$ となる．
したがって ${(R-L+1)×\lfloor N/L\rfloor}$ の総和を取ればよい．計算量は ${O(\sqrt{N})}$

N = int(input())
ans = 0
L = 1
while L <= N: 
    R = N // (N // L)
    ans += (R - L + 1) * (N // L)
    L = R + 1
print(ans)

問題2

${\left\lfloor\dfrac{10^N}{M}\right\rfloor\bmod{M}}$ を求めよ．
制約
・ ${1\leq N\leq 10^{18}}$
・ ${1\leq M\leq 10^9}$

解答

性質6を ${m\leftarrow\left\lfloor\dfrac{10^N}{M}\right\rfloor , n\leftarrow M}$ として用いると，
${\left\lfloor\dfrac{10^N}{M}\right\rfloor\bmod{M}=\left\lfloor\dfrac{10^N}{M}\right\rfloor-M\left\lfloor\dfrac{10^N}{M^2}\right\rfloor}$ となる．(性質11を用いて ${\left\lfloor\dfrac{\lfloor 10^N/M\rfloor}{M}\right\rfloor=\left\lfloor\dfrac{10^N}{M^2}\right\rfloor}$ と変換した)
さらに性質6を用いると
${\begin{array}{l} \left\lfloor\dfrac{10^N}{M}\right\rfloor\bmod{M}&=&\dfrac{10^N-10^N\bmod{M}}{M}-M\dfrac{10^N-10^N\bmod{M^2}}{M^2}\\ &=&\dfrac{10^N\bmod{M^2}-10^N\bmod{M}}{M}\\ \end{array}}$
となり ${O(\log{N})}$ で求められる．

N,M = map(int,input().split())
print((pow(10,N,M**2)-pow(10,N,M))//M)

*1:[Tutorial] Math note — Dirichlet convolution - Codeforces

*2:[Tutorial] Math note — linear sieve - Codeforces

*3:線形篩 – 37zigenのHP

*4:[Tutorial] Math note — Möbius inversion - Codeforces

*5:Floor Sum of Arithmetic Progression and Other Variants

2021-08-07

yukicoder No.1640 簡単な色塗り

典型グラフ yukicoder 競技プログラミング解説

公式解説とは別の解法です．
問題はこちら

問題概要
解説1：最大二部マッチング
解説2：2-SAT
提出プログラム
感想

問題概要

${1,2,\cdots,N}$ と番号付けされた ${N}$ 個の白い球がある．球 ${A_i}$ または球 ${B_i}$ を選んで黒く塗ることができるという操作を ${N}$ 回行う．すべての球を黒で塗ることが可能かどうかを判定し，可能なら塗り方を出力せよ．

${1\leq N\leq 10^5\\ 1\leq A_i,B_i\leq N}$

解説1：最大二部マッチング

${N}$ 個の頂点 ${U_i}$ と ${N}$ 個の頂点 ${V_i}$ を作り， ${U_i}$ と ${V_{A_i}}$ の間， ${U_i}$ と ${V_{B_i}}$ の間に辺を張る．このグラフの最大マッチングが答え．Dinicを用いると ${O(N\sqrt{N})}$ とかになるが間に合う．この方法だと ${3}$ つ以上の選択肢がある場合でも解ける．

解説2：2-SAT

${N}$ 個の論理変数 ${x_i}$ を考える． ${x_i}$ を ${A_i}$ を選ぶことに， ${\lnot{x_i}}$ を ${B_i}$ を選ぶことに対応させる． ${A_i=A_j}$ なら ${(\lnot{x_i}\lor\lnot{x_j})}$ ， ${A_i=B_j}$ なら ${(\lnot{x_i}\lor x_j)}$ ， ${B_i=B_j}$ なら ${(x_i\lor x_j)}$ という節を追加していけば2-SATを解くアルゴリズムで解ける．このままだと最悪 ${O(N^2)}$ になるが，ABC210 F - Coprime Solitaireと同じようにして節の数を省略することで ${O(N)}$ で解ける．

提出プログラム

https://yukicoder.me/submissions/687124 最大二部マッチング
https://yukicoder.me/submissions/687347 2-SAT

感想

2-SATの節削減覚えたので使ってみた．

2021-08-01

ABC212 E - Safety Journey

グラフ DP高速化 ABC 動的計画法式変形数え上げ競技プログラミング解説

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 頂点の完全無向グラフから ${M}$ 辺取り除く．このグラフの頂点 ${1}$ から ${K}$ 本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点 ${1}$ であるようなパスの数を求めよ．

${2\leq N\leq 5000\\ 0\leq M\leq \min(\frac{N(N-1)}{2},5000)\\ 2\leq K\leq 5000}$

解説

頂点 ${i}$ から頂点 ${j}$ への長さ ${K}$ のパス(厳密にはwalk)の数は，グラフの隣接行列を ${K}$ 乗した行列の ${(i,j)}$ 成分と一致する．
ja.wikipedia.org

これを用いると今回の問題では，グラフの隣接行列を ${K}$ 乗した行列の ${(1,1)}$ 成分が求めるものとなる．このまま適用すると，隣接行列は ${N×N}$ の行列なので ${O(N^3\log{K})}$ かかって間に合わない．

${\downarrow}$

補グラフの隣接行列を見ると ${M}$ 個の非零成分のみからなる疎行列になっている(この行列を ${A}$ とする)．また，全成分が ${1}$ の ${N×N}$ 行列を ${P}$ ，単位行列を ${I}$ とすると，元のグラフの隣接行列は ${P-I-A}$ と表される．
したがって， ${(P-I-A)^K}$ の ${(1,1)}$ 成分が答えとなる．第 ${1}$ 成分のみ ${1}$ であり，他の成分が ${0}$ であるような列ベクトル ${v\in\mathbb{R}^N}$ を用いると ${v^{\top}(P-I-A)^Kv}$ と書ける．

分かりづらいと思うので例(入力例3)

入力例3において
グラフの隣接行列 ${ \left( \begin{array}{ccccc} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{array} \right)}$

補グラフの隣接行列 ${A= \left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)}$

${P= \left( \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{array} \right)}$

${I= \left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right)}$

${v= \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0 \end{array} \right)}$

求めるものは
${v^{\top}(P-I-A)^Kv= \left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \end{array} \right) \left( \begin{array}{ccccc} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{array} \right)^K \left( \begin{array}{c} 1\\ 0\\ 0\\ 0\\ 0 \end{array} \right)}$

${(P-I-A)^K}$ を計算する代わりに右から順に ${(P-I-A)x, x\in \mathbb{R}^N}$ を計算していく．

${Px}$ は ${P}$ の全ての行が同じなので ${O(N)}$ で計算できる．
${(I+A)x}$ は ${I+A}$ の非零成分が ${N+2M}$ 個なので， ${O(N+M)}$ で計算できる(詳しくは下の実装)．
よって， ${(P-I-A)x}$ は ${O(N+M)}$ で計算できる．これを ${K}$ 回繰り返すので ${O((N+M)K)}$ で解ける．

和を取っていくつか引いてるだけなので本質的には公式解説と同じ．

提出プログラム

https://atcoder.jp/contests/abc212/submissions/24702277

感想

初の8問ABC．全体的にいつもより実装きつめだった気がする(Fとか)．

2021-07-17

ABC210 D - National Railway

ABC 典型式変形競技プログラミング解説

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

${H}$ 行 ${W}$ 列のグリッド上の異なる ${2}$ マス ${(i,j),(i',j')}$ を選ぶ， ${C×(|i-i'|+|j-j'|)+A_{ij}+A_{i'j'}}$ の最小値を求めよ．

${2\leq H,W\leq 1000\\ 1\leq C\leq 10^9\\ 1\leq A_{ij}\leq 10^9}$

解説

式の中に絶対値があって面倒なので ${i' \leq i\land j'\leq j}$ と決めることで絶対値を外す．グリッド全体を反転させれば他の場合も表せるので， ${i' \leq i\land j'\leq j}$ の場合で求められればいい．

${\downarrow}$

各 ${(i,j)}$ で ${C×(i-i'+j-j')+A_{ij}+A_{i'j'}}$ の最小を求める．この式を変形すると，

${\underset{i'\leq i\land j'\leq j\land (i,j)\neq(i',j')}{\min}(C×(i-i'+j-j')+A_{ij}+A_{i'j'})\\ =\underset{i'\leq i\land j'\leq j\land (i,j)\neq(i',j')}{\min}(A_{i'j'}-C×(i'+j'))+A_{ij}+C×(i+j)}$

となるので ${A_{i'j'}-C×(i'+j')}$ の2次元の累積minを求めながら計算すれば各マス ${O(1)}$ で求められる．全体の計算量は ${O(HW)}$

提出プログラム

https://atcoder.jp/contests/abc210/submissions/24331401

感想

2021-07-10

ABC209 F - Deforestation

ABC DP高速化典型動的計画法数え上げ解説競技プログラミング

問題はこちら

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列 ${H}$ に対して以下の操作を行うことで ${H}$ の任意の要素を ${0}$ にするときのコストが最小となるような操作列の数を求めよ．

${1\leq i\leq N}$ を選び ${H_i}$ を ${0}$ にする．このとき，この操作を行う前の ${H_{i-1}+H_i+H_{i+1}}$ 分だけコストがかかる．

また， ${H_0=H_{N+1}=0}$ とする．

${0\leq N\leq 4000\\ 1\leq H_i\leq 10^9}$

解説

${H_i}$ の大きい方から取っていくのがよさそう．実際， ${H_i}$ の降順に操作を行えば最小コストになる．ただし， ${H=\{4,2,3\}}$ とかだったら ${3}$ から操作をしてもいい．結局大事なのは隣り合う要素の大小関係で，

${H_i < H_{i+1}}$ なら ${H_{i+1}}$ から操作を行う．
${H_i > H_{i+1}}$ なら ${H_i}$ から操作を行う．
${H_i=H_{i+1}}$ ならどちらから行ってもいい．

という条件を満たすような操作列を数え上げたい．(適当に有向辺を張ったグラフのトポロジカルソートの数え上げのようなもの)

${i}$ の昇順に ${H_i}$ を左から並べていく(左のものから操作する)．ここでは例として ${H=\{3,1,4,1,5\}}$ を考える．

f:id:kanpurin:20210710225848p:plain:w300

まず， ${H_1=3}$ を置く．

f:id:kanpurin:20210710230818p:plain:w300

次に ${H_2=1}$ を置きたいが， ${H_1 > H_2}$ であるため ${H_1}$ の右側に置くしかない．この場合並べ方は次の ${1}$ 通り．

f:id:kanpurin:20210710230901p:plain:w300

次の ${H_3=4}$ は ${H_2 < H_3}$ であるため ${H_2}$ の左側に置く．置き方は次の2通り．

f:id:kanpurin:20210710231019p:plain:w300

残りも同様に ${H_3 > H_4}$ なので ${H_4}$ は ${H_3}$ の右側， ${H_4 < H_5}$ なので ${H_5}$ は ${H_4}$ の左側という風においていけばいい．

ここで重要になるのが，ある要素 ${H_i}$ を置く方法の数を求めるのに必要なのが ${H_{i-1}}$ が今まで並べた ${i-1}$ 要素のうち左から何番目に置かれているかという情報のみであるということ．これを状態として持ちながらDPできる．

${dp[i][j]}$ を「 ${H_i}$ まで並べて， ${H_i}$ が ${j}$ 番目にあるような並べ方の数」とすると遷移は以下の様になる．

$dp[i+1][j]=\sum_{k=j}^{i}dp[i][k]　(H_i < H_{i+1})$
$dp[i+1][j]=\sum_{k=1}^{j-1}dp[i][k]　(H_i > H_{i+1})$
$dp[i+1][j]=\sum_{k=1}^{i}dp[i][k]　(H_i=H_{i+1})$

$dp[i+1][j]=\sum_{k=j}^{i}dp[i][k]　(H_i < H_{i+1})$ の遷移について説明する．
既に ${H_i}$ まで並べられている列の ${j}$ 番目に ${H_{i+1}}$ を入れる．

f:id:kanpurin:20210710234653p:plain:w400

このとき， ${H_{i+1}}$ を入れた後に「 ${H_i}$ より ${H_{i+1}}$ が左に置かれている」という条件が成り立つ必要があり，これが成り立っているようなものは ${H_i}$ が ${j}$ 番目から ${i}$ 番目にある列であるので， ${dp[i+1][j]}$ には ${dp[i][k](j\leq k\leq i)}$ からの遷移がある．

他の遷移も同様に考えることができる．

これはいわゆる挿入DPというやつで順列の数え上げでよく使う．

提出プログラム

https://atcoder.jp/contests/abc209/submissions/24140336

感想

丁寧に考察すれば見えてくる問題