2023-01-12

ABC284 G - Only Once

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

問題概要

${1}$ 以上 ${N}$ 以下の整数からなる長さ ${N}$ の整数 ${A}$ について， ${B_{i,1}=i}$ ， ${B_{i,j+1} = A_{B_{i,j}}}$ という数列 ${B_i}$ にちょうど一度だけ現れる数の種類を ${S_i}$ とする．
${A}$ として考えられる ${N^N}$ 個の数列全てにおいて ${\sum_{i=1}^{N}S_i}$ を求め，その総和を ${M}$ で割った余りを求めよ．

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

解説

対称性から、頂点 ${1}$ を基準に考えて最後に ${N}$ 倍することにします．

公式解説のようにグラフの問題として考えます．

すべてのFunctional Graphに対する「頂点 ${i}$ から辺を辿ったとき，ちょうど ${1}$ 回頂点 ${1}$ を訪れるような ${i}$ の数」の総和が答えになります．

あるグラフに対して，ちょうど ${1}$ 回頂点 ${1}$ を訪れるような ${i}$ はどのようになるのか考えてみましょう．

以下のように，赤の頂点を ${i}$ として選ぶと頂点 ${1}$ をちょうど ${1}$ 回訪れることが分かります．

赤い頂点からなる部分グラフは頂点 ${1}$ を根とする木となっていることが分かります．また，「頂点 ${1}$ をちょうど ${1}$ 回訪れる」という条件を満たすためには頂点 ${1}$ から赤い頂点以外の頂点に辺が張られている必要があります．

以上のことから「ちょうど ${1}$ 回頂点 ${1}$ を訪れるような ${i}$ の数」が ${k+1}$ となるようなグラフは次のように作ることができます．

頂点 ${1}$ を除く ${N-1}$ 個の頂点から ${k}$ 個を選ぶ
選んだ ${k}$ 個の頂点と頂点 ${1}$ を用いて木を作る
残りの ${N-1-k}$ 個の頂点から ${1}$ 個の頂点を選び，頂点 ${1}$ から辺を張る
${N-1-k}$ 個の頂点から ${N-1-k}$ 個の頂点に向かう辺を適当に張る

これらの選び方の数はそれぞれ以下のようになります．

${\binom{N-1}{k}}$
${(k+1)^{k-1}}$ (ケイリーの公式)
${N-1-k}$
${(N-1-k)^{N-1-k}}$

したがって，最終的なこの問題の答えは

$N×\sum_{k=0}^{N-2}\binom{N-1}{k}(k+1)^k(N-1-k)^{N-k}$

となります．任意modの二項係数を求める必要があることに注意してください．

nyaannyaan.github.io

qiita.com

提出プログラム

https://atcoder.jp/contests/abc284/submissions/37886440

感想

任意mod二項係数の話が一番難しい

2023-01-12

ABC284 F - ABCBAC

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

問題はこちら

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

問題概要

長さ ${2N}$ の文字列 ${T}$ が与えられる．長さ ${N}$ の文字列 ${S}$ であって， ${T=S[0,i)+rev(S)+S[i,N)}$ となるようなものを求めよ．

${1\leq N\leq 10^6}$

解説

${T[i,j)}$ で文字列 ${T}$ の ${i}$ 文字目から ${j-1}$ 文字目までの文字列とします．
${rev(T)}$ で文字列 ${T}$ を反転させた文字列とします．

すべての ${i}$ で以下の判定が高速に行えればこの問題を解くことができます．

${T[0,i)+T[N+i,2N)=rev(T[i,i+N))}$ か？

例として以下の入力を考えます．

以下のような判定ができればよいです．

必要な操作は

連続部分文字列の取得
文字列の結合
文字列の比較

となりますが，これはローリングハッシュを用いることで前処理 ${O(N)}$ のもと，すべて ${O(1)}$ で行うことができます．

qiita.com

提出プログラム

https://atcoder.jp/contests/abc284/submissions/37954573

感想

ロリハやるだけでした

2022-12-16

EDPC S - Digit Sum

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

問題はこちら

問題概要
解説

問題概要

${1}$ 以上 ${K}$ 以下の整数のうち，十進表記における各桁の数字の総和が ${D}$ の倍数であるようなものはいくつか．

${1\leq K < 10^{10000}}$
${1\leq D\leq 100}$

解説

桁DPというものを用いると解くことができます．実装方法には様々な種類があるので代表的なものについて解説を行います．桁DPの概念については他の分かりやすい記事を参考にしてください．

以下のけんちょんさんの記事がおすすめです。

drken1215.hatenablog.com

以下， ${K}$ の上から ${i}$ 桁目の数を ${K_i}$ ， ${K}$ の桁数を ${L}$ と表します．

未満フラグを持つDP

${dp[i][j][k]=}$ 「上位 ${i}$ 桁まで決めたとき，桁和を ${D}$ で割った余りが ${j}$ となるようなものの数( ${k}$ は決めた数が ${K}$ 未満であることが確定しているかのフラグ)」とします．
${dp[i][j][0]}$ からの遷移は以下のものがあります．

${dp[i+1][(j+x)\%D][0]}$ ( ${i+1}$ 桁目の数 ${x}$ として ${x=K_{i+1}}$ を選んだ場合)
${dp[i+1][(j+x)\%D][1]}$ ( ${i+1}$ 桁目の数 ${x}$ として ${0\leq x < K_{i+1}}$ を選んだ場合)

${dp[i][j][1]}$ からの遷移は以下のものがあります．

${dp[i+1][(j+x)\%D][1]}$ ( ${i+1}$ 桁目の数 ${x}$ として ${0\leq x\leq 9}$ を選んだ場合)

これをそのまま書けば求めることができます．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
DP = [[[0]*2 for _ in range(D)] for _ in range(L+1)]
MOD = 10**9+7

DP[0][0][0] = 1
for i in range(L):
    for j in range(D):
        for x in range(10):
            if x == int(K[i]):
                DP[i+1][(j+x)%D][0] += DP[i][j][0]
                DP[i+1][(j+x)%D][0] %= MOD
            if x < int(K[i]):
                DP[i+1][(j+x)%D][1] += DP[i][j][0]
                DP[i+1][(j+x)%D][1] %= MOD
            DP[i+1][(j+x)%D][1] += DP[i][j][1]
            DP[i+1][(j+x)%D][1] %= MOD
            
print((DP[L][0][0]+DP[L][0][1]-1)%MOD)

未満フラグを持たない方法

${dp[i][j]=}$ 「上位 ${i}$ 桁まで決めたとき，桁和を ${D}$ で割った余りが ${j}$ となるようなもののうち ${K}$ より小さいことが確定しているものの数」とします．

${dp[i][j]}$ からは ${dp[i+1][(j+x)\%D](0\leq x\leq 9)}$ への遷移があります．
また， ${i}$ 桁目で初めて ${K}$ より小さいことが確定するような数( ${i-1}$ 桁まで ${K}$ と同じで， ${i}$ 桁目が ${K_{i}}$ より小さい数)の分も考える必要があります．
${dp[L][0]}$ は ${0\leq x < K}$ を満たす ${x}$ について桁和が ${D}$ の倍数であるものの数となるので，これから ${0}$ の分を引いて ${K}$ の分を確認して足せば答えが求まります．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
DP = [[0] * D for _ in range(L+1)]
MOD = 10**9+7
 
S = 0
for i in range(L):
    for x in range(10):
        for j in range(D):
            DP[i+1][(j+x)%D] += DP[i][j]
            DP[i+1][(j+x)%D] %= MOD
        if 0 <= x < int(K[i]):
            DP[i+1][(S+x)%D] += 1
            DP[i+1][(S+x)%D] %= MOD
    S += int(K[i])
 
if S%D == 0:
    print(DP[L][0])
else:
    print((DP[L][0]-1)%MOD)

今回の問題はLeadingZeroがあったとしても(0は和の単位元なので)問題なく数えられますが，LeadingZeroがあってはならない問題もあります．*1
この場合はDPを上位 ${i}$ 桁まで決めたとき以下の条件を満たすものの数と定義すればよいです．

${N}$ より小さいことが確定している
すべての桁が ${0}$ ではない( ${000...0}$ でない)

すると，以下のように分けられます．

${dp[i][j]}$ から ${dp[i+1][(j+x)\%D](0\leq x\leq 9)}$ への遷移
${i}$ 桁目で初めて ${K}$ より小さいことが確定するような数( ${i-1}$ 桁まで ${K}$ と同じ)
${i}$ 桁目で初めて ${0}$ でない数が現れるような数．

最後に ${K}$ の分を確認して足せば答えが求まります．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
DP = [[0] * D for _ in range(L+1)]
MOD = 10**9+7

for i in range(1,int(K[0])):
    DP[1][i%D] += 1
    DP[1][i%D] %= MOD

S = int(K[0])
for i in range(1,L):
    for x in range(10):
        for j in range(D):
            DP[i+1][(j+x)%D] += DP[i][j]
            DP[i+1][(j+x)%D] %= MOD
        if 0 <= x < int(K[i]):
            DP[i+1][(S+x)%D] += 1
            DP[i+1][(S+x)%D] %= MOD
        if 1 <= x:
            DP[i+1][x%D] += 1
            DP[i+1][x%D] %= MOD
    S += int(K[i])

if S%D == 0:
    print((DP[L][0]+1)%MOD)
else:
    print(DP[L][0])

メモ化再帰

${f(x,d):=}$ ${0}$ 以上 ${x}$ 以下の整数のうち，桁和を ${D}$ で割った余りが ${d}$ となるものの数

とします． ${1}$ の位の数字を ${k}$ としたときの場合分けをします．

${k\leq (x\bmod{10})}$ のとき

　 ${f(\lfloor x/10\rfloor, (d-k)\bmod{D})}$

${(x\bmod{10}) < k}$ のとき

　 ${f(\lfloor x/10\rfloor-1, (d-k)\bmod{D})}$
となるので再帰で解くことができます。
実は ${f(K,*)}$ を計算するために再帰していく際，第 ${1}$ 引数には「 ${K}$ の上位 ${i}$ 桁」か「 ${K}$ の上位 ${i}$ 桁 ${-1}$ 」の形の数しか現れません．
したがって，全体で ${O(D\log{K})}$ しかかかりません．

C++プログラム

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

constexpr int MOD = 1e9 + 7;

unordered_map<ll,ll> memo;
string K;
int D;

// 0以上K[:x](tight?以下:未満)の整数のうち，桁和をDで割った余りがdとなるものの数
ll solve(int x, int tight, int d) {
    if (memo.count(x*D*2+tight*D+d)) return memo[x*D*2+tight*D+d];
    if (x == -1 && tight == 1 && d == 0) return 1;
    else if (x == -1) return 0;
    ll res = 0;
    int k = K[x]-'0'-1+tight;
    for (int i = 0; i <= k; i++) {
        res += solve(x-1,1,((d-i)%D+D)%D);
        res %= MOD;
    }
    for (int i = k+1; i < 10; i++) {
        res += solve(x-1,0,((d-i)%D+D)%D);
        res %= MOD;
    }
    return memo[x*D*2+tight*D+d] = res;
}

int main() {
    cin >> K >> D;
    cout << (solve(K.size()-1,1,0)+MOD-1)%MOD << endl; // 0の分引く
    return 0;
}

以下の記事も参考になります．
maspypy.com

場合分け

${1}$ 以上 ${K}$ 以下の整数 ${x}$ は以下の ${4}$ つのグループのうち，ちょうど ${1}$ グループに属します．

${K}$ と上位 ${k}$ 桁が一致する ${L}$ 桁の整数( ${1\leq k < L}$ )
${K}$ と ${1}$ 桁目が異なる ${L}$ 桁の整数
${k}$ 桁の整数( ${1\leq k < L}$ )
${K}$ そのもの

それぞれのグループに属する整数のうち，桁和 ${D}$ で割った余りが ${0}$ となるものの数を数えます．
このとき，以下の値が必要になるのであらかじめ基本的なDPにより求めておきましょう．

${N,d}$ が与えられる．
整数列 ${\{a_1,a_2,\dots,a_N\}}$ のうち， ${0\leq a_i\leq 9(1\leq i\leq N)}$ かつ ${\sum_{i=1}^{N}a_i\equiv d\bmod{D}}$ となるものの数 ${f(N,d)}$ を求めよ．

それぞれ以下のように求められます．

${K}$ と上位 ${k}$ 桁が一致する ${L}$ 桁の整数( ${1\leq k < L}$ )

${x_i=K_i(i\leq k)}$ かつ ${0\leq x_i < K_i(i= k+1)}$ かつ ${0\leq x_i\leq 9(k+1 < i)}$ となるので，
${f(L-k-1,-x_{k+1}-\sum_{i\leq k}K_i)}$ が答えになります．

${K}$ と ${1}$ 桁目が異なる ${L}$ 桁の整数

${1\leq x_1 < K_1}$ かつ ${0\leq x_i\leq 9(1 < i)}$ となるので，
${f(L-1,-x_1)}$ が答えになります．

${k}$ 桁の整数( ${1\leq k < L}$ )

${x_i=0(i\leq L-k)}$ かつ ${1\leq x_i\leq 9(i=L-k+1)}$ かつ ${0\leq x_i\leq 9(L-k+1 < i)}$ となるので，
${f(k-1,-x_{L-k+1})}$ が答えになります．

${K}$ そのもの

${x_i=K_i(i\leq L)}$ となるので，
${f(0,-\sum_{i\leq L}K_i)}$ が答えになります．

Pythonプログラム

K = input()
D = int(input())
L = len(K)
F = [[0] * D for _ in range(L+1)]
MOD = 10**9+7
ans = 0

# f(N,d)の計算
F[0][0] = 1
for i in range(L):
    for j in range(D):
        for x in range(10):
            F[i+1][(j+x)%D] += F[i][j]
            F[i+1][(j+x)%D] %= MOD

S = 0
for k in range(1,L):
    S += int(K[k-1])
    S %= D
    for xk in range(int(K[k])):
        SS = (S + xk) % D
        ans += F[L-k-1][(D-SS)%D]
        ans %= MOD

for x1 in range(1,int(K[0])):
    ans += F[L-1][(D-x1)%D]
    ans %= MOD

for k in range(1,L):
    for xk in range(1,10):
        ans += F[k-1][(D-xk%D)%D]
        ans %= MOD

S += int(K[-1])
if S % D == 0:
    ans += 1

print(ans)

オートマトンDP

桁DPはオートマトン上のDPと捉えることができる．

kuretchi.github.io

kanpurin.github.io

C++プログラム

他の桁DPの問題は以下の記事にまとめています。
kanpurin.hatenablog.com

*1:ABC235 F

2022-12-13

ABC275 F - Erase Subarrays

ABC DP高速化競技プログラミング解説動的計画法

問題はこちら

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

問題概要

正整数列 ${A=(a_1,a_2,\dots,a_N)}$ に対して次の操作を ${0}$ 回以上行う．

${A}$ から連続部分列を選び，削除する．

${x=1,2,…,M}$ に対し， ${A}$ の要素の総和をちょうど ${x}$ にするために必要な操作回数の最小値を求めよ．

${1\leq N,M,a_i\leq 3000}$

解説

操作も制約も明らかにDPの気配がします。

そうすると自然に以下のDPを思い付きます。

${dp[i][j]:=a_i}$ までで、ちょうど ${j}$ にするために必要な操作回数の最小値
求める値は ${dp[N][x]}$ です。

左端を ${a_k}$ 、右端を ${a_i}$ とする連続部分列に対して操作を行う場合、 ${dp[k-1][j]+1}$
${a_i}$ を含む連続部分列に対して操作を行わない場合、 ${dp[i-1][j-a_i]}$

からの遷移があり、これらの最小値 ${\min(\underset{1\leq k\leq i}{\min}(dp[k-1][j]+1),dp[i-1][j-a_i])}$ が ${dp[i][j]}$ となります。

しかし、このままだと時間計算量 ${O(N^2M)}$ となり間に合いません。

ここで、各遷移がどのようになってるのかをDPテーブルを見ながら考えてみましょう。

★の値を求めるためには赤枠の値の最小値と青枠の値を求める必要があります。

赤枠の値を各★毎に求めていると ${O(N)}$ の計算量がかかってしまいますが、 ${dp[i][j]}$ のときの赤枠と ${dp[i-1][j]}$ の赤枠はほとんど同じであることを利用することで計算量を減らすことができます。

具体的には以下のような順番で赤枠の最小値を持ちながらDPテーブルを埋めていけばよいです。

提出プログラム

N,M = map(int,input().split())
a = list(map(int,input().split()))
INF = 10**10
 
dp = [[INF]*(M+1) for _ in range(N+1)]
 
dp[0][0] = 0
 
for j in range(M+1):
    premin = 0 if j == 0 else INF
    for i in range(N):
        if j >= a[i]: dp[i+1][j] = dp[i][j-a[i]]
        dp[i+1][j] = min(dp[i+1][j],premin+1)
        premin = min(premin,dp[i+1][j])
 
for x in range(1,M+1):
    if dp[N][x] == INF:
        print(-1)
    else:
        print(dp[N][x])

感想

基本的なDP高速化問題でした。

2022-12-11

燃やす埋める纏める

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

この記事は競プロ Advent Calendar 2022 11日目のために作成されました。

燃やす埋める問題として解ける制約やその他関連情報をまとめました。
他の情報も見つけ次第更新していきます。(最終更新日：2022/12/11)

燃やす埋める問題とは
燃やす埋めるで解ける制約
3つ以上の処理方法がある場合
その他の損失
答えの復元
計算量
ライブラリの作成
練習問題

燃やす埋める問題とは

燃やす埋める問題[1]の元ネタは多分こんな感じです。
「燃やす/埋める」以外にも「白で塗る/黒で塗る」、「使う/使わない」などの選択肢の問題もあります。

燃やす埋める問題
${i}$ 番目のゴミを燃やすとき ${A_i}$ の損失が、埋めるとき ${B_i}$ の損失が発生する。さらに、 ${i}$ 番目のゴミを燃やし ${j}$ 番目のゴミを埋めると追加で ${C_{i,j}}$ の損失が発生する。
すべてのゴミを適切に処理することで損失を最小化せよ。

この制約はグラフカット[2]に帰着され[3]、最小カット(=最大流)が答えとなります。
具体的には、以下のようなグラフを作り、 ${s}$ - ${t}$ カット ${(S,T)}$ のうち最小のものを求めればよいです。 ${i\in S}$ のとき、ゴミ ${i}$ を燃やすことに対応し、 ${i\in T}$ のとき、ゴミ ${i}$ を埋めることに対応しています。

カットエッジは赤い頂点から青い頂点への有向辺であり、最小カットは各頂点を赤or青に塗り分けるもののうちカットエッジの重みの和を最小にするようなものになります。この塗り分けが燃やすor埋めるへの割り当てと同じ意味になっています。

この「燃やす埋める」というのは日本の競プロ界隈でしか使われていません。

流行りのChatGPTも知らないみたいです()

「Project Selection Problem」と言う人もいますが、燃やす埋めると問題設定が違うと思います(解ける問題の集合は同じ)[4][5]。

単に「最小カット」としか言ってないような解説も多いです。

燃やす埋める問題として解ける制約

燃やす埋める問題として解ける制約について解説します。
他にもあると思いますが分かる範囲で書いてます。

ゴミ ${i}$ を燃やしたとき ${A_i}$ の損失

${A_i > 0}$ のとき

ゴミ ${i}$ を燃やしたとき ${A_i}$ の損失発生するので、 ${i\in S}$ のときに ${A_i}$ の重みのカットエッジがあるようにグラフを作ればよいです。

そのようなグラフは頂点 ${i}$ から頂点 ${t}$ に重み ${A_i}$ の有向辺を張ることで作ることができます。

${A_i < 0}$ のとき

ゴミ ${i}$ を燃やすと ${A_i}$ の損失 ${\rightarrow}$ 無条件で ${A_i}$ の損失＋ゴミ ${i}$ を埋めると ${-A_i(> 0)}$ の損失
と言い換えることができるので、次に説明する埋めたときと同様に辺を張ることができます。

例

ゴミ ${i}$ を埋めると ${-50}$ の損失が発生する場合、以下のように辺を張ったグラフの最小カットの重みを求め、それに ${-50}$ を加えたものが問題の答えとなります。

ゴミ ${i}$ を埋めたとき ${B_i}$ の損失

${B_i > 0}$ のとき

${i\in T}$ のときカットの重みが ${B_i}$ である ${\Leftrightarrow}$ 頂点 ${s}$ から頂点 ${i}$ に重み ${B_i}$ の有向辺がある。

${B_i < 0}$ のとき

ゴミ ${i}$ を燃やしたとき、 ${A_i(< 0)}$ の損失が発生する場合と同様に考えることができます。

ゴミ ${i}$ を燃やしゴミ ${j}$ を埋めたとき ${C_{i,j}(> 0)}$ の損失

${i\in S}$ かつ ${j\in T}$ のときカットの重みが ${C_{i,j}}$ である ${\Leftrightarrow}$ 頂点 ${i}$ から頂点 ${j}$ に重み ${C_{i,j}}$ の有向辺がある。

${2}$ つのゴミの処理方法による損失

実は[ゴミiを燃やしゴミjを埋めたときCij(> 0)の損失]は一般化できます。
ゴミ ${i}$ とゴミ ${j}$ の処理方法(燃やす、埋める)による損失が以下のように表されるとします。

この損失が ${B+C-A-D\geq 0}$ を満たす場合、以下のように分解することができます。

無条件に ${A}$ の損失
＋ゴミ ${i}$ を埋めると ${C-A}$ の損失
＋ゴミ ${j}$ を埋めると ${D-C}$ の損失
＋ゴミ ${i}$ を燃やし、ゴミ ${j}$ を埋めると ${B+C-A-D}$ の損失

これらはすでに説明した方法でグラフを作ることができます[6][7]。

${3}$ ゴミの処理方法による損失

${3}$ つのゴミの処理方法による損失を考えます。詳しい説明(理由)は他の方の記事[6][7]に任せますが、この損失を表現するには「ゴミ ${i,j,k}$ のうち、 ${1}$ つ以上が燃やされたとき ${C}$ の損失が発生する」という損失を表現する必要があります。

${C > 0}$ の場合について説明します。
これは、新たにグラフに「ゴミ ${i,j,k}$ のうち、 ${1}$ つ以上が燃やされた(※)」ことを表す頂点 ${v}$ を追加し、(※)が真の場合 ${v\in S}$ 、偽の場合 ${v\in T}$ になると考えると、

(※)が偽かつゴミ ${i}$ を燃やすと ${\infty}$ の損失
＋(※)が偽かつゴミ ${j}$ を燃やすと ${\infty}$ の損失
＋(※)が偽かつゴミ ${k}$ を燃やすと ${\infty}$ の損失
＋(※)が真なら ${C}$ の損失

として表すことができます。

複数のゴミのうち ${1}$ つ以上が燃やされたとき ${C(> 0)}$ の損失

ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、 ${1}$ つ以上が燃やされたとき ${C(> 0)}$ の損失がかかることをグラフで表現します。
先程 ${3}$ つのゴミの場合を説明しましたが、これと同様の方法で表現することができます。

複数のゴミのうち ${1}$ つ以上が埋められたとき ${C(> 0)}$ の損失

ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、 ${1}$ つ以上が埋められたとき ${C(> 0)}$ の損失がかかることをグラフで表現します。
先程と同様に考えると以下のように表現することができます。

より複雑な損失

ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ と ${Y=\{y_1,y_2,\dots ,y_{|Y|}\}}$ 、
${A_x > 0(x\in X), B_y > 0(y\in Y)}$ 、
${C > 0}$

が与えられたときに、

${X}$ に含まれるゴミ ${x}$ のうち燃やしたゴミににおける ${A_x}$ の和 ${\sum_{x\in S\cap X}A_x}$
${Y}$ に含まれるゴミ ${y}$ のうち埋めたゴミにおける ${B_y}$ の和 ${\sum_{y\in T\cap Y}B_y}$
${C}$

の最小値 ${\min(\sum_{x\in S\cap X}A_x,\sum_{y\in T\cap Y}B_y,C)}$ が損失となるようなグラフを作ります。

詳細は省略しますが、以下のように新たに頂点 ${u,v}$ を追加し、有向辺を張ればよいです。
これが正しく損失を表現できていることは、任意の ${s}$ - ${t}$ カット ${(S,T)}$ において、このカットエッジの重みが最小となる ${u,v}$ の割り当てを考えることで確認出来ます。
図では ${X\cap Y = \emptyset}$ に見えますが、 ${X\cap Y \neq \emptyset}$ であっても構いません。

( ${u\leftarrow v}$ の ${\infty}$ の辺は張らなくてもいいかも...)

また、

${\min(\sum_{y\in T\cap Y}B_y,C)}$ は ${u=s}$
${\min(\sum_{x\in S\cap X}A_x,C)}$ は ${v=t}$
${\min(\sum_{x\in S\cap X}A_x,\sum_{y\in T\cap Y}B_x)}$ は ${u=v}$

とすることで表現できます。

したがって、上で説明した以下の ${2}$ つはこの損失の特殊な例と考えることができます。
複数のゴミのうち1つ以上が燃やされたときC(> 0)の損失
 複数のゴミのうち1つ以上が埋められたときC(> 0)の損失

他にも、以下のようにこの構造を複数組み合わせるとより複雑な損失を表現することができます。複雑すぎる割にあまりコンテストに出てこなさそうなのでこの記事では説明しませんが、どのような損失を表すのか考えてみてください。

3つ以上の処理方法がある場合

これまでは選択肢が ${2}$ つ([燃やす/埋める])の場合について説明してきました。以下のグラフにおいて、頂点 ${i}$ を赤に塗る( ${i\in S}$ )ことが[燃やす]を選ぶことに対応し、青に塗る( ${i\in T}$ )ことが[埋める]を選ぶことに対応しています。

これを選択肢が ${3}$ つ以上ある場合に拡張します。

ゴミ ${i}$ の処理方法として ${k_i}$ 個の選択肢([処理 ${1}$ /処理 ${2}$ / ${\dots}$ /処理 ${k_i}$ ])があるとします。
以下の条件を満たす頂点 ${i_1, i_2, \dots ,i_{k_i-1}}$ を新たに追加します。

${x=1,2,\dots,k_{i}-1}$ について、

${i_x\in S}$ のとき、[処理 ${1}$ , 処理 ${2}$ , ${\dots}$ , 処理 ${x}$ ]のうちいずれも選ばない。
${i_x\in T}$ のとき、[処理 ${1}$ , 処理 ${2}$ , ${\dots}$ , 処理 ${x}$ ]のうちいずれかを選ぶ。

${i_x\in T\land i_{x+1}\in S}$ となることはないことに注意すると、以下のようなグラフを作ることができます。 ${c_x}$ は処理 ${x}$ を選んだ時の損失です。

${c_x}$ が負の場合でも、無条件で ${C=\underset{1\leq x\leq k_i-1}{\min}c_x}$ の損失を発生させ、 ${c_x\leftarrow c_x - C}$ とすることで ${c_x\geq 0}$ とすることができます。

他にも[8]のように張る方法もあります。

2つのゴミの処理方法による損失

${2}$ つのゴミの処理方法の選択による損失を考えます。以下のように

赤： ${i_1}$ から ${j_1}$ への有向辺
橙： ${i_1}$ から ${j_2}$ への有向辺
緑： ${i_2}$ から ${j_1}$ への有向辺
青： ${i_2}$ から ${j_2}$ への有向辺

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

損失を表で書くと以下のようになります。辺の色と同じ色の枠の部分には一律に辺の重み分の損失が発生します。

損失をこの形に分解することができればグラフで表すこともできるということになります。例として以下のような損失をグラフで表してみます。

ゴミiを燃やしたときAiの損失やゴミiを埋めたときBiの損失を用いると、行や列から一律に値を引くことができます。

まず、ゴミ ${i}$ に対して[処理 ${1}$ ]を選ぶと ${36}$ の損失が発生することにすると、ゴミ ${i}$ の[処理 ${1}$ ]の行から ${36}$ を引くことができます。同様に[処理 ${2}$ /処理 ${3}$ ]の行についても行います。

ゴミ ${j}$ に対して[処理 ${1}$ ]を選ぶと ${-35}$ の損失( ${35}$ の利得)が発生することにすると、ゴミ ${i}$ の[処理 ${1}$ ]の列から ${-35}$ を引くことができます。同様に[処理 ${2}$ /処理 ${3}$ ]の列についても行います。

先程の色枠の表を見ると、損失が ${2}$ 次元累積和のようになっており、差分を取ることでそれぞれの辺の重みを求めることができます。

このとき、差分を取った値(右表)は非負である必要があります。
非負である条件として、損失の表(左表)内のすべての ${2×2}$ の部分を抜き出し、値を以下のように ${A,B,C,D}$ としたとき ${B+C-A-D\geq 0}$ であることが必要です。

∞の損失の扱い

これで機械的に解けるようになったわけですが、 ${\infty}$ の損失を扱う場合には注意が必要です。ここで以下のような損失を考えてみましょう。

実装の際、 ${\infty}$ を巨大な定数として扱ってしまうと非負条件( ${B+C-A-D\geq 0}$ )が成り立たないためグラフを作ることができません。
しかし、実際には以下のようなグラフによりこの損失を表現することができます。

※これの処理方法について書きたいのですが投稿日に間に合わなさそうだったので後日書きます。

処理方法の決め方

各ゴミの処理方法は自由に決めることができます。[8]
ゴミ ${1}$ は(処理 ${1}$ ,処理 ${2}$ )=(燃やす,埋める)、ゴミ ${2}$ は(処理 ${1}$ ,処理 ${2}$ )=(埋める,燃やす)といったように、各ゴミで処理方法の並びが異なっていても構いません。

これを利用すると以下のような非負条件( ${B+C-A-D\geq 0}$ )を満たさない場合にも[2つのゴミの処理方法による損失]で説明した方法でグラフを作ることができる場合もあります。

${2}$ 部グラフ系の問題でこの変換を使うことがあります。

その他の損失

その他の損失を問題形式でいくつか置いておきます。重要な問題も含まれているので是非解いてみてください。

損失問題 ${1}$
ゴミ ${i}$ とゴミ ${j}$ を燃やすと ${P( > 0)}$ の利得( ${-P}$ の損失)が発生する。

解説

2つのゴミの処理方法による損失のように損失の表を作ります。

これは非負条件 ${0+0-(-P)-0\geq 0}$ を満たすのでコレに従ってグラフを作ることができます。

損失問題 ${2}$
ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、燃やされたゴミの数を ${K}$ とする。このとき、 ${K^2}$ の利得が発生する。

解説

${X}$ に含まれるすべてのゴミのペア ${(x_i,x_j) (1\leq i < j\leq |X|)}$ について、ゴミ ${x_i}$ とゴミ ${x_j}$ を燃やすと ${2}$ の利得が発生するようにします(損失問題 ${1}$ )。

${K}$ 個のゴミが燃やされたとすると ${K(K-1)}$ の利得が発生しますが、さらに ${x_i (1\leq i\leq |X|)}$ についてゴミ ${x_i}$ を燃やした時に ${1}$ の利得が発生するものとすれば、追加で ${K}$ の利得が発生し、全体で ${K(K-1)+K=K^2}$ の利得を表現するとこができます。

一般に、ゴミの集合 ${X}$ および ${w_{x_i} \geq 0}$ が与えられているとき、 ${(\sum_{x\in X\cap S}w_x)^2=\sum_{x\in X\cap S}w_x^2+2\sum_{x_i,x_j\in X\cap S, i < j}w_{x_i}w_{x_j}}$ となるので、 ${(\sum_{x\in X\cap S}w_x)^2}$ は「 ${x_i}$ を燃やすと ${w_{x_i}^2}$ の利得」、「 ${x_i,x_j}$ を燃やすと ${2w_{x_i}w_{x_j}}$ の利得」によって表現できます。

損失問題 ${3}$
ゴミの集合 ${X=\{x_1,x_2,\dots ,x_{|X|}\}}$ に含まれるゴミのうち、燃やされたゴミの数を ${K}$ とする。このとき、 ${K^3}$ の利得が発生する。

解説

損失問題 ${2}$ と同様に考えると3つのゴミの処理方法による損失が必要になってしまい、 ${O(|X|^3)}$ の頂点や辺が追加されてしまいます。これを頂点 ${O(|X|)}$ 、辺 ${O(|X|^2)}$ に抑える方法を説明します。

実は、損失の関数 ${f}$ において ${f(K+1)-f(K)\leq f(K)-f(K-1) (1\leq K\leq |X|-1)}$ が成り立つならばグラフで表現することができます。今回の問題では ${f(K)=-K^3}$ なのでこれが成り立っています。

例として、 ${|X|=7}$ の以下のような関数 ${f}$ を考えます(分かりやすいように折れ線で表しています)。

結論から言うと、この関数は、
${ \begin{array}{ll} f(K)=&\min(K,4)+\min(K,2)+\min(K,1) \\ &+\min(21-3K,6)+\min(7-K,1)-7 \end{array} }$
と分解できます[9]。一般に、この条件を満たす関数 ${f(K)}$ は正整数 ${a,b}$ を用いて ${\min(a×K,b)}$ や ${\min(a×(|X|-K),b)}$ と表されるものの和として表すことができ、これはまさに[より複雑な損失]で説明したようにグラフで表現することができます。

答えの復元

最小カットの重みで求めた後、それぞれのゴミの処理としてどれを選んだかを求めることができます。

[1]で説明されているように、各頂点 ${v}$ が ${v\in S}$ であるか ${v\in T}$ であるかは、 ${v}$ が残余ネットワークにおいて始点 ${s}$ から到達可能であるかどうかで分かります。

計算量

最大フロー最小カット定理[10]より、最小カットを求めるには最大フローを求めればよいです。

${n}$ 頂点 ${m}$ 辺のグラフを考えます。

Dinic法で解く場合、計算量は ${O(n^2m)}$ となりますが、様々な条件下でより計算量が落ちることがあります[11]。

他にも最大フローを求めるアルゴリズムとして

Ford-Fulkerson[12]： ${O(Fm)}$
Edmonds-Karp[13]： ${O(nm^2)}$
Push-Relabel[14]： ${O(n^3)}$ や ${O(n^2\sqrt{m})}$

などがあります。

ライブラリの作成

これまでの説明をもとに燃やす埋める問題を解くライブラリを作る場合、以下のような機能があればいいと思います。

ゴミの処理方法の数(必須)

各ゴミの処理方法の数 ${k_i}$ を与えます。何よりも先に必要です。

ゴミの処理方法による損失(必須)

各ゴミの処理方法による損失 ${cost_i(x),(1\leq x\leq k_i)}$ を与えるとその損失に応じた辺を張ります。負の数でも構いません。

ただし、損失が与えられた時点で辺を張るのではなく最小カットを求める直前に辺を張るようにしてください。後程説明する他の種類の損失で ${cost_i}$ の値が変更される場合があるためです。

${2}$ つのゴミの処理方法による損失(必須)

${2}$ つのゴミの処理方法の選択間にかかる損失 ${cost_{i,j}(x,y),(1\leq x\leq k_i,1\leq y\leq k_j)}$ を与えるとその損失に応じた辺を張ります。
[2つのゴミの処理方法による損失]で説明した非負の条件を満たすことを関数内で確認するようにしましょう。

損失が与えられた時点で辺を張ってもいいですが、後から変更される場合もあるので注意してください。

答えの復元

ここで説明したとおりに最小カットの復元を行いましょう。

頂点 ${i_{x}\in S}$ かつ ${i_{x+1}\in T}$ であるならば処理 ${x+1}$ を選んだことになります。

複数のゴミのうち ${1}$ つ以上が処理 ${1}$ をされたときの損失

たまにこの制約がある問題を見ます。

任意の ${i}$ で ${k_i=2}$ ならコレとコレで実現できます。
他にも「複数のゴミのうちすべて処理 ${1}$ をしたら ${C > 0}$ の利得」に言い換えることもできます。

${k_i > 2}$ の場合にも拡張できますが、変な制約になります(素直に「 ${1}$ つ以上が処理 ${x}$ をしたら ${C}$ の損失」みたいにはなりません)。

${3}$ つのゴミの処理方法における損失

[3つ以上の処理方法がある場合]で説明したものです。

数回だけこれが必要な問題を見ました。

その他の損失

損失問題2はどこかで見たような記憶がある程度。
[より複雑な損失]や損失問題3の損失は見たことないです。

流行り出したら作るくらいでいいでしょう。

練習問題

練習問題 ${1}$ 🔗
長さ ${N}$ の整数列 ${x=(x_1,x_2,\dots,x_N)}$ を作ろうとしています。各 ${i(1≤i≤N)}$ について， ${x_i}$ の値の候補が ${M}$ 種類あり、そのうち ${k}$ 種類目の値は ${A_{i,k}}$ です。なお、 ${A_{i,k}}$ を選ぶ場合には、 ${C_{i,k}}$ のコストがかかります。また、 ${x}$ を決めたあと、各 ${i,j (1\leq i < j\leq N)}$ について、 ${|x_i−x_j|×W_{i,j}}$ のコストが追加でかかります。最終的なコストの総和としてありうる最小値を求めてください。

解説

燃やす埋めるライブラリを作る動機になる問題です。

[3つ以上の処理方法がある場合]を実装すれば解けます。
各 ${i,j}$ 間に張られる辺の数は ${O(M)}$ であることも簡単に分かります。

練習問題 ${2}$ 🔗
${n×m}$ のマス目が与えられます。既に白か黒で塗られているマスがあり、その他のマスは塗られていません。色が塗られていないマスをすべて白か黒で塗り、マス目上のチェックパターンの数を最大にしたいです。 ${2×2}$ の正方形を形成する ${4}$ つのマスは、以下のいずれかのように塗られている場合、チェックパターンであると言います。

チェックパターンの数の最大値とそのときの塗り方を求めてください。

解説

各マスの選択肢は[白で塗る/黒で塗る]です。既に塗られたマスを異なる色で塗ろうとする選択には ${\infty}$ の損失が発生するようにします。

すべての ${2×2}$ の正方形に対して、チェックパターンなら ${1}$ の利得が発生するようにしたいですが、このままではうまくできません。

ここで、 ${i+j\equiv 0\bmod{2}}$ となるマス ${(i,j)}$ の選択肢を[黒で塗る/白で塗る]に変更すると、チェックパターンの制約が「 ${2×2}$ の正方形を形成する ${4}$ つのマスすべてが選択肢 ${1}$ /選択肢 ${2}$ を選ぶ」と言い換えられるのでコレやコレが使えます。

他の問題は以下の記事にまとめています。
kanpurin.hatenablog.com

[1] 最小カットを使って「燃やす埋める問題」を解く(診断人さん)

[2] カット (グラフ理論)(Wiki)

[3] 最小カットについて(yosupoさん)

[4] ［Tutorial, Flows］ Project Selection Problem(AlexLuchianovさん)

[5] Max-flow min-cut theorem/Project selection problem(Wiki)

[6] 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性その①(つるさん)

[7] 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性その②(つるさん)

[8] 最小カット問題の k 値への一般化(noshi91さん)

[9] 0から7の範囲でmin(x,4)+min(x,2)+min(x,1)+min(21-3x,6)+min(7-x,1)-7(wolframalpha)

[10] 最大フロー最小カット定理(Wiki)

[11] Dinic 法とその時間計算量(misawaさん)

[12] Ford–Fulkerson algorithm(Wiki)

[13] Edmonds–Karp algorithm(Wiki)

[14] Push–relabel maximum flow algorithm(Wiki)

2022-10-05

ABC186 E - Throne

Baby-step Giant-stepを用いた別解です。

問題はこちら

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

問題概要

円状に並べられた ${N}$ 個の椅子があり，そのうち ${1}$ つは玉座である。玉座の ${S}$ 個右にある椅子から始めて， ${1}$ 回につき ${K}$ 右にある椅子に移動していく行動を繰り返すとき何回目の行動で玉座に移動することができるか．
${T}$ 個のテストケースについて答えよ．

${1\leq T\leq 100}$
${2\leq N\leq 10^9}$
${1\leq S < N}$
${1\leq K\leq 10^9}$

解説

Baby-step Giant-stepを用いた別解を紹介します．
Baby-step Giant-stepの解説

${f(x)=x+K\bmod{N}}$ として， ${f^{t}(S)=0}$ となる最小の非負整数 ${t}$ を求める問題になります．

${f^{M}(x)=x+KM\bmod{N}}$ ， ${f^{-1}(x)=x-K\bmod{N}}$ であるので，整数集合の値の検索にhashを用い， ${M=\lfloor\sqrt{N}\rfloor}$ とすれば，全体の時間計算量は ${O(\sqrt{N})}$ となります．

提出プログラム

https://atcoder.jp/contests/abc186/submissions/35220724 値の検索にmapを用いているので ${O(\sqrt{N}\log{N})}$ になってます．

感想

2022-09-02

燃やす埋める練習問題４

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

問題はこちら

ポイント
問題概要
解説
- 操作1のみしか行わない場合
- 操作2も行う場合
提出プログラム
感想

ポイント

${A\rightarrow B}$ (論理包含)タイプの制約

問題概要

${N}$ 頂点 ${M}$ 辺の有向グラフが与えられます． ${i}$ 番目の辺は頂点 ${x_i}$ から頂点 ${y_i}$ へ向かう有向辺です．各頂点には整数 ${B_i}$ が書かれており，各頂点ははじめ白で塗られています．
次の操作を順に行うとき，黒で塗られている頂点に書かれた整数の和の最大値を求めてください．
操作 ${1}$ ： ${0}$ 個以上の頂点を選択し，選択した頂点からたどり着ける頂点を黒で塗る．
操作 ${2}$ ： ${0}$ 個以上の頂点を選択し，選択した頂点からたどり着ける頂点を白で塗る。

${2 \leq N \leq 1000}$
${0 \leq M \leq \min(N(N-1),1000)}$
${0\leq B_i\leq 10^9}$
${1\leq x_i,y_i\leq N}$
${x_i\neq y_i}$
${(x_i,y_i)\neq (x_j,y_j) (i\neq j)}$

解説

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

操作1のみしか行わない場合

操作 ${1}$ のみしか行わない場合はARC085 E - MULと同じようにして解くことができます．
操作 ${1}$ を行った後に，黒で塗られた頂点から白で塗られた頂点へ向かう有向辺が存在してはいけません(黒で塗られた頂点から辿りつける頂点は黒で塗られているはずなので)．したがって，有向辺 ${(u,v)}$ すべてについて頂点 ${u}$ が黒，頂点 ${v}$ が白で塗られている場合に ${\infty}$ のコストをかけるようにすればよいです．
強連結成分はすべて同じ色になりますが，わざわざ強連結成分分解する必要はありません．

操作2も行う場合

操作 ${2}$ で白に塗るのではなく赤に塗ると考えます．すると，先程と同様に考えることができ，黒 ${\rightarrow}$ 白・赤 ${\rightarrow}$ 白・赤 ${\rightarrow}$ 黒，の頂点が存在する場合に ${\infty}$ のコストをかけるようにすればよいです．コストの表とグラフは以下のようになります．

負辺は以下の記事に従って除去してください．最大流を求めるアルゴリズムとしてPush-Relabelを用いると ${O(N^2\sqrt{N+M})}$ で求められます．Dinicも速いので間に合います．

kanpurin.hatenablog.com

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

提出プログラム

https://mojacoder.app/users/_kanpurin_/problems/project_selection_problem004/submissions/816c461e-5df1-4951-84d5-232061020e91

感想

${A\rightarrow B}$ タイプの問題は気付きにくい印象がある。

問題概要

解説

提出プログラム

感想

問題概要

解説

提出プログラム

感想

問題概要

解説

未満フラグを持つDP

未満フラグを持たない方法

メモ化再帰

場合分け

オートマトンDP

問題概要

解説

提出プログラム

感想

燃やす埋める問題とは

燃やす埋める問題として解ける制約

ゴミを燃やしたときの損失

のとき

のとき

ゴミを埋めたときの損失

のとき

のとき

ゴミを燃やしゴミを埋めたときの損失

つのゴミの処理方法による損失

ゴミの処理方法による損失

複数のゴミのうちつ以上が燃やされたときの損失

複数のゴミのうちつ以上が埋められたときの損失

より複雑な損失

3つ以上の処理方法がある場合

2つのゴミの処理方法による損失

∞の損失の扱い

処理方法の決め方

その他の損失

答えの復元

計算量

ライブラリの作成

ゴミの処理方法の数(必須)

ゴミの処理方法による損失(必須)

つのゴミの処理方法による損失(必須)

答えの復元

複数のゴミのうちつ以上が処理をされたときの損失

つのゴミの処理方法における損失

その他の損失

練習問題

問題概要

解説

提出プログラム

感想

ポイント

問題概要

解説

操作1のみしか行わない場合

操作2も行う場合

提出プログラム

感想

ゴミ ${i}$ を燃やしたとき ${A_i}$ の損失

${A_i > 0}$ のとき

${A_i < 0}$ のとき

ゴミ ${i}$ を埋めたとき ${B_i}$ の損失

${B_i > 0}$ のとき

${B_i < 0}$ のとき

ゴミ ${i}$ を燃やしゴミ ${j}$ を埋めたとき ${C_{i,j}(> 0)}$ の損失

${2}$ つのゴミの処理方法による損失

${3}$ ゴミの処理方法による損失

複数のゴミのうち ${1}$ つ以上が燃やされたとき ${C(> 0)}$ の損失

複数のゴミのうち ${1}$ つ以上が埋められたとき ${C(> 0)}$ の損失

${2}$ つのゴミの処理方法による損失(必須)

複数のゴミのうち ${1}$ つ以上が処理 ${1}$ をされたときの損失

${3}$ つのゴミの処理方法における損失