かんプリンの学習記録

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

ABC259 G - Grid Card Game

問題はこちら

問題概要

{H\times W}枚のカードがグリッド上に並んでおり，{(i,j)}にあるカードには{A_{i,j}}が書かれている．{H}行からいくつか選び，選んだカードの上に赤いトークンを置く．{W}列からいくつか選び，選んだカードの上に青いトークンを置く．その後，トークンが置かれているカードに書かれた整数の和が得点となる．ただし，赤いトークンと青いトークンがともに置かれているカードであって，書かれている整数が負であるものが存在する場合，得点は{-10^{100}}となる．
得点としてあり得る最大値を求めよ．

  • {1\leq H,W\leq 100}
  • {-10^9 \leq A_{i,j}\leq 10^9}

解説

行{i}または列{j}を選ぶと{A_{i,j}}点を得ます．これを「行{i}を選ぶと{A_{i,j}}点を得る」，「列{j}を選ぶと{A_{i,j}}点を得る」，「行{i}と列{j}をともに選ぶと{A_{i,j}}点を失う」と考えることにすると，選択間にコストがかかる問題となり，Project Selection Problem(燃やす埋める問題)と同じく最小カットを求める問題に帰着させることができます．

選択間にかかるコストを表にしてみます．

{A_{i,j} > 0}の場合，このままだと上手くグラフを作れないので行の選択の順番を変更してみます．ちなみに，選択間のコストは行と列の間にしかかからないためこの変更を行うことができます．

{A_{i,j} < 0}の場合も同様にして以下のコストがかかることが分かります．

グラフの構築

ここからは実際にグラフを構築していきます．最小カットに対応させるため，行/列に対応する頂点および始点{S}・終点{T}を用意します．行{i}を選ぶことと頂点を{T}側集合に含めることに対応させ，列{j}を選ぶことと頂点を{S}側集合に含めることに対応させると

  • 行{i}を選ぶと{A_{i,j}}点を得る{\longrightarrow} 行{i}に対応する頂点を{S}側集合に含めるとコストが{-\sum_{i=1}^{W}A_{i,j}}かかる．
  • 列{j}を選ぶと{A_{i,j}}点を得る{\longrightarrow} 列{j}に対応する頂点を{T}側集合に含めるとコストが{-\sum_{j=1}^{H}A_{i,j}}かかる．
  • 行{i}と列{j}をともに選ぶと{A_{i,j}}点を失う{\longrightarrow} 行{i}に対応する頂点を{S}側集合に，列{j}に対応する頂点を{T}側集合に含めるとコストが{A_{i,j}} ({A_{i,j} < 0}の場合{\infty})かかる．

となるため，これをもとにグラフが構築できます．

このグラフの最小カットが答えとなります．
また，{-\sum_{i}A_{i,j}}および{-\sum_{j}A_{i,j}}が負の場合は以下の記事の様に負辺除去をすれば良いです．

kanpurin.hatenablog.com

頂点数は{O(H+W)}，辺数は{O(HW)}であるので計算量{O((H+W)^2HW)}で解くことができます．

Project Selection Problem(燃やす埋める問題)に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

Project Selection Problem(燃やす埋める問題)の他の問題は以下にまとめているので参考にしてください．
kanpurin.hatenablog.com

提出プログラム

https://atcoder.jp/contests/abc259/submissions/34424274

感想

燃やす埋める練習問題３

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

燃やす埋める(Project Selection Problem)の練習問題についての解説です。

問題はこちら

ポイント

  • 負のコスト
  • 複数の選択肢
  • 機械的なグラフの構築

問題概要

{N}人の人が数直線上に家を建てようとしています。{i}番目の人が建てる家の場所の候補は{M}個あり、このうちちょうど{1}つの地点を選び家を建てます。{j}番目の候補は地点{P_{i,j}}にあり、この地点に家を建てると不満度が{A_{i,j}}増えます。また、友達関係にある人のペアが{K}組与えられ、{k}番目のペアである{x_k}番目の人と{y_k}番目の人が建てた家の距離が{D}である場合、不満度が{B_{k}\times D^2}増えます。

{N}人の家の場所を適切に決めることで不満度の和を最小化してください。

  • {2 \leq N \leq 100}
  • {2 \leq M \leq 5}
  • {1 \leq K \leq \min(N(N-1)/2,400)}
  • {0 \leq P_{i,1} < P_{i,2} < \dots < P_{i,M} \leq 10^3}
  • {-10^9 \leq A_{i,j} \leq 10^9}
  • {1 \leq x_{k} < y_{k} \leq N}
  • {0 \leq B_{k} \leq 10^9}

解説

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

選択肢が複数になっています。選択肢が{2}つ([A/B])の場合は以下のようにグラフを作成すればよかったです。{v}をT側集合に選ぶことが[A]を選ぶことに対応し、S側集合に選ぶことが[B]を選ぶことに対応しています。

これを選択肢が{3}つ以上ある場合に拡張しようとする場合以下のようなグラフが考えられます。[A/B/C]

{v_1,v_2}をT側集合に選ぶことが[A]を選ぶことに対応し、{v_1}をS側集合{v_2}をT側集合に選ぶことが[B]を選ぶことに対応し、{v_1,v_2}をS側集合に選ぶことが[C]を選ぶことに対応します。しかし、{v_1}をT側集合{v_2}をS側集合に選ぶことができてしまうため、このような選択に{\infty}のコストをかけることでこのような選択が発生しないようにします。

次に{2}つの選択間にかかるコストを考えます。以下のように

  • 赤：{u_1}から{v_1}への有向辺
  • 橙：{u_1}から{v_2}への有向辺
  • 緑：{u_2}から{v_1}への有向辺
  • 青：{u_2}から{v_2}への有向辺

が張られたグラフがどのようなコストを表しているかを考えます。

コストを表で書くと以下のようになります。辺の色と同じ色の枠の部分には一律に辺の重み分のコストがかかります。

コストがこの形で表すことができればグラフで表すこともできるということになります。例として入力例2の{1}番目の人と{2}番目の人の距離に関するコストをグラフで表してみます。

まず、{P_{2,1}}の列から{1}を引き、{A_{2,1}}に{1}を足します。このようにしても選択によるコストは変わりません。同様に{P_{2,2},P_{2,3}}についても行います。

次に、{P_{1,2}}の行から{-32}を引き、{A_{1,2}}に{-32}を足します。同様に{P_{1,3}}についても行います。

先程の辺のコストを色分けした表を見ると、コストが2次元累積和のようになっており、差分を取ることでそれぞれの辺の重みを求めることができます。

このとき、差分を取った値は非負である必要があります。
非負である条件として、コストの表内のすべての{2×2}の部分を抜き出し、値を以下のように{a,b,c,d}としたとき{a-b-c+d\leq 0}であることが必要です。
今回のコスト関数{B_k\times D^2}は{P_i}がソートされている(単調増加である)場合この条件を満たします(証明略)。この辺の話は劣モジュラ性・Monge性の話と関わってきます。

頂点数は{O(NM)}、辺数は{O(KM^2+NM)}であるので、Dinic法で{O(N^2M^3(KM+N))}、Push-Relabelで{O(N^2M^2\sqrt{KM^2+NM})}です。

辺の省略と負辺除去
選択肢が3つありそれぞれのコストがA/B/Cであるものを考えます。普通にグラフを作ると以下のようになります。

{A=\min(A,B,C)}であるとき、全てのコストから{A}を引き、最終的な答えに{A}を足すとグラフは以下のようになり辺が1つ省略できます。

最小値が{B,C}である場合も同様にできます。これを用いると負のコストがある場合でも負辺を取り除くことができます。

類題(ほぼ同じ)
kanpurin.hatenablog.com

他の燃やす埋める問題(Project Selection Problem)の例題については以下にまとめています。
kanpurin.hatenablog.com

提出プログラム

[]

感想

機械的にグラフを構築する問題でした。

燃やす埋める練習問題２

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

燃やす埋める(Project Selection Problem)の練習問題についての解説です。

問題はこちら

ポイント

  • 最大化を最小化へ言い換える
  • グラフ表現可能なコストの性質
  • 2部グラフの性質を用いたの選択肢の順序変更

問題概要

頂点数{|L|,|R|}、辺数{M}の二部グラフおよび各頂点の重み{w_{L_i},w_{R_i}}が与えられます。{j}番目の辺は頂点{L_{x_j}}と頂点{R_{y_j}}を結んでいます。このグラフにおける最大重み独立集合を求め、重みの和を出力してください。

最大重み独立集合とは独立集合のうち、頂点の重みの和が最大となるもののことです。

  • {1 \leq |L|,|R| \leq 100}
  • {0 \leq M \leq L\times R}
  • {1\leq w_{L_i},w_{R_i} \leq 10^9}
  • {1\leq x_j\leq L}
  • {1\leq y_j\leq R}
  • {i\neq j \Leftrightarrow (x_i,y_i)\neq (x_j,y_j)}

解説

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

各頂点を独立集合として[選ばない/選ぶ]を選択します。頂点{L_i}を選ぶ際のコストは以下のようになります。[選ぶ]と{w_{L_{i}}}の利得が発生するので{-w_{L_{i}}}のコストがかかると考えます。これは頂点{R_i}を選んだ際も同様です。

各辺{(L_{x_j},R_{y_j})}について、頂点{L_{x_j}}と頂点{R_{y_j}}をともに[選ぶ]ことはできないのでともに[選ぶ]を選択すると{\infty}のコストが発生するようにします。

このままだとうまくグラフを作ることができないので二部グラフの性質を利用します。頂点{L_i}の選択肢の順番を入れ替えると以下のようにグラフで表せるコストの形になりました。二部グラフであることから、{L}と{R}を結ぶ辺しかなく、全てのコストがこの形で書けることが分かります。

負の辺({-w_{L_{i}},-w_{R_{i}}})が存在するため、あらかじめ{-w_{L_{i}},-w_{R_{i}}}を加算しておくことで、[選ばない]を選択した際に{w_{L_{i}},w_{R_{i}}}がかかると考えることができます。
以上をまとめるとコストは以下のようになります。

この最小コストが最小カットとなるようなグラフが構築でき、例えば入力例2では以下のようなグラフが構築できます。{L_i}を[選ぶ]ときは{S}側の集合に、[選ばない]ときは{T}側の集合に割り当てることを意味し、{R_i}を[選ぶ]ときは{T}側の集合に、[選ばない]ときは{S}側の集合に割り当てることを意味します。このときの{S}側の頂点から{T}側の頂点に向かう辺の重みの和がカットのコストとなります(この辺の話は他の資料が詳しいです)。

{N=|L|+|R|}として、頂点数は{O(N)}、辺数は{O(N+M)}です。Dinicを用いると時間計算量{O(N^2(N+M))}で解くことができます。

他の燃やす埋める問題(Project Selection Problem)の例題については以下にまとめています。
kanpurin.hatenablog.com

提出プログラム

[]

感想

燃やす埋めるの基本的な問題でした。
タイトルがヒントになっているので難易度は水色にしました。

燃やす埋める練習問題１

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

燃やす埋める(Project Selection Problem)の練習問題についての解説です。

問題はこちら

ポイント

  • 選択に対するコストからグラフを構築する

問題概要

{0,1}からなる文字列{S}が与えられます。{A_i}円支払うことにより、{S_i}を({0}ならば{1}に、{1}ならば{0}に)変更することができます。また、{K}個の区間{[L_k,R_k]}が与えられ、文字列{T=S_{L_k}S_{L_k+1}\dots S_{R_k}}について{f(T)\times B_k}円追加で支払う必要があります。

  • {f(T):=}文字列{T}を回文にするために必要な文字の最小変更回数

例えば、{110101}を回文にするためには{2,3}文字目を変更する必要があるため{f(110101)=2}となります。

適切に{S}の文字を変更することにより、支払う金額を最小化してください。

  • {1 \leq N \leq 300}
  • {1 \leq K \leq N(N-1)/2}
  • {0\leq A_i,B_k \leq 10^9}
  • {1\leq L_k < R_k\leq N}
  • {S_i \in\{0,1\}}

解説

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

各{S_i}を[変更しない/変更する]を選択肢とするのではなく、[0にする/1にする]を選択肢とします({f(T)}が最終的な{S_i}の値に関する制約なので)。
もともと{S_i=0}であるのものは以下のコストがかかります。

{S_i=1}であるのものも同様にして以下のコストがかかります。

{f(S_{L_k}S_{L_k+1}\dots S_{R_k})}の値は{S_{L_k+i}\neq S_{R_k-i}}となるような{i(0\leq i < \frac{R_k-L_k}{2})}の個数です。したがって、{S_{L_k+i}\neq S_{R_k-i}}となる場合に{B_k}のコストがかかると考えます。

グラフを作成していきます。各文字に対応する頂点を作り、始点Sから各頂点に向けて有向辺を張り、各頂点から終点Tに向けて有向辺を張ります。このグラフの(S,T)カットで頂点{S_i}がS側の集合に含まれることを「{S_i}を{0}にする」ことに、T側の集合に含まれることを「{S_i}を{1}にする」ことに対応させます。上のコスト表を見ると、{S_i=0, S_j=1}か{S_i=1, S_j=0}のときにコストをかけたいです。{S_i=0, S_j=1}にコスト{B_k(\geq 0)}をかける場合、つまり頂点{S_i}がS側に、頂点{S_j}がT側にある際にコスト{B_k}をかける場合は頂点{S_i}から頂点{S_j}に重み{B_k}の有向辺を張ればよいです。

入力例1に対するグラフは以下のようになります。重み{0}の辺は省略しています。

同じ頂点対{S_i,S_j}に辺を張る場合は{B_k}をまとめて張ると辺の数は{O(N^2)}となります。頂点数は{O(N)}となるので、Dinicを用いると時間計算量{O(N^4)}、Push-Relabelを用いると{O(N^3)}で解くことができます。

※2022/10/13追記
同じ頂点間に張られている辺はまとめて下さい．
{u\rightarrow v}に{3,5,9}の辺が張られていたら{17}の辺のみ張るようにする

他の燃やす埋める問題(Project Selection Problem)の例題については以下にまとめています。
kanpurin.hatenablog.com

提出プログラム

[]

感想

なんか他の方法でも解けそうな気がしますが、燃やす埋める問題の例として出題しました。

yukicoder No.2023 Tiling is Fun

yukicoder 典型 動的計画法 数え上げ 競技プログラミング 解説

問題はこちら

問題概要

{xy}平面上の {A=(1,0),B=(a,0),C=(a,b−1),D=(a−1,b),E=(0,b),F=(0,1)} を頂点とする六角形{ABCDEF}を考えます。
この六角形に次の3種類の図形を敷き詰めます。

yukicoder No.2023問題文中の画像

これらの図形を回転・反転を許さずに、隙間も重なりもないように敷き詰める方法は何通りありますか。

  • {2\leq a,b\leq 10^5}

解説

求めるものを{f(a,b)}とします。
六角形の左下には黄色の図形か青の図形を埋めるしかありません。
黄色の図形を埋めると、以下の様に赤の図形を埋めるしかなくなります。残りは{f(a,b-1)}を求めればよいです。

青の図形を埋めると、以下の様に赤の図形を埋めるしかなくなります。残りは{f(a-1,b)}を求めればよいです。

以上から{f(a,b)=f(a,b-1)+f(a-1,b)}となります。
{f(a,1)=1, f(1,b)=1}であることを踏まえると{\displaystyle f(a,b)=\binom{a+b-2}{a-1}}であることが分かります。

提出プログラム

https://yukicoder.me/submissions/782760

感想

解説と違ったので書いてみました。この問題思いつくのがすごい。

yukicoder No.2013 Can we meet?

yukicoder 形式的冪級数 式変形 期待値 競技プログラミング 解説

ほとんど公式解説と同じなので簡単に書きます。

問題はこちら

問題概要

2点{(x_1,y_1),(x_2,y_2)}がそれぞれ上下左右に{1}移動することを{N}回繰り返す．移動は左右には{\frac{A}{2(A+B)}}の確率で，上下には{\frac{B}{2(A+B)}}の確率で移動するとき、2点が{i}回目の移動直後に初めて重なる確率を{p_i}としたときの{\sum_{i=1}^{N}p_i×a_i}を求めよ．

  • {1\leq N\leq 10^5}
  • {0\leq x_1,y_1,x_2,y_2\leq 10^9}
  • {(x_1,y_1)\neq (x_2,y_2)}
  • {1\leq A,B\leq 10^6}
  • {1\leq a_i\leq 10^9}

解説

公式解説と同様に{x=|x_1-x_2|,y=|y_1-y_2|}とします．以降，{2N}回の移動で{(0,0)}から{(x,y)}への移動を考ます．
ここで，

  • {f(n):=(0,0)}から{2n}回の移動後に初めて{(x,y)}にいる確率
  • {g(n):=(0,0)}から{2n}回の移動後に{(x,y)}にいる確率
  • {h(n):=(0,0)}から{2n}回の移動後に{(0,0)}にいる確率

とすると，{g(n)=\sum_{i=0}^{n}f(i)×h(n-i)}が成り立ちます．公式解説と同様の方法で{g,h}を計算した後，{f,g,h}を形式的冪級数と考えると{f=g/h}として{f}を求めることができます．

計算量は{O(N\log{N})}です．

提出プログラム

https://yukicoder.me/submissions/779185

感想

結構きれいな形になった．

yukicoder No.2002 Range Swap Query

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

問題はこちら

問題概要

長さ{N}の数列{P}と{K}個の操作があり，操作{i}は{P_{A_i}}と{P_{B_i}}を入れ替える．
以下の{Q}個のクエリを処理せよ．
操作{L_j,L_j+1,\cdots ,R_j}をこの順に行ったときの{P_{X_j}}を求めよ．

  • {2\leq N\leq 4×10^5}
  • {1\leq K\leq 2×10^5}
  • {1\leq Q\leq 2×10^5}
  • {1\leq A_i < B_i \leq N}
  • {1\leq L_j \leq L_j \leq K}
  • {1\leq X_j \leq N}

解説

このクエリはオフラインで処理できるのでMo's algorithmが使えないかを考える．

Mo's algorithmについては以下の記事を参照
kanpurin.hatenablog.com

{[l,r)}の答え(状態)から{[l±1,r),[l,r±1)}の答え(状態)が高速に計算できればMo's algorithmを適用することができる．

{[l±1,r)}を左側への追加/削除，{[l,r±1)}を右側への追加/削除と言うことにする．
操作{i}を左側に追加/削除する場合，{P_{a}=A_i,P_{b}=B_i}となるような{a,b}に対し，{P_{a},P_{b}}を入れ替える．
操作{i}を右側に追加/削除する場合，{P_{A_i},P_{B_i}}を入れ替える．

これらは全て{O(1)}でできるので全体で{O(N\sqrt{Q})}で解くことができる．

提出プログラム

https://yukicoder.me/submissions/776935

感想