くるのプログラミング記録

プログラミングの感想とか解説とか。

yukicoder contest 229 解説

writer: くる / ningenMe
解説です。

A - Omiyage

https://yukicoder.me/problems/2842
部分和{\displaystyle dp}を行い、使えるお金のうち{\displaystyle K}以下の最大値を求めます。
{\displaystyle dp_{i,j}: i}番目の国まで訪れて{\displaystyle 1}つずつおみやげを買ったときに{\displaystyle j}円使えるかどうか。
これは計算量 {\displaystyle O(NMK)}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/391792










B - Plus Or Multiple Operation

https://yukicoder.me/problems/3389
まず {\displaystyle C=1}のときは{\displaystyle A}を作ることができません。その他の場合では必ず{\displaystyle A}を作ることができます。
{\displaystyle C}進展開を考えます。{\displaystyle C}進数で{\displaystyle M}桁(0-indexed)であるとき {\displaystyle A=D_MC_M+D_{M−1}C_{M−1}+… +D_1C+D_0,\ 0 \le D_j < C\ (0 \le j \le M)}と書けます。
ここで{\displaystyle C}倍する操作は{\displaystyle C}進数において{\displaystyle 1}桁シフトする操作、{\displaystyle i\ (0 < i < C)}を足す操作は{\displaystyle 0}桁目に{\displaystyle i}を足す操作に言い換えることができます。
よって桁の大きい方から「和の操作」によって数字を揃え、「積の操作」によって桁を上げることを貪欲に繰り返すことで、最適なコストで数{\displaystyle A}を作ることができます。
ただし最初の{\displaystyle 2}回の操作に関しては、和の操作で起きる繰上りにより桁シフトを行うことができ、この場合の方がコストが少ないときがあります。
具体的には{\displaystyle D_MC+D_{M-1}}と{\displaystyle 2C-2}の大小関係によってこのコストが変化します。
1クエリあたり{\displaystyle \log{A}/\log{C}}で計算することができるため、全体として計算量{\displaystyle O(Q \log{A}/\log{C})}で解くことができます。

【補足】
上記の操作が最適なことに関しての補足を以下に記します。(主にテスターのtpyneriverさんが証明してくれました、ありがとうございます)
数xにする最小手順を{\displaystyle f(x)}とすると以下が成り立ちます。

(1)
{\displaystyle f(0)=0}
{\displaystyle f(x)=1 \ (0 < x < C)}

(2)
{\displaystyle f(x)=\min{(f(x−1),f(x−2)…f(x−C+1))}+1 \ (C \le x,\ x\equiv\begin{eqnarray} i \bmod C\end{eqnarray}, 0 < i < C) }
{\displaystyle f(x)=\min{(f(x−1),f(x−2)…f(x−C+1), f(x/C))}+1 \ (C \le x,\ x\equiv\begin{eqnarray} 0 \bmod C\end{eqnarray} ) }

(3)
{\displaystyle f(Cx)=f(x)+1 \ (0 < x)}

{\displaystyle x=k \ (0 < k)}のとき{\displaystyle f(Ck)=f(k)+1 \ (0 < x)}が成り立つと仮定する
{\displaystyle x=k+1}のとき{\displaystyle f(C(k+1)) < f(k+1)+1}とすると(2)より{\displaystyle f(C(k+1)-i)+1= f(C(k+1)) \ (0 < i < C)}なる{\displaystyle f(Cx)=i}が存在する。
また{\displaystyle f(C(k+1)-i-j)+1=f(C(k+1)-i) \ (0 < j < C)}なる{\displaystyle j}が存在する。
これらより{\displaystyle f(C(k+1)-y)+2=f(C(k+1)) \ (C < y < 2C-2)}なる{\displaystyle y}が存在する。
ここで{\displaystyle C(k+1)-y \le Ck}であることと(2)より
{\displaystyle f(Ck) \le f(C(k+1)−y)+1=f(C(k+1))−1}が成立するので{\displaystyle f(k)+1\le f(C(k+1))−1 < f(k+1)}が成立。
しかし(2)より{\displaystyle f(k+1)\le f(k)+1}なので矛盾する。
よって{\displaystyle x=k (0 < k)}で{\displaystyle f(Ck)=f(k)+1}が成り立つとき{\displaystyle x=k+1}で{\displaystyle f(k+1)+1\le f(C(k+1))}が成立。
また(2)より常に{\displaystyle f(Cx) \le f(x)+1}であることから{\displaystyle f(k+1)+1\le f(C(k+1))\le f(k+1)+1} となり{\displaystyle f(C(k+1))=f(k+1)+1}が成立。

以上より{\displaystyle f(Ck)=f(k)+1}が成り立つとき{\displaystyle f(C(k+1))=f(k+1)+1}が成り立ち、{\displaystyle f(C)=2=f(1)+1}より{\displaystyle 0 < x}のとき常に{\displaystyle f(Cx)=f(x)+1}が成り立つ。

(4)
{\displaystyle f(Cx+i)=f(Cx)+1 \ (1 < x, 0 < i < C)}

{\displaystyle x=k \ (1 < k)}で{\displaystyle f(Ck+i)=f(Ck)+1}が成立すると仮定する。
まず{\displaystyle f(C(K+1)+1) \ (0 < j < C)}について、{\displaystyle C(k+1)+1}が{\displaystyle C}の倍数でないので(2)より
{\displaystyle f(C(k+1)+1)=\min{(f(C(k+1),f(Ck+i))}+1=\min{(f(C(k+1)),f(Ck)+1)}+1=\min{(f(C(k+1)),f(k)+1)}+1=f(C(k+1))+1}
同様に{\displaystyle j=2,…,C−1}で{\displaystyle f(C(k+1)+j)=f(C(k+1))+1}が成立。
よって{\displaystyle x=k}で{\displaystyle f(Ck+i)=f(Ck)+1 \ (0 < i < C)}が成立するとき{\displaystyle x=k+1}で{\displaystyle f(C(k+1)+j)=f(Ck)+1 \ (0 < j < C)}が成立する。
{\displaystyle f(2C+i)=f(2C)+1 \ (0 < i < C)}が成立するので、{\displaystyle 1 < x}で(4)は成立する。


以上より最適手順として
{\displaystyle f(0)=0}
{\displaystyle f(x)=1 \ (1 \le x < C)}
{\displaystyle f(x)=2 \ (C \le x < 2C-1)}
{\displaystyle f(x)=f(x/C)+1 \ (2C-1 \le x,\ x\equiv\begin{eqnarray} 0 \bmod C\end{eqnarray} )}
{\displaystyle f(x)=f(x - {\begin{eqnarray} x \bmod C\end{eqnarray}})+1} {\displaystyle (2C-1 \le x,\ x\equiv\begin{eqnarray} i \bmod C\end{eqnarray},\ (0 < i < C) )}

と遷移がわかる。

writer解はこちら。
https://yukicoder.me/submissions/392103









C - Encounter On A Tree

https://yukicoder.me/problems/2827
「すべての{\displaystyle i,j}について、頂点{\displaystyle i}の深さが頂点{\displaystyle j}の深さよりも大きいならば、頂点{\displaystyle i}に書き込まれる番号は頂点{\displaystyle j}に書き込まれる番号より大きい」という条件から深さ{\displaystyle d}の頂点に書き込まれるような数字の候補の集合を{\displaystyle s_d}とすると、{\displaystyle s_1=\{1\},s_2=\{2,3\},s_3=\{4,5,6,7\},…,s_d=\{2^{d-1},…,2^d−1\},…}となります。
よってある数字が書きこまれるとき、その頂点の深さは一意に決まることが分かります。

{\displaystyle l, r}が書き込まれた頂点の深さをそれぞれ{\displaystyle d_l, d_r}とし、また{\displaystyle l, r}が書き込まれた頂点の{\displaystyle lca}(最小共通祖先)の頂点の深さを{\displaystyle d_{lca}}とします。
長さ{\displaystyle k}のパスが存在する場合{\displaystyle k=d_l+d_r−2d_{lca}}かつ{\displaystyle d_{lca}≤d_l}が成り立ちます。
このような{\displaystyle lca}である頂点の候補は{\displaystyle 2^{d_{lca}-1}}通りあり、その1つの{\displaystyle lca}に対して{\displaystyle l}が書き込まれるような数字の候補は「{\displaystyle lca}の子を根とする部分木」を考えると{\displaystyle 2^{d_l-d_{lca}-1}}通りあります。
同様に{\displaystyle r}が書き込まれるような数字の候補は{\displaystyle 2^{d_r-d_{lca}-1}}通りあります。
また{\displaystyle lca}の子は左右の2通りがあるため、パスの長さが{\displaystyle k}となるような{\displaystyle l, r}の書き込み方は{\displaystyle 2^{d_{lca}-1}×2^{d_l-d_{lca}-1}×2^{d_r-d_{lca}-1} ×2}通りとなります。
残りの{\displaystyle l, r}以外の書き込み方に関しては、各深さごとに独立に候補の数字の順列を考えればよく、これは簡単に計算できます。

実装の際は{\displaystyle d_l=d_{lca}}となる場合のコーナーケースに注意してください。
全体として計算量{\displaystyle O(2^d)}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392120












D - Make One With GCD

https://yukicoder.me/problems/3305
愚直に全探索をすると{\displaystyle 2^N}通りの場合があり、とても間に合いません。そこで {\displaystyle dp}を行います。
{\displaystyle dp[i][j]: A_1}から見ていって最後に{\displaystyle A_i}を使って最大公約数が{\displaystyle j}になるような場合の数。
ここで{\displaystyle j}に関してですが、{\displaystyle \max{A}≤10^8}なので愚直に状態を持つと空間計算量、時間計算量ともに制約をオーバーしてしまいます。
しかし{\displaystyle A_i}を用いた最大公約数は必ず{\displaystyle A_i}の約数となり、{\displaystyle 10^8}以下の数字の約数の個数は高々{\displaystyle 768}個であることから無駄な状態を減らすことで十分高速に計算できます。

{\displaystyle 1}つの状態に対して遷移が{\displaystyle O(N)}個あるので、{\displaystyle x}以下の数字の約数の個数の最大値を{\displaystyle d_{max}(x)}とすると、計算量 {\displaystyle O(\ N^2d_{max}(A)( \log{\max{A}}+\log{d_{max}(A)})\ )}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392116













E - LISGRID

https://yukicoder.me/problems/3092
最初に数列{\displaystyle A}と{\displaystyle B}を昇順にソートします。
そして各行、各列において「前半は単調減少な数列、後半は単調増加な数列」になるように数列を構築することを考えます。ここで単調増加な部分に関しては題意の条件を満たすようにします。

するとこのとき、各マスにおける隣接マスとの大小関係が決まります。
この大小関係を有向辺とみなすことでトポロジカル順序が決まるため数字を矛盾なく書き込むことができます。トポロジカルソートしたときのスタートの候補となる頂点は最大でも{\displaystyle (1,1),(1,W),(H,1),(H,W)}の4つが存在しますが、{\displaystyle (1,1)}を最初にスタートとして{\displaystyle H*W}から順に書き込み、最後に{\displaystyle (H,W)}をスタートとして用いることで問題の条件に合うグリッドを構築することができます。

ソートと書き込み時の探索を考慮すると、計算量 {\displaystyle O(\ H\log{H}+W\log{W}+HW\ )}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392115











F - You Are A Project Manager

https://yukicoder.me/problems/3227

{\displaystyle K}を決め打ちすることを考えます。
すると左右からぞれぞれ{\displaystyle K}の倍数だけプログラマを選ぶ操作としてみなすことができるので、そのときの区間の中央値の塁積和を前計算しておくことで左から{\displaystyle L}チーム、右から{\displaystyle R}チーム作ったときの行動力の最大値を求める問題になります。

またこの値は塁積和をとった値に対してさらに累積maxをとることで、{\displaystyle L,R}の分割を決める位置を探索することに言い換えれます。

{\displaystyle K=1,2,......N}と動かしたときに、中央値を求める区間の数に関しては調和級数的に状態が小さくなるため、全体で{\displaystyle O(N\log{N})}個になります。

よってこの{\displaystyle O(N\log{N})}個の区間の中央値が分かると、{\displaystyle K}について全探索することでこの問題が解けます。

すなわち区間の大きさ{\displaystyle O(N)}、クエリ数{\displaystyle O(N\log{N})}で区間の中央値をオフラインで答える問題に言い換えることができました。

この中央値を愚直に求めると計算量が{\displaystyle O( Σ (N/K) K\log{K}) = O( N^2\log{N})}となりとても間に合いません。
しかし区間を平方分割し、Mo's Algorithmを利用することで区間を伸縮させながら高速に中央値を求めることができます。
区間の伸縮の際は(c++における)multisetを2本持つことで、{\displaystyle O(\log{N})}で中央値を管理することができます。

よって必要な区間の中央値を{\displaystyle O(N\sqrt{N}(\log{N})^2)}で求めることができます。

また全体としても計算量{\displaystyle O(N\sqrt{N}(\log{N})^2)}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392113