ITF.PC 2024 M - Does My Favored Team Have a Chance? 完全解説

問題概要

勝ち、引き分け、負けのポイントがそれぞれ 2 、 1 、 0 のリーグ戦について、各チームの現在のポイントと残りの試合数が与えられるので、単独優勝できる場合および優勝できる場合があるかを判定する問題である。

解法

あるチームの優勝可能性の判定

チーム i\ (1\leq i\leq N) が優勝する場合がある条件と、その高速な判定法を考える。

T=\{1,2,\ldots,N\},\ T'=T\setminus\{i\} とする。 また、空でない R\ (\subseteq T') について P(R)=\sum _ {k\in R} P _ k,\ G(R)=\sum _ {\{j,k\}\subseteq R} G _ {j,k} と定義する。 そして、 a(R)=(P(R)+2G(R))/|R| と定義する。

空でないある R\ (\subseteq T') が存在して a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j} が成立するならば、チーム i が優勝する場合はないことが次のようにいえる。 チーム j\ (\in T') とチーム k\ (\in T') が今後対戦することにより、 G _ {j,k} と G _ {k,j} が 1 小さくなり、試合結果によって P _ j または P _ k にポイントが加わると考える。 すべての試合が終了した後の P _ k,\ a(R) をそれぞれ P' _ k,\ a'(R) とおくと、 a(R)\leq a'(R) がいえる。 また、 a'(R) は P' _ k\ (k\in R) の平均であることもいえる。 平均の性質より、あるチーム k\ (\in R) が存在して、 a(R)\leq a'(R)\leq P' _ k が成立する。 P' _ i\leq P _ i+2\sum _ {j\in T'} G _ {i,j} と仮定より、空でないある R\ (\subseteq T') と k\ (\in R) が存在して P' _ i\lt P' _ k となるから、チーム i はどの場合においても優勝できない。

次に、 a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j} を満たす、空でない R\ (\subseteq T') が存在するかどうかは次のように判定できる。 \{s\}\cup T'\cup\{t\} を頂点集合とし、 s から各 j\ (\in T') に容量 2\sum _ {j\lt k} G _ {j,k} の有向辺を、各 j\ (\in T') から k\ (\in T',\ j\lt k) に容量 2G _ {j,k} の有向辺を、各 k\ (\in T') から t に容量 P _ i+2\sum _ {j\in T'} G _ {i,j}-P _ k の有向辺を張る。 なお、ある k\ (\in R) について P _ i+2\sum _ {j\in T'} G _ {i,j}-P _ k が負になる場合は、明らかにチーム i は優勝できない。 このネットワークの s から t への最小カットの s 側の頂点集合を S としたとき、ある R\ (\subseteq T') が存在して S=\{s\}\cup R となる。 そして、 s 側の頂点集合が \{s\} となるようなカットの容量は 2\sum _ {\{j,k\}\subseteq T'} G _ {j,k} であるから、 R が空でないとき最小カットの容量は 2\sum _ {\{j,k\}\subseteq T'} G _ {j,k} 未満である。 このとき、 a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j} を満たすことが次のようにいえる。
\begin{gathered} 2\sum _ {\{j,k\}\subseteq T'} G _ {j,k}\gt 2\sum _ {j\notin R}\sum _ {j\lt k} G _ {j,k}+2\sum _ {j\in R}\sum _ {k\notin R,\ j\lt k} G _ {j,k}+|R|\left(P _ i+2\sum _ {j\in T'} G _ {i,j}\right)-\sum _ {k\in R} P _ k\\ \therefore\ 2G(R)=2\sum _ {\{j,k\}\subseteq R} G _ {j,k}\gt |R|\left(P _ i+2\sum _ {j\in T'} G _ {i,j}\right)-P(R)\\ \therefore\ a(R)=\frac{P(R)+2G(R)}{|R|}\gt P _ i+2\sum _ {j\in T'} G _ {i,j}\end{gathered}
また、最小カットの s 側の頂点集合が \{s\} となる場合、最大フローに注目すると、すべてのチーム k\ (\in T') について今後チーム i 以外との対戦で得るポイントの合計が P _ i+2\sum _ {j\in T'} G _ {i,j}-P _ k 以下となる場合が構築できている。 このような場合において、チーム i は今後のすべての試合に勝てば優勝できる。

よって、チーム i\ (1\leq i\leq N) の優勝可能性の判定は上のネットワークについて最大流問題を解くことで行える。 このネットワークは \Theta(N) 頂点 \Theta(N ^ 2) 辺であるため、Push-Relabel Algorithmによる時間計算量は O(N ^ 3) となる。 Dinic法でも、この問題に対しては十分高速である。

あるチームの単独優勝可能性の判定

チーム i\ (1\leq i\leq N) が単独優勝する場合がある条件と、その高速な判定法を考える。

同様に、 T=\{1,2,\ldots,N\},\ T'=T\setminus\{i\} とする。 また、空でない R\ (\subseteq T') について P(R)=\sum _ {k\in R} P _ k,\ G(R)=\sum _ {\{j,k\}\subseteq R} G _ {j,k} と定義する。 そして、 a(R)=(P(R)+2G(R))/|R| と定義する。

空でないある R\ (\subseteq T') が存在して a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j}-1 が成立するならば、チーム i が優勝する場合はないことが次のようにいえる。 すべての試合が終了した後の P _ k を P' _ k とおくと、あるチーム k\ (\in R) が存在して、 a(R)\leq P' _ k が成立するのであった。 P' _ i\leq P _ i+2\sum _ {j\in T'} G _ {i,j} と仮定より、空でないある R\ (\subseteq T') と k\ (\in R) が存在して P' _ i-1\lt P' _ k となる。 ポイントの整数性より P' _ i\leq P' _ k が成立するから、チーム i はどの場合においても単独優勝できない。

\{s\}\cup T'\cup\{t\} を頂点集合とし、 s から各 j\ (\in T') に容量 2\sum _ {j\lt k} G _ {j,k} の有向辺を、各 j\ (\in T') から k\ (\in T',\ j\lt k) に容量 2G _ {j,k} の有向辺を、各 k\ (\in T') から t に容量 P _ i+2\sum _ {j\in T'} G _ {i,j}-1-P _ k の有向辺を張る。 ある k\ (\in R) について P _ i+2\sum _ {j\in T'} G _ {i,j}-1-P _ k が負になる場合は、明らかにチーム i は優勝できない。 また、優勝可能性と同様の不等式変形により、最小カットの s 側の頂点集合が \{s\} でない場合、 a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j}-1 を満たす。 また、最小カットの s 側の頂点集合が \{s\} となる場合、最大フローに注目すると、すべてのチーム k\ (\in T') について今後チーム i 以外との対戦で得るポイントの合計が P _ i+2\sum _ {j\in T'} G _ {i,j}-1-P _ k 以下となる場合が構築できている。 このような場合において、チーム i は今後のすべての試合に勝てば単独優勝できる。

よって、チーム i\ (1\leq i\leq N) の単独優勝可能性の判定は上のネットワークについて最大流問題を解くことで行える。 優勝可能性と同様に、Push-Relabel Algorithmによる時間計算量は O(N ^ 3) となり、Dinic法でもこの問題に対しては十分高速である。

すべてのチームの優勝可能性の高速な判定

T=\{1,2,\ldots,N\},\ T'=T\setminus\{i\},\ T''=T\setminus\{k\} とおく。 チーム i\ (\in T) が優勝する場合はないとする。 このとき、チーム k\ (\in T) について P _ i+2\sum _ {j\in T'} G _ {i,j}\geq P _ k+2\sum _ {j\in T''} G _ {k,j} が成立するならばチーム k が優勝する場合もないことが次のようにいえる。

まず、仮定より空でないある R\ (\subseteq T') が存在して a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j}\geq P _ k+2\sum _ {j\in T''} G _ {k,j} が成立する。 R\subseteq T'' でもあるならば明らかにチーム k が優勝する場合はない。 R\not\subseteq T'' であることは k\in R であることと同値である。 a(\{k\})=P _ k\leq P _ k+2\sum _ {j\in T''} G _ {k,j} より R\neq\{k\} であるから、そのような場合は R\setminus\{k\} は空でない。 a(R\setminus\{k\}) を求める。
\begin{align} a(R\setminus\{k\})&=\frac{P(R\setminus\{k\})+2G(R\setminus\{k\})}{|R|-1}\\ &=\frac{P(R)-P _ k+2G(R)-2\sum _ {j\in R} G _ {k,j}}{|R|-1}\\ &\geq\frac{P(R)-P _ k+2G(R)-2\sum _ {j\in T''} G _ {k,j}}{|R|-1}\\ &\gt \frac{P(R)+2G(R)-a(R)}{|R|-1}\\ &=\frac{|R|a(R)-a(R)}{|R|-1}\\ &=a(R)\\ &\gt P _ k+2\sum _ {j\in T''} G _ {k,j}\end{align}
となり、この場合もチーム k が優勝する場合はないことが示された。

条件が等号付きであるため、 P _ i+2\sum _ {j\in T'} G _ {i,j} が等しければ優勝可能かどうかも等しい。 よって、各チームを P _ i+2\sum _ {j\in T'} G _ {i,j} でソートして二分探索を行うことにより、全体としての時間計算量を O(N ^ 3\log N) にすることができる。 また、他のチームと今後対戦しない仮のチームを追加して、そのチームが各チームの P _ i+2\sum _ {j\in T'} G _ {i,j} と等しいポイントを持っているとして二分探索してもよい。

すべてのチームの単独優勝可能性の高速な判定

同様に T=\{1,2,\ldots,N\},\ T'=T\setminus\{i\},\ T''=T\setminus\{k\} とおく。 チーム i\ (\in T) が単独優勝する場合はないとし、チーム k\ (\in T) について P _ i+2\sum _ {j\in T'} G _ {i,j}\geq P _ k+2\sum _ {j\in T''} G _ {k,j} が成立する場合を考える。

まず、仮定より空でないある R\ (\subseteq T') が存在して a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j}-1\geq P _ k+2\sum _ {j\in T''} G _ {k,j}-1 が成立する。 R\subseteq T'' でもあるならば明らかにチーム k が単独優勝する場合はない。 一方、 k\in R である場合、 \sum _ {j\in T''} G _ {k,j}=0 ならば a(\{k\})=P _ k\gt P _ k+2\sum _ {j\in T''} G _ {k,j}-1 より R=\{k\} である可能性がある。 ただし、 \sum _ {j\in T''} G _ {k,j}=0 を満たすチーム k が単独優勝するためには、任意のチーム k'\ (\in T'') について P _ k\gt P _ {k'} が成り立つ必要がある。 そのようなチームが存在すれば、そのチームについて判定を行えばよい。

k\in R かつ \sum _ {j\in T''} G _ {k,j}\gt 0 の場合は R\setminus\{k\} は空でないとしてよい。 また、ポイントの整数性を考慮して a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j}-1\geq P _ k+2\sum _ {j\in T''} G _ {k,j}-1 を a(R)-1/|R|\geq P _ i+2\sum _ {j\in T'} G _ {i,j}-1\geq P _ k+2\sum _ {j\in T''} G _ {k,j}-1 と言い換えておく。
\begin{align} a(R\setminus\{k\})&=\frac{P(R\setminus\{k\})+2G(R\setminus\{k\})}{|R|-1}\\ &=\frac{P(R)-P _ k+2G(R)-2\sum _ {j\in R} G _ {k,j}}{|R|-1}\\ &\geq\frac{P(R)-P _ k+2G(R)-2\sum _ {j\in T''} G _ {k,j}}{|R|-1}\\ &\geq\frac{P(R)+2G(R)-(a(R)+1-1/|R|)}{|R|-1}\\ &=\frac{|R|a(R)-a(R)-(|R|-1)/|R|}{|R|-1}\\ &=a(R)-\frac{1}{|R|}\\ &\geq P _ k+2\sum _ {j\in T''} G _ {k,j}-1\end{align}
となり、 a(R)-1/|R|=P _ i+2\sum _ {j\in T'} G _ {i,j}-1=P _ k+2\sum _ {j\in T''} G _ {k,j}-1 かつ \sum _ {j\in R} G _ {k,j}=\sum _ {j\in T''} G _ {k,j} が成立する場合のみ、 a(R\setminus\{k\})\gt P _ k+2\sum _ {j\in T''} G _ {k,j}-1 がいえない。

他のチームと今後対戦しない仮のチームを追加する二分探索を行いながら、上のコーナーに対処する。 まず、 p 点のチームを追加して優勝可能性の判定をすることは、 (p+1) 点のチームを追加してそのチームの単独優勝可能性の判定をすることと等価である。 優勝可能と判定された最小のポイントを p _ m 点とおく。 P _ i+2\sum _ {j\in T'} G _ {i,j}\lt p _ m ならば明らかにチーム i は優勝不可能である。 P _ i+2\sum _ {j\in T'} G _ {i,j}\gt p _ m ならばチーム i は単独優勝も可能であることが次のようにいえる。 P _ i+2\sum _ {j\in T'} G _ {i,j}\gt p _ m かつチーム i が単独優勝不可能であることを仮定する。 すると、ある R\ (\subseteq T') が存在して a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j}-1 が成立する。 T に p _ m 点を持ち今後試合がないチーム k を追加すると、明らかに R\subseteq T と a(R)\gt P _ i+2\sum _ {j\in T'} G _ {i,j}-1\geq p _ m が成立し、チーム k が優勝可能と判定されたことと矛盾する。

P _ i+2\sum _ {j\in T'} G _ {i,j}=p _ m の場合、 (p+1) 点のチームを追加してそのチームの単独優勝可能性の判定を行う。 明らかに単独優勝は不可能と判定され、最小カットの容量が 2\sum _ {\{j,k\}\subseteq T'} G _ {j,k}-1 でない場合はコーナーでないことが次のようにいえる。
\begin{gathered} 2\sum _ {\{j,k\}\subseteq T'} G _ {j,k}-1\gtreqless 2\sum _ {j\notin R}\sum _ {j\lt k} G _ {j,k}+2\sum _ {j\in R}\sum _ {k\notin R,\ j\lt k} G _ {j,k}+|R|\left(P _ i+2\sum _ {j\in T'} G _ {i,j}-1\right)-\sum _ {k\in R} P _ k\\ \therefore\ 2G(R)-1=2\sum _ {\{j,k\}\subseteq R} G _ {j,k}-1\gtreqless |R|\left(P _ i+2\sum _ {j\in T'} G _ {i,j}-1\right)-P(R)\\ \therefore\ a(R)-\frac{1}{|R|}=\frac{P(R)+2G(R)-1}{|R|}\gtreqless P _ i+2\sum _ {j\in T'} G _ {i,j}-1\end{gathered}
ただし、不等号は複号同順。 最小カットの容量が 2\sum _ {\{j,k\}\subseteq T'} G _ {j,k}-1 である場合について考える。 R に属し p _ m=P _ i+2\sum _ {j\in T'} G _ {i,j} を満たす各頂点 i について、フローを押し戻して s から i へのパスにフローを 1 流せるようにできる。 i から t へフローを流せるならば得られたのが最大フローではないということになってしまうから、 i から t へ張った辺にはフローを流しきっている。 i を経由する s から t へのパスに無理矢理フローを 1 流すことを考えると、すべてのチーム k\ (\in T') について今後得るポイントの合計が p _ m-1-P _ k 以下であり、かつチーム i の今後得るポイントの合計が p _ m-P _ i である場合が構築できている。 これは、チーム i が単独優勝できている場合である。

よって、単独優勝可能性も判定する場合、二分探索をした後、境界について最小カットを求めることが必要となる。 最大流問題を解く回数を \Theta(\log N) にする場合、優勝可能となる最小の P _ i+2\sum _ {j\in T'} G _ {i,j} が優勝可能となる最小のポイントではない可能性に注意が必要である。 また、Push-Relabel Algorithmの場合、実装によっては残余ネットワークだけでなく残存量を考慮して最小カットを求める必要があることに注意が必要である。

基になった論文

優勝判定については、KD Wayne, "A New Property and Faster Algorithm for Baseball Elimination", 1999に記載がある。

おわりに

作問の際、計算量解析および単独優勝判定のコーナーの対処をtatyamさんに教えていただきました。 また、問題原案を出した際にYu_さんにも助言をいただきました。 ここに感謝の意を表します。

AtCoder Regular Contest 185 (ARC185) E - Adjacent GCDの勉強

問題

E - Adjacent GCDatcoder.jp

素朴なDP

単純な考察により、答え R _ 1,R _ 2,\ldots,R _ Nは、 R _ 0=0として R _ i=2R _ {i-1}+\sum _ {j=1} ^ {i-1} 2 ^ {j-1} \gcd{(A _ j, A _ i)}で表されることがわかる。

この問題では、このDPを高速化することが求められている。

高速化1

解法

Nyaanさん、maspyさんの公式解説による方法である。

\max A _ i=Mとおく。 \delta _ {n,g}\ (1\leq n,g\leq M)をクロネッカーのデルタとする。
\begin{align} \gcd{(A _ j, A _ i)}=\sum _ {n=1} ^ M n\delta _ {n,\gcd{(A _ j, A _ i)}}\end{align}
が成立する。 また、数列 a _ {n,g}を
\begin{align} a _ {n,g}=\sum _ {n|m,\ m\leq M} \delta _ {m,g}\end{align}
で定義する。 \gcd{(A _ j, A _ i)}を a _ {n,\gcd{(A _ j, A _ i)}}で表したいと考える。
\begin{align} \gcd{(A _ j, A _ i)}=\sum _ {n=1} ^ M x _ {n,\gcd{(A _ j, A _ i)}}a _ {n,\gcd{(A _ j, A _ i)}}\end{align}
が成り立つと仮定すると
\begin{align} \gcd{(A _ j, A _ i)}&=\sum _ {n=1} ^ M n\delta _ {n,\gcd{(A _ j, A _ i)}}\\ &=\sum _ {n=1} ^ M x _ {n,\gcd{(A _ j, A _ i)}}a _ {n,\gcd{(A _ j, A _ i)}}\\ &=\sum _ {n=1} ^ M x _ {n,\gcd{(A _ j, A _ i)}}\sum _ {n|m,\ m\leq M} \delta _ {m,\gcd{(A _ j, A _ i)}}\\ &=\sum _ {m=1} ^ M\left(\sum _ {n|m,\ n\leq M} x _ {n,\gcd{(A _ j, A _ i)}}\right)\delta _ {m,\gcd{(A _ j, A _ i)}}\end{align}
となり、 x _ {n,\gcd{(A _ j, A _ i)}}は \gcd{(A _ j, A _ i)}に依存しないことがわかる。 そして、
\begin{align} n=\sum _ {m|n,\ m\leq M} x _ m\end{align}
となる (x _ n)は存在する。 x _ n=\varphi(n)であるが、それがわからなくても約数メビウス変換で十分高速に事前計算できる。

ここで、最大公約数の性質より、アイバーソン括弧を用いると a _ {n,\gcd{(A _ j, A _ i)}}=[n|\gcd{(A _ j, A _ i)}]=[n|A _ j][n|A _ i]と表せる。 したがって、
\begin{align} \sum _ {j=1} ^ {i-1} 2 ^ {j-1} \gcd{(A _ j, A _ i)} &=\sum _ {j=1} ^ {i-1} 2 ^ {j-1} \sum _ {n=1} ^ M x _ n[n|A _ j][n|A _ i]\\ &=\sum _ {j=1} ^ {i-1} 2 ^ {j-1} \sum _ {n|A _ i,\ n\leq M}x _ n[n|A _ j]\\ &=\sum _ {n|A _ i,\ n\leq M}x _ n\sum _ {j=1} ^ {i-1} 2 ^ {j-1} [n|A _ j]\end{align}
と変形できる。 DPとともに、 A _ iの約数の列挙と各 nについての \sum _ {j=1} ^ {i-1} 2 ^ {j-1} [n|A _ j]の更新を行うことで、十分高速に答えが求まる。

提出

Submission #58928300 - AtCoder Regular Contest 185atcoder.jp

Nyaan’s Libraryを使用

倍数変換・約数変換 | Nyaan’s Librarynyaannyaan.github.io

高速化2

解法

noshi91さんのユーザ解説による方法である。

数列 (a _ i),(b _ i)について、 c _ k=\sum _ {\gcd(i,j)=k} a _ i b _ jで定まる数列 (c _ i)ã‚’ (a _ i),(b _ i)のGCD畳み込みという。 また、 f(x) _ k=\sum _ {k|i} x _ i（ (x _ i)は有限列とする）で定まる数列 (f(x) _ i)について、 (c _ i)が (a _ i),(b _ i)のGCD畳み込みであれば、 f(c) _ i=f(a) _ i f(b) _ iが成立する。 以下の記事が詳しい。 添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモnoshi91.hatenablog.com

\max A _ i=Mとおく。単位行列の第 j列をとった列ベクトルを \boldsymbol{\delta} _ jと表すことにする。 それぞれの \boldsymbol{\delta} _ jを数列と見ると、 \boldsymbol{\delta} _ {\gcd(A _ j,A _ i)}は \boldsymbol{\delta} _ {A _ j},\boldsymbol{\delta} _ {A _ i}のGCD畳み込みになっている。 線形変換 Zを、 Z(\boldsymbol{\delta} _ j) _ k=\sum _ {k|i,\ i\leq M} (\boldsymbol{\delta} _ j) _ iで定めると、逆変換 Z ^ {-1}が存在する。 また、列ベクトル \boldsymbol{n}を \boldsymbol{n} _ i=iで定め、演算 \circをアダマール積とする。
\begin{align} \gcd{(A _ j, A _ i)}&=\sum _ {n=1} ^ M n(\boldsymbol{\delta} _ {\gcd(A _ j,A _ i)}) _ n\\ &=\langle\boldsymbol{n},\boldsymbol{\delta} _ {\gcd(A _ j,A _ i)}\rangle\end{align}
が成立する。 したがって、
\begin{align} \sum _ {j=1} ^ {i-1} 2 ^ {j-1} \gcd{(A _ j, A _ i)} &=\sum _ {j=1} ^ {i-1} \langle\boldsymbol{n},2 ^ {j-1} \boldsymbol{\delta} _ {\gcd(A _ j,A _ i)}\rangle\\ &=\sum _ {j=1} ^ {i-1} \langle\boldsymbol{n},2 ^ {j-1} \boldsymbol{\delta} _ {\gcd(A _ j,A _ i)}\rangle\\ &=\sum _ {j=1} ^ {i-1} \langle\boldsymbol{n},Z ^ {-1}(Z(2 ^ {j-1}\boldsymbol{\delta} _ {A _ j})\circ Z\boldsymbol{\delta} _ {A _ i})\rangle\\ &=\sum _ {j=1} ^ {i-1} \langle (Z ^ {-1}) ^ \top\boldsymbol{n},Z(2 ^ {j-1}\boldsymbol{\delta} _ {A _ j})\circ Z\boldsymbol{\delta} _ {A _ i}\rangle\\ &=\left\langle (Z ^ {-1}) ^ \top\boldsymbol{n},\left(\sum _ {j=1} ^ {i-1} Z(2 ^ {j-1}\boldsymbol{\delta} _ {A _ j})\right)\circ Z\boldsymbol{\delta} _ {A _ i}\right\rangle\\ &=\sum _ {n=1} ^ M \left((Z ^ {-1}) ^ \top\boldsymbol{n}\right) _ n\left(\sum _ {j=1} ^ {i-1} Z(2 ^ {j-1}\boldsymbol{\delta} _ {A _ j})\right) _ n \left(Z\boldsymbol{\delta} _ {A _ i}\right) _ n\end{align}
と変形できる。 \left(Z\boldsymbol{\delta} _ {A _ i}\right) _ nが掛かるから、 nが A _ iの約数である場合のみ計算すればよい。 また、 \sum _ {j=1} ^ {i-1} Z(2 ^ {j-1}\boldsymbol{\delta} _ {A _ j})も十分高速に更新できる。 そして、 Zが倍数ゼータ変換にあたることを考えると、 (Z ^ {-1})が倍数メビウス変換で、 (Z ^ {-1}) ^ \topが約数メビウス変換にあたることがわかる。 結局、高速化1の方法と同じ実装を行うことになり、さらに、結局maspyさんのユーザ解説で軽く触れられている転置原理からの導出を行っていたことがわかる。 提出は省略する。

【自分のための備忘録】競プロで精進した問題一覧【2024/9～】

※ネタバレ注意


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
メモ：一見\binom{100}{5}\lt 10^8なのかよといらつく問題だが、より難しい問題で合同算術の積の衝突可能性について慣れていると、そういう意図であろうという見通しが立ちやすい


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：進数変換
メモ：2,8,10,16進数以外を標準ライブラリで扱える言語は意外と少ない。今回はHaskellを使用したが、普通にC++やPythonで直書きしたほうが早く書き終わる気がする。
qiita.com
scrapbox.io
https://www.tumblr.com/sarabandejp/101471543023
blog.sarabande.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
メモ：do-while文のcontinueのためにgotoを使う場合、ラベルの位置をdoの前に置くと無限ループになる危険性がある


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：多倍長整数
メモ：C++の符号付き128bit整数型は__int128_t


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
メモ：符号付き64bit整数型で10^18を10倍しないように気をつける、符号なし64bit整数型を使うのも手


atcoder.jp
atcoder.jp


https://atcoder.jp/contests/typical90/tasks/typical90_aatcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：木の直径
ライブラリ：
ei1333.github.io


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：尺取り法


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：01 BFS
メモ：01 BFSの説明
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：ダブリング
メモ：繰り返し二乗法と根本は同じ


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
メモ：hとwのループなどの場合、continueは普通にcontinueで内側のループのみ抜ければよい


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：Convex Hull Trick (Li Chao Tree) + DP


atcoder.jp
atcoder.jp
キーワード：ワーシャル・フロイド法 更新クエリ
メモ：コンテスト中のデバッグは、アルゴリズムが間違っている可能性の検証とアルゴリズムを正しく実装できていない可能性の検証を切り分けて行ったほうがよいかもしれない


atcoder.jp
atcoder.jp
メモ：操作に関する問題を具体例で検証する場合は、具体例の性質をなるべく気にせずに操作の性質に注目したほうがよいことが多い
また、今回は有限回で行えなくなる不可逆な操作で、かつ目的の状態からも行える可能性がある操作である
このような場合、操作が行えなくなる状態について考察するのも手


atcoder.jp
atcoder.jp
キーワード：倍数変換・約数変換（ゼータ変換・メビウス変換）、GCD畳み込み
メモ：まとめた
not-leonian.hatenablog.com
ライブラリ：
nyaannyaan.github.io


atcoder.jp
atcoder.jp
メモ：


atcoder.jp
atcoder.jp
キーワード：01 on Tree


atcoder.jp
atcoder.jp
キーワード：01 on Tree
メモ：「数列の、位置の重み付きの総和」は「01の数列の列の転倒数」に言い換えられる


atcoder.jp
atcoder.jp
メモ：ゲームの勝敗をメモ化再帰で判定する場合、先手の場合は初期値をfalseにして次の後手の勝敗との論理和をとり、後手の場合は初期値をtrueにして次の先手の勝敗との論理積をとるのが定石


atcoder.jp
atcoder.jp
キーワード：2-SAT


atcoder.jp
atcoder.jp
キーワード：Zero-Sum Ranges


atcoder.jp
atcoder.jp
キーワード：フィボナッチ数列、多項式の多点評価（Multipoint Evaluation）
ライブラリ：
nyaannyaan.github.io
メモ：Nyaan's Libraryの多点評価は2点以上でないと実行時エラーが発生することに注意、Nyaan's Libraryの998244353を法とするmodintはLazyMontgomeryModInt<998244353>


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：ダイクストラ法
ライブラリ：
ei1333.github.io


atcoder.jp
atcoder.jp
キーワード：強連結成分分解


atcoder.jp
atcoder.jp
キーワード：最大値取得・アフィン変換区間更新クエリの遅延セグ木


atcoder.jp
atcoder.jp
キーワード：乗法的関数
ライブラリ：
nyaannyaan.github.io
メモ：和を積として解釈　上のライブラリはbundleするとtemplateが衝突したり、enumurateを誤字っていたりとそのままでは使いにくい

atcoder.jp
キーワード：エラトステネスの篩
メモ：2以上$N$以下の整数について各素因数ごとに処理を行うときの計算量は、エラトステネスの篩で考えられる
algo-method.com


atcoder.jp
atcoder.jp
キーワード：マンハッタン距離、45度回転


atcoder.jp
atcoder.jp
キーワード：区間chminクエリのSegment Tree Beats!
ライブラリ：
nyaannyaan.github.io
メモ：Segment Tree Beats!は時間/空間ともに定数倍に注意

atcoder.jp
キーワード：最大値取得のセグ木
メモ：もらうDPか送るDPかで必要なデータ構造が変わってしまう例　ただセグ木が得意なのは1点更新であることを考えると自然と思いつくはず　最大値または-1を出力する問題でセグ木を使う場合、e()の返す値に注意


atcoder.jp
atcoder.jp
キーワード：木DP、LCAによる木上の2頂点の距離の公式
メモ：
ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム | アルゴリズムロジック

atcoder.jp
メモ：わざわざLCAによる公式を考えなくても、似たような主客転倒により各辺の寄与はその辺を切って得られる森の各連結成分の頂点数の積であることがわかる


atcoder.jp
atcoder.jp
キーワード：半分全列挙


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：最大値取得のセグ木によるLIS


atcoder.jp
atcoder.jp
キーワード：区間和取得、アフィン変換区間更新クエリの遅延セグ木
メモ：制約に途中で気付いたが、そのまま時間\Theta(N\log\operatorname{max}A)/空間\Theta(\operatorname{max}A)で解ききってしまった


atcoder.jp
atcoder.jp
キーワード：BIT
メモ：ac-libraryのfenwick_treeは1点更新ではなく1点加算であることに注意


atcoder.jp
atcoder.jp
キーワード：木DP


atcoder.jp
atcoder.jp
キーワード：平面走査


atcoder.jp
atcoder.jp
メモ：ビットごとの論理積・論理和・排他的論理和に関する問題はビットごとに分解して考えがち


atcoder.jp
atcoder.jp
キーワード：ワーシャル・フロイド法


atcoder.jp
atcoder.jp
キーワード：期待値DP
メモ：FPSで解いたが、結局出てきたのは公式解説と同じ式
すごろくDPは有理数modだとゼロ除算が発生するという理由で出力形式が小数である場合が多い


atcoder.jp
atcoder.jp
キーワード：最大値取得・アフィン変換区間更新クエリの遅延セグ木


atcoder.jp
https://atcoder.jp/contests/dp/submissions/60385892atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
メモ：DPの手法の1つに、「答えを添字にして、答えを達成する状態のうち最も良いものを求める」というものがある


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：DAG上のDP


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：期待値DP、Sushi
メモ：DPの計算の順番に注意


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
メモ：落ち着いて式変形をする


atcoder.jp
atcoder.jp
キーワード：Union-Find
メモ：既に連結である場合に注意


atcoder.jp
atcoder.jp


atcoder.jp
atcoder.jp
キーワード：最大値取得・アフィン変換区間更新クエリの遅延セグ木、セグ木上の二分探索
メモ：倍々になるので計算量がlogで抑えられるテク
ac-libraryのセグ木上の二分探索は追加の引数を取れないため、セグ木ではなく遅延セグ木にしないといけない場合がある


atcoder.jp
https://atcoder.jp/contests/arc189/submissions/60628783atcoder.jp
キーワード：最長共通部分列(LCS)、最長増加部分列(LIS)
メモ：distinctな2つの列のLCSは、片方の列の値を「もう片方の列でのその値の添字」に置き換えることでLISに落とし込まれる


atcoder.jp
atcoder.jp
キーワード：Grundy数
メモ：コンテスト中、時間が少なかったとしてもGrundy数の問題は落ち着いて法則を確認しよう

QCoder Programming Contest 002のB4～B8の勉強

はじめに

この記事は私がQPC002で解けなかった問題を理解するためのノートのようなものであり、有名な量子アルゴリズムの回路の導出などには深く立ち入りません。
より体系的に勉強したい場合は別の記事を見ることを推奨します。

B4: Quantum Fourier Transform

この問題はコンテスト中に解くことができました。

問題

www.qcoder.jp

解法

この問題は量子フーリエ変換(QFT)の回路を実装する問題です。
QFTについては、以下のサイトなどで詳しく説明されています。
dojo.qulacs.org
しかし、QCoderと異なりビッグエンディアンで実装されています。最後にスワップゲートを用いていますが、この代わりに最初にスワップゲートを用いるとリトルエンディアンでの実装になります。
公式解説のように、そもそも実装を逆順にしてしまってもよいです。
B3の題材にもなっているスワップゲートについては、以下のサイトなどで詳しく説明されています。
dojo.qulacs.org

実装

後の問題のために、QFTの回路を返す関数を実装しています。

from qiskit import QuantumCircuit
import math


def r(qc: QuantumCircuit, control: int, target: int, l: int):
    qc.cp(2*math.pi/(1<<l), control, target)

def qft(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    for i in range(n//2):
        qc.cx(i, n-i-1)
        qc.cx(n-i-1, i)
        qc.cx(i, n-i-1)
    for i in range(0, n):
        qc.h(i)
        for j in range(1, n-i):
            r(qc, i+j, i, j+1)
    return qc

def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    # Write your code here:
    qc = qc.compose(qft(n))

    return qc

B5: Quantum Arithmetic I

この問題はコンテスト中に解くことができました。

問題

www.qcoder.jp

解法

この問題はB6以降のための前座であり、実は難しくありません。
f(x)および指数関数の性質に注目すると、位相シフトゲートを用いてj番目のQubitの位相を\exp\left(2\pi iS_j/2^m\right)ずらせばよいことがわかります。

実装

from qiskit import QuantumCircuit
import math


def solve(n: int, m: int, S: list[int]) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    # Write your code here:
    for i in range(n):
        qc.p(2*math.pi*S[i]/(1<<m), i)

    return qc

B6: Quantum Arithmetic II

問題

www.qcoder.jp

解法

以下のサイトで解説されている位相推定アルゴリズムに注目します。
dojo.qulacs.org
ユニタリ行列Uと量子状態\def\ket#1{\mathinner{\left|{#1}\right\rangle}}\ket{\psi}が与えられ、\ket{\psi}をUの各固有状態\ket{\mathrm{eigen}_l}およびある定数c_lで\ket{\psi}=\sum_l c_l\ket{\mathrm{eigen}_l}と表したとき、\ket{\psi}\ket{0}_mを\ket{\psi}=\sum_l c_l\ket{\mathrm{eigen}_l}\ket{\lambda_l}_mと変換するのが位相推定アルゴリズムです。ここで、\ket{\lambda_l}_mはUの各固有値の位相を2\piで割ってリトルエンディアンの2進m桁で表した小数部分に対応する量子状態です。

さらに、B5で実装したオラクルの固有状態は各\ket{x}で、対応する固有値は\exp\left(2\pi if(x)/2^m\right)であることがわかります。
そして、\ket{\lambda_l}_mは\ket{f(x)\!\!\!\!\mod\! 2^m}_mと等しいこともわかります。

位相シフトゲートを2^k回かけることは1つの位相シフトゲートでできるので、位相推定アルゴリズムの回路を実装すればよいです。
ただし、上のサイトではIQFTを行う前の制御量子ビットが同じサイト内のQFTの定義と逆順に得られているのを強調していないことに注意が必要です。
リトルエンディアンにおけるQFTも、先頭のQubitの位相が0桁左シフトで末尾に向かうにつれて左シフトの桁が1桁ずつ大きくなっていくことに変わりないので、k番目のQubitを使って制御位相シフトゲートを2^k回かけることには変わりはありません。よく理解せずに逆順にしてしまうとハマります。

実装

IQFTはinverse関数を使うと楽です。

from qiskit import QuantumCircuit, QuantumRegister
import math


def r(qc: QuantumCircuit, control: int, target: int, l: int):
    qc.cp(2*math.pi/(1<<l), control, target)

def qft(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    for i in range(n//2):
        qc.cx(i, n-i-1)
        qc.cx(n-i-1, i)
        qc.cx(i, n-i-1)
    for i in range(0, n):
        qc.h(i)
        for j in range(1, n-i):
            r(qc, i+j, i, j+1)
    return qc

def solve(n: int, m: int, S: list[int]) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(m)
    qc = QuantumCircuit(x, y)
    # Write your code here:
    qc.h(y)
    for k in range(m):
        for i in range(n):
            qc.cp(2*math.pi*S[i]/(1<<m)*(1<<k), y[k], x[i])
    qc = qc.compose(qft(m).inverse(), y)

    return qc

B7: Quantum Arithmetic III

問題

www.qcoder.jp

解法

B6で最初に補助量子ビットにHゲートをかけるのはそれが\ket{0}_mのQFTと等価だからなのでした。そこから、HゲートをQFTに変えればよいという予想ができます。
実際、\exp(2\pi i\times 0.j_{m-1}j_{m-2}\ldots j_0)=\exp(2\pi i\times 1.j_{m-1}j_{m-2}\ldots j_0)を考慮すると、指数法則よりHゲートをQFTに変えることで\ket{(y+f(x))\!\!\!\!\mod\! 2^m}_mのQFTが得られることがわかります。

実装

from qiskit import QuantumCircuit, QuantumRegister
import math


def r(qc: QuantumCircuit, control: int, target: int, l: int):
    qc.cp(2*math.pi/(1<<l), control, target)

def qft(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    for i in range(n//2):
        qc.cx(i, n-i-1)
        qc.cx(n-i-1, i)
        qc.cx(i, n-i-1)
    for i in range(0, n):
        qc.h(i)
        for j in range(1, n-i):
            r(qc, i+j, i, j+1)
    return qc

def solve(n: int, m: int, S: list[int]) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(m)
    qc = QuantumCircuit(x, y)
    # Write your code here:
    qft_m = qft(m)
    qc = qc.compose(qft_m, y)
    for k in range(m):
        for i in range(n):
            qc.cp(2*math.pi*S[i]/(1<<m)*(1<<k), y[k], x[i])
    qc = qc.compose(qft_m.inverse(), y)

    return qc

B8: Quantum Arithmetic IV

問題

www.qcoder.jp

解法

B6とB2が解けていればこれはウィニングランでしょう。
全体にB6を適用してから、\ket{f(x)\!\!\!\!\mod\! 2^m}_mにB2を適用し、全体にB6の逆のゲートを適用すればよいです。

実装

from qiskit import QuantumCircuit, QuantumRegister
import math


def r(qc: QuantumCircuit, control: int, target: int, l: int):
    qc.cp(2*math.pi/(1<<l), control, target)

def qft(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    for i in range(n//2):
        qc.cx(i, n-i-1)
        qc.cx(n-i-1, i)
        qc.cx(i, n-i-1)
    for i in range(0, n):
        qc.h(i)
        for j in range(1, n-i):
            r(qc, i+j, i, j+1)
    return qc

def b6(n: int, m: int, S: list[int]) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(m)
    qc = QuantumCircuit(x, y)
    # Write your code here:
    qc.h(y)
    for k in range(m):
        for i in range(n):
            qc.cp(2*math.pi*S[i]/(1<<m)*(1<<k), y[k], x[i])
    qc = qc.compose(qft(m).inverse(), y)

    return qc

def b2(n: int, L: int, theta: float) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    # Write your code here:
    b=[0]*n
    for i in range(n):
        b[i]=L%2
        L//=2
    for i in range(n):
        if b[i]==0:
            qc.x(i)
    if n>1:
        qc.mcp(theta, list(range(n-1)), n-1)
    else:
        qc.p(theta, 0)
    for i in reversed(range(n)):
        if b[i]==0:
            qc.x(i)

    return qc

def solve(n: int, m: int, L: int, S: list[int], theta: float) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(m)
    qc = QuantumCircuit(x, y)
    # Write your code here:
    qc = qc.compose(b6(n, m, S))
    qc = qc.compose(b2(m, L, theta), y)
    qc = qc.compose(b6(n, m, S).inverse())

    return qc

PuLPと制約条件の逐次的な追加で鉄則本の演習問題集のTSPを通す

（AtCoderで典型的なTSPの問題あるかな…？鉄則本のTSPはN≤15, TL10sかよ…多分制約条件の逐次的な追加使わなくても通るけどまあいいや）

はじめに

巡回セールスマン問題は次のような01整数問題として定式化することができます。
\mathrm{minimize}\ \sum_{e\in E}d(e)x_e,\ \mathrm{subject\ to}\ \sum_{j\in V\setminus\lbrace i\rbrace} x_{\lbrace i, j\rbrace}=2\ (\forall i\in V),\ \sum_{{\lbrace i, j\rbrace}\subseteq S} x_{\lbrace i, j\rbrace}\leq |S|-1\ (\forall S\in 2^V\setminus\lbrace\emptyset,V\rbrace)
競プロ界隈で定期的に話題になるPuLPを用いると、鉄則本の演習問題集のB23 - Traveling Salesman Problemは以下のように解くことができます。

from math import dist
from itertools import combinations
from pulp import LpProblem, LpVariable, LpBinary, LpMinimize, lpSum, PULP_CBC_CMD

n=int(input())
x=[0.]*n
y=[0.]*n
for i in range(n):
    x[i],y[i]=(float(x) for x in input().split())

var=LpVariable.dicts("var", [(i, j) for i in range(n) for j in range(i+1, n)], 0, 1, LpBinary)
prob=LpProblem("prob", LpMinimize)

prob+=lpSum([dist((x[i], y[i]), (x[j], y[j]))*var[(i, j)] for i in range(n) for j in range(i+1, n)])

for i in range(n):
    prob+=lpSum([var[(j, i)] for j in range(i)])+lpSum([var[(i, j)] for j in range(i+1, n)])==2

for k in range(2, n-1):
    for comb in combinations(list(range(n)), k):
        lcomb=list(comb)
        prob+=lpSum([var[(lcomb[i], lcomb[j])] for i in range(k) for j in range(i+1, k)])<=k-1

prob.solve(PULP_CBC_CMD(msg=False))

print(prob.objective.value())

ただし、制約条件の個数が\Theta(2^N)になってしまうため、とても遅いです。
この問題はN≤15, TL10sなので通りますが、実行時間もメモリもギリギリでしょう。

制約条件の逐次的な追加

（正式名称がわかりません…切除平面法とは違うと思いますが…）

参考: http://dopal.cs.uec.ac.jp/okamotoy/lect/2022/ip/lect10.pdf
線形計画問題や整数計画問題について、一部の制約条件のみについての問題の最適解が全ての制約条件を満たす場合、明らかにその解は全ての制約条件についての問題の最適解でもあります。
また、巡回セールスマン問題においては得られた解が部分巡回路を持たないかどうかはDFSやUnion-Findで容易に求めることができます。

そこで、部分巡回路除去制約を持たない問題を最初に解き、得られた部分巡回路を除去する制約を追加して問題を解くことを繰り返せば、より高速になることが期待されます。

上のソースコードを書き換えると、以下のようになります。

from math import dist
from pulp import LpProblem, LpVariable, LpBinary, LpMinimize, lpSum, PULP_CBC_CMD
from atcoder.dsu import DSU

n=int(input())
x=[0.]*n
y=[0.]*n
for i in range(n):
    x[i],y[i]=(float(x) for x in input().split())

var=LpVariable.dicts("var", [(i, j) for i in range(n) for j in range(i+1, n)], 0, 1, LpBinary)
prob=LpProblem("prob", LpMinimize)

prob+=lpSum([dist((x[i], y[i]), (x[j], y[j]))*var[(i, j)] for i in range(n) for j in range(i+1, n)])

for i in range(n):
    prob+=lpSum([var[(j, i)] for j in range(i)])+lpSum([var[(i, j)] for j in range(i+1, n)])==2

unfinished=True

while unfinished:
    prob.solve(PULP_CBC_CMD(msg=False))

    unfinished=False
    cnt=0
    g=DSU(n)
    for i in range(n):
        for j in range(i+1, n):
            if var[(i, j)].value()==1:
                cnt+=1
                if cnt<n and g.same(i, j):
                    s=list(filter(lambda v: g.same(v, i), list(range(n))))
                    prob+=lpSum([var[(s[i], s[j])] for i in range(len(s)) for j in range(i+1, len(s))])<=len(s)-1
                    unfinished=True
                g.merge(i, j)

print(prob.objective.value())

特にCPythonでの提出において、実行時間もメモリもより良い結果になっています。


おわりに

このテクニックが使える類題を見つけて解こうと思ったのですが、数時間探して見つからなかったのでやけくそでこの記事を締めます笑
いかがでしたか？笑

【ネタ】動的木とカラバのアルゴリズムで最小全域木の辺の重みの総和を求める

カラバのアルゴリズム

カラバのアルゴリズム (Kalaba's Algorithm)とは、以下のように最小木問題を解くアルゴリズムです。

  • 適当な全域木をとる。
  • 最初にとった全域木に含まれない辺について、適当な順序で順に以下の操作を行う。
    • 注目する辺を全域木に追加する。
    • できた閉路（基本閉路）をなす辺で最も重みが大きい辺をとる。
    • とった辺を全域木から削除する。

組み合わせ最適化問題の文脈で、最小木問題をM凸関数の最小化と見ることで自然に導かれる貪欲アルゴリズムのようです。（私は講義で最小木問題のアルゴリズムの1つとして知っただけなので詳しくはありません。）

単純であるため一瞬これから使おうと思いましたが、冷静に考えてみるとオンラインで木の形状の変更を行いパスクエリを解かなければならないことからクラスカル法・プリム法・ブルーフカ法などと異なり容易に時間O(|E|\log|V|)を達成することが難しいです。
実用性よりも理論として重要ということでしょうか。

Link Cut Treeなどの動的木を用い、辺を表す頂点を追加した(|V|+|E|)頂点の森に対して辺の追加や削除とパスクエリを行えばならしO(|E|\log|V|)が達成できます。
動的木を自分で書かなければそこまで実装量が多いわけでもないので書きました。

ソースコード (C++)

Luzhiled's LibraryのLink Cut Treeを使用しました。

#include <algorithm>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

template <typename TreeDPInfo>
struct LinkCutTree {
  using Path = typename TreeDPInfo::Path;
  using Info = typename TreeDPInfo::Info;

 private:
  struct Node {
    Node *l, *r, *p;

    Info info;

    Path sum, mus;

    bool rev;

    bool is_root() const { return not p or (p->l != this and p->r != this); }

    Node(const Info &info)
        : info(info), l(nullptr), r(nullptr), p(nullptr), rev(false) {}
  };

 public:
  using NP = Node *;

 private:
  void toggle(NP t) {
    swap(t->l, t->r);
    swap(t->sum, t->mus);
    t->rev ^= true;
  }

  void rotr(NP t) {
    NP x = t->p, y = x->p;
    push(x), push(t);
    if ((x->l = t->r)) t->r->p = x;
    t->r = x, x->p = t;
    update(x), update(t);
    if ((t->p = y)) {
      if (y->l == x) y->l = t;
      if (y->r == x) y->r = t;
    }
  }

  void rotl(NP t) {
    NP x = t->p, y = x->p;
    push(x), push(t);
    if ((x->r = t->l)) t->l->p = x;
    t->l = x, x->p = t;
    update(x), update(t);
    if ((t->p = y)) {
      if (y->l == x) y->l = t;
      if (y->r == x) y->r = t;
    }
  }

 public:
  LinkCutTree() = default;

  void push(NP t) {
    if (t->rev) {
      if (t->l) toggle(t->l);
      if (t->r) toggle(t->r);
      t->rev = false;
    }
  }

  void push_rev(NP t) {
    if (t->rev) {
      if (t->l) toggle(t->l);
      if (t->r) toggle(t->r);
      t->rev = false;
    }
  }

  void update(NP t) {
    Path key = TreeDPInfo::vertex(t->info);
    t->sum = key;
    t->mus = key;
    if (t->l) {
      t->sum = TreeDPInfo::compress(t->l->sum, t->sum);
      t->mus = TreeDPInfo::compress(t->mus, t->l->mus);
    }
    if (t->r) {
      t->sum = TreeDPInfo::compress(t->sum, t->r->sum);
      t->mus = TreeDPInfo::compress(t->r->mus, t->mus);
    }
  }

  void splay(NP t) {
    push(t);
    while (not t->is_root()) {
      NP q = t->p;
      if (q->is_root()) {
        push_rev(q), push_rev(t);
        if (q->l == t)
          rotr(t);
        else
          rotl(t);
      } else {
        NP r = q->p;
        push_rev(r), push_rev(q), push_rev(t);
        if (r->l == q) {
          if (q->l == t)
            rotr(q), rotr(t);
          else
            rotl(t), rotr(t);
        } else {
          if (q->r == t)
            rotl(q), rotl(t);
          else
            rotr(t), rotl(t);
        }
      }
    }
  }

  NP expose(NP t) {
    NP rp = nullptr;
    for (NP cur = t; cur; cur = cur->p) {
      splay(cur);
      cur->r = rp;
      update(cur);
      rp = cur;
    }
    splay(t);
    return rp;
  }

  void link(NP child, NP parent) {
    if (is_connected(child, parent)) {
      throw runtime_error(
          "child and parent must be different connected components");
    }
    if (child->l) {
      throw runtime_error("child must be root");
    }
    child->p = parent;
    parent->r = child;
    update(parent);
  }

  void cut(NP child) {
    expose(child);
    NP parent = child->l;
    if (not parent) {
      throw runtime_error("child must not be root");
    }
    child->l = nullptr;
    parent->p = nullptr;
    update(child);
  }

  void evert(NP t) {
    expose(t);
    toggle(t);
    push(t);
  }

  NP alloc(const Info &v) {
    NP t = new Node(v);
    update(t);
    return t;
  }

  bool is_connected(NP u, NP v) {
    expose(u), expose(v);
    return u == v or u->p;
  }

  vector<NP> build(vector<Info> &vs) {
    vector<NP> nodes(vs.size());
    for (int i = 0; i < (int)vs.size(); i++) {
      nodes[i] = alloc(vs[i]);
    }
    return nodes;
  }

  NP lca(NP u, NP v) {
    if (not is_connected(u, v)) return nullptr;
    expose(u);
    return expose(v);
  }

  void set_key(NP t, const Info &v) {
    expose(t);
    t->info = std::move(v);
    update(t);
  }

  const Path &query_path(NP u) {
    expose(u);
    return u->sum;
  }

  const Path &query_path(NP u, NP v) {
    evert(u);
    return query_path(v);
  }

  template <typename C>
  pair<NP, Path> find_first(NP u, const C &check) {
    expose(u);
    Path sum = TreeDPInfo::vertex(u->info);
    if (check(sum)) return {u, sum};
    u = u->l;
    while (u) {
      push(u);
      if (u->r) {
        Path nxt = TreeDPInfo::compress(u->r->sum, sum);
        if (check(nxt)) {
          u = u->r;
          continue;
        }
        sum = nxt;
      }
      Path nxt = TreeDPInfo::compress(TreeDPInfo::vertex(u->info), sum);
      if (check(nxt)) {
        splay(u);
        return {u, nxt};
      }
      sum = nxt;
      u = u->l;
    }
    return {nullptr, sum};
  }
};

struct TreeDPInfo {
    struct Path { long long max_weight; int idx; };
    struct Info { long long weight; int idx; };
    static Path vertex(const Info & u) { return {u.weight, u.idx}; };
    static Path compress(const Path& p, const Path& c) {
        if(p.max_weight>c.max_weight){
            return p;
        } else {
            return c;
        }
    };
};

struct Edge {
    int to, idx;
};

int main(void) {
    int n,m;
    cin >> n >> m;
    vector<int> a(m);
    vector<int> b(m);
    vector<long long> c(m);
    LinkCutTree<TreeDPInfo> lct;
    vector g(n, vector<Edge>());
    vector<TreeDPInfo::Info> vs(n+m);
    for(int i=0;i<n;++i){
        vs[i]={0, m};
    }
    for(int i=0;i<m;++i){
        cin >> a[i] >> b[i] >> c[i];
        --a[i];
        --b[i];
        g[a[i]].emplace_back(Edge{b[i], i});
        g[b[i]].emplace_back(Edge{a[i], i});
        vs[n+i]={c[i], i};
    }
    auto vertices=lct.build(vs);
    long long ans=0;
    stack<int> st;
    vector<bool> seen(n);
    vector<bool> used(m);
    st.emplace(0);
    seen[0]=true;
    while(!st.empty()){
        int v=st.top();
        st.pop();
        for(auto [u, i]: g[v]){
            if(!seen[u]){
                lct.evert(vertices[n+i]);
                lct.link(vertices[n+i], vertices[v]);
                lct.evert(vertices[n+i]);
                lct.link(vertices[n+i], vertices[u]);
                st.emplace(u);
                seen[u]=true;
                used[i]=true;
                ans+=c[i];
            }
        }
    }
    for(int i=0;i<m;++i){
        if(used[i]){
            continue;
        }
        int e=lct.query_path(vertices[a[i]], vertices[b[i]]).idx;
        if(c[i]<c[e]){
            lct.evert(vertices[n+e]);
            lct.cut(vertices[a[e]]);
            lct.evert(vertices[n+e]);
            lct.cut(vertices[b[e]]);
            ans-=c[e];
            lct.evert(vertices[n+i]);
            lct.link(vertices[n+i], vertices[a[i]]);
            lct.evert(vertices[n+i]);
            lct.link(vertices[n+i], vertices[b[i]]);
            ans+=c[i];
        }
    }
    cout << ans << endl;
    return 0;
}

提出 (鉄則A67)

普通に定数倍が重くて遅いです笑
atcoder.jp

感想

普通にクラスカル法かプリム法かブルーフカ法が書ければよくね？

【メドレー無茶振り合作2】「とにかく面白いメドレーを作って！」って何！？！？！？！？【制作後記】

こんにちは、獅子座じゃない人です！
メドレー無茶振り合作2に参加しました！
www.nicovideo.jp
www.nicovideo.jp
www.nicovideo.jp
www.nicovideo.jp

ウケるに配置されていました。
正直、サブタイトルが発表された時点でウケるに入っているだろうと予想していました。

制作時に考えていたことなどを、つらつらと書いていこうと思います。
この記事は、面白さよりもまともなことが中心になりそうです。

制作に取り掛かるまで

2月頭に無茶振りが振り分けられたとき、正直困惑してしまいました。
まず、初代メドレー無茶振り合作では縛り系の無茶振りが多く、私に来たお題もそうでした。
なので、今回もほとんど縛り系の無茶振りが来るだろうと思っていました。

そして、よりにもよってこの私に「とにかく面白いメドレーを作って！」を振ったことも正直理解できず、もっと適任がいっぱいいるだろうと思ってしまいました。俺が面白いわけないだろ

「とにかく面白いメドレーを作って！」という書き方が2段くらい難しさをさらに上げていると思います。「面白いと自分で思えるメドレーを作って！」ならばまだマシでした。
どういうことかというと、「とにかく」という言葉から面白さで畳みかけないといけないという印象を感じ、「面白い」とだけ書かれていることから主観的にではなく客観的に面白くなって初めて無茶振り達成という印象を感じました。

リアルタスクや他の合作、他の趣味など他にやることも多かったため、少しだけ取り組んで没にしてを繰り返すだけで、4月中旬まで進捗が本当に0でした。

とりあえずの進捗提出

4月に入ったあたりで、「とにかく」面白いメドレーについて改めて分析しつつ、主観的にちゃんと面白いと思えるメドレーを作って初めて客観的にも面白いメドレーを作れると考えました。
そこで、ニコニコメドレーで自分が面白いと思える技法やネタを詰め合わせようという結論に至りました。
また、ゲテモノみたいな面白いものは終盤だけ入れようということも考えました。
結果的には、3分という制限が短すぎてネタ要素が多くなってしまいましたが。

そのとき考えたネタをリストにし、とりあえずの進捗として提出しました。
そのリストはここには書きません。結果的には使えたネタが一番面白かったと思うので。

制作スタート

結局、大学の新生活に慣れるなどの理由でGWまで実際に取り組むことはできませんでした。
そして、GWに取り組み始めました。

取り組む前に使う曲・ネタと構成はほとんど決めていたので、音源・動画ともにGW中に終わらせられたはずです。

それぞれの曲について、軽く解説していこうと思います。

1. おもちゃの兵隊の観兵式

「ニコニコメドレーシリーズに使用された曲の一覧」の『おもちゃの兵隊の観兵式』はだいたい「キューピー3分クッキング」でいいよねという話を見て、じゃあ逆に本当の意味で『おもちゃの兵隊の観兵式』を打ち込もうと考えました。
クラシックの楽譜をまとめているIMSLPがとても役に立ちました。

ずっとピアノソロだと次の曲に繋げにくいため、後半はいつも通りのアレンジに戻しました。

2. Bling-Bang-Bang-Born, 3. (ミャンマー版Bling-Bang-Bang-Born)

あえて「(ミャンマー版Bling-Bang-Bang-Born)」としているのは、動画中の曲名とユニット名が正しい自信が本当にないからです。
翻訳結果をもとにこれが曲名でこれがユニット名だろうと適当にあたりをつけました。

この曲を知ったきっかけは、大学のDTMサークルの作曲に関する講義で「リファレンスに寄せすぎてしまったオリジナル曲」の例として挙げられていたことです。オリジナル曲なのに24小節共通音とはたまげたなぁ

これだけ一致しているならいっそ原曲のボーカルを入れてクロスしてしまおうと考えました。
打ち込みメドレーで一部だけ原曲のボーカルが入るの、好きなんですよね。やれてよかった。

映像が二重に大変でした。
クロスはKANONさんのプログラムがあるものの、それだと生成されるオブジェクトが640×360用になってしまうため、自力でなるべく再現しました。
そして、ビルマ語は日本語でいうShift-JISのように独自に文字コードが浸透してしまったのもあり、なかなか対応するおしゃれなフォントが少ないという点も苦労しました。
そのうえ、Google Fontsで対応するゴシック体を見つけたものの、今度はAviUtlが合字に上手く対応できないという点にハマりました。
結局、aviutl_browserを使ってAviUtl上でインターネットブラウザを動かし、そこで文字を表示するという本当に本末転倒なことをしました。

2. Bling-Bang-Bang-Born, 3. (ミャンマー版Bling-Bang-Bang-Born), 4. POP TEAM EPIC

豆知識：OPとしての『POP TEAM EPIC』は普通に「ポップチームエピック」と読む

打ち込みメドレーで一部だけ原曲のボーカルが入るのが好きとさっき言いましたが、さらに原曲のボーカルと打ち込みのメロディが重なるのも好きなんですよね。やれてよかった。

後半はクロス檄風にするというのは決めていました。
映像が大変でした。

5. メドレー無茶振り合作2 獅子座じゃない人パート

駆け合作FINALの先行公開がウケていたので、このパート自体を入れるのもウケるだろうと入れました。
もちろん先行公開の形にしています。

次のネタの前座として一応クイズ形式に。

一応曲名を字幕に入れないといけないので、早めにどう表記していいかは運営と相談していました。

6.～18. (カオスゾーン)

順不同がやりたかっただけ。
カオスゾーンと一緒にやっちゃったのであまり触れられなかったものの。

ちゃんと順不同にできる完全な共通音を探すのが大変で、結局駆け合作4から引用。
次のシルエットは、もったいないとらんどからのリズムのずれた共通音のつもりです。

他の曲は、一応クイズ形式なのでわかりやすいようにしもメド皆勤賞とFLAG四天王にしました。

19. 【メドレータンピン】ニコニコ動画七対子, 20. （あの…陰キャなんで…リアル麻雀は…許してください…）

存在しない曲メドレー合作から丸ごと引用。
プロジェクトファイルも流用して移調だけしているはずです。

これは存メドの制作後記にも書きましたが
メドレータンピン←単品とタンピンをかけている
ニコニコ動画七対子←ニコニコと七対子をかけている
音MAHJONG合作←音○○に寄せ、MADとMAHJONGが頭2文字一致しているのを利用
対々和全裸待機P←裸単騎と全裸待機をかけている、そして麻雀についてのメドレーを対々和裸単騎するような人が作ってたら面白そうという理由もあり、タンピン、七対子、対々和と違う面子構成の手役を登場させている
と結構な言葉遊びをしているものの、なかなか通じなくて悲しいという。

これで、ニコメドに自分の声を使ったのは3回目になりました。
インターネットリテラシーがなさすぎる。

21.～38. (雀魂)

リアル麻雀はしませんがネット麻雀ならします(?)

これが上で言ったゲテモノ枠。
考えていたゲテモノ枠のなかで唯一音楽ですらなくなるものなので、それが逆にウケにつながったかもしれません。

曲じゃないものに曲名と曲番号がついてたら絶対面白いからね。

普通麻雀でこういうことをするなら、国士無双や大三元みたいな役満ですると思うのですが、自分が麻雀を好きすぎてダブ東チャンタ三色とかいう玄人すぎる手役を選んでしまいました。

この局を選んだ理由は、無茶振り合作関係なく段位戦打っててこれがアガれて爽快だったからです。
こんな誰でもアガれるダマ親跳、爽快じゃないわけがない。
そういう理由で選んでいるので、実際のプレイ中の画面ではなくリプレイ画面になっています。
まあプレイ中の画面だったら同じ巡数でも時間長くなるだろうし、これでいいでしょう。

映像の字幕のタイミング調整や配置の調整が大変で、かなり妥協しました。

39. 【Disc2】M14：Daydream Café?／Petit Rabbit’s

雀魂で終わるのは流石に迷惑すぎるので、最後はまともに締めようと考えていました。
そのほうが面白いと思いますしね。

このバージョン、たまたまYouTubeで聞いて初見めちゃくちゃびっくりしたのですが、今じゃこのバージョンじゃないと満足できないです。

全体構成について

ピアノソロ→シンセアレンジ→シンセアレンジ＋原曲ボーカル→チップチューン→シンセアレンジ→ただの動画→ストリングスと地味にアレンジがコロコロ変わるので、マスタリングしにくい音源だったのではないでしょうか…。また、前後の繋ぎを考えるのも苦労するような始まりと終わりだったと思います。
それにもかかわらず、ちゃんと仕上げてもらって運営の皆さんには感謝です。

また、エンJさんパートと2動画離してくれたり、VubbleStarさんパートより前に配置してくれたり、サブタイトルをウケるにしてくれたり、全体構成のせいでスベるということがないように最大限配慮してくれているように感じました。とてもありがたかったです。

改めて、運営の皆さん、ありがとうございました。

私の出した無茶振り

「全ての使用曲について、既存のニコニコメドレーや音MADなどによるメロディ改変を取り入れて！」でした！
記事口授さんありがとうございます！
ニコメドや音MADについての知見が深い記事口授さんらしい納得のいく選出で、「これこれ！」と思いながら聴いていました。

他のパートも良いパートだらけですごかったですね。
視聴者としてもとても楽しめました。

では、ここら辺で。やっぱり方向性が決まっているメドレー合作は楽しいですね。