コンテスト中AC:A〜E

C - Filling 3x3 array

$i+j+k=S$ となる $(i,j,k)$ の組が何通りあるか考えます。これは、 $S$ 個の区別のないボールを横1列に並べ、 $N-1$ 個のボールの間から2つ選んで区別のない仕切りを置き、仕切りの左から順にボールの個数を整数として、 $i,j,k$ に割り当てる組合わせに等しいので、 $_{N-1}C_{2}$ 通りです。

これは、 $i,j$ について、それぞれ $1,\ \cdots ,\ S$ まで全探索することで、 $O(S^2)$ でこれらを全て列挙できます。また、全組み合わせは $N=30$ のケースで $_{29}C_{2}=406$ 通りで、かなり少ないです。

$(i,j,k)$ の組が少ないことがわかったので、マスへの整数の割り当てについても次から示すように全探索できます。

これから示すマスの文字は以下のようなイメージです。

a b c
x y z
p q r

1行目と2行目が確定すれば3行目も確定します。そこで、以下のような解法となります。

$a_i+b_i+c_i=h_1$ 、 $x_i+y_i+z_i=h_2$ となる組を全探索で列挙する。
列挙したものを
$V=\{(a_1,\ b_1,\ c_1),\ \cdots ,\ (a_M,\ b_M,\ c_M)\}$
$W=\{(x_1,\ y_1,\ z_1),\ \cdots ,\ (x_K,\ y_K,\ z_K)\}$
とする。
$V,W$ の要素の全組について、以下を調べる。

$V_i,W_j$ について、これらの組から $p = w_1 - a_i - x_j,\ q = w_2 - b_i - y_j,\ r = w_3 - c_i - z_j$ を計算する。
$p \gt 0,\ q\gt 0,\ r\gt0,\ p+q+r=h_3$ を全て満たすなら答えに+1する

$V,\ W$ の全要素の全組の全探索は、 $O(MK)$ で、最大でも $406\times 406 = 164836$ で、問題ありません。

実は、コンテスト中は $i+j+k=S$ を満たすものが何通りあるかの見積もりが間違っていました。
区別の無いボール $S$ 個と、区別の無い仕切り3個を横1列に並べる通り数として計算していました。 $_{S+3}C_{3}$ です。
これは、 $i+j+k+l=S$ を満たす $i,j,k,l$ の組であって、それぞれ0以上の場合の通り数です。

Submission #32614557 - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256) この解法はコンテスト後に見直したものです。

E - Takahashi's Anguish

キャンディを食べる順序を有向辺と見なせそうなので、グラフの問題で考えてみます。
また、人 $X_i$ が人 $i$ より前にキャンディを食べるというのがややこしいので、以下のように言い換えてみます。

最初の不満度は $S=C_1+\cdots +C_N$ である。人 $i$ の後に人 $X_i$ がキャンディを食べると不満度は $C_i$ 減少する。不満度の最小値を求めよ。

このように考えると、人 $i$ の後に人 $X_i$ にキャンディを食べさせて得られる不満度の減少量を最大化する問題となります。ここでは、減少量をスコアと表現します。

人を頂点とみなし、 $i$ から $X_i$ に向かうコスト $C_i$ の有向辺を持つ有向グラフを考えます。
これは、出次数1の有向グラフであり、このグラフに含まれる全ての連結成分は以下を満たします。

閉路をただ1つ持つ
任意の頂点から有向辺を辿る移動を繰り返すと連結成分内の閉路にたどり着き、無限ループに入る

これは一応、当ブログのAtCoderの過去問の記事で証明してみてあります。(あまり自信はないです)
リンク (ネタバレ注意)

この有向グラフの各頂点に1回ずつ訪れることを考えると、頂点を訪問順に並べた数列 $A$ を $P$ とすることができます。

訪問順を考える際、 $u$ を始点とする有向辺 $e=(u,\ v,\ C_u)$ をもつ頂点 $u$ を訪問した時に、

$v$ が未訪問なら、コスト $C_u$ を得る(スコアに加算する)。そうでない時、得られない。

とすることで、スコアの取得条件との辻褄があいます。

スコアの上界を見積もります。
各連結成分には閉路が存在します。各閉路について、閉路に属する辺の内の1つは確実にコストを得ることができません。この得ることができないコストには各閉路で最小のものを選ぶのが最適です。

以上から、閉路 $Cyc_i$ に属する辺のコストの内、最小のものを $w_i$ とし、その和を $S_w = w_1+\cdots + w_M$ とすると、スコアの上界は $S - S_w$ となります。
実はこれは常に達成可能です。

これを説明するために有向グラフ $G=(V,E)$ の連結成分の1つ $Comp_i = (V',E')$ を考えます。
$Comp_i$ にはただ1つ閉路が存在するので、これを $Cyc_i$ とします。
$Comp_i$ の部分グラフであって、 $T_j\rightarrow Cyc_i$ という感じで閉路と接続する $T_j$ を考えます。

$T_j$ は閉路を含まないため、トポロジカル順に頂点に訪問していくことで、 $T_j$ に属する辺及び、 $T_j$ と $Cyc_i$ を繋ぐ全ての辺(言い換えれば $T_j$ に属する頂点を始点とする全ての有向辺)のコストを得ることができます。

$Cyc_i$ に接続する全ての各部分グラフについてトポロジカル順に訪問した後、 $Cyc_i$ のうちコスト最小の有向辺の終点から訪問を開始し、閉路を一周すれば、閉路のコスト最小の有向辺以外のコストを全て得ることができます。

減少量(スコア)の最大値は $S-S_w$ であることが分かったので、当初の問題に戻ると $S$ から減少量の最大値 $S - S_w$ を引いた値が答えなので、結果として、不満度の最小値は $S_w$ です。

以上より、解法は、

各連結成分の閉路 $Cyc_1,\ \cdots ,\ Cyc_m$ のコスト最小を $w_1,\ \cdots ,\ w_m$ とすると、 $w_1 +\cdots +w_m$ が答え

ということになります。

閉路の求め方の実装ですが、強連結成分分解を利用しました。
atcoder::scc_graphを使うと、強連結な頂点集合が二次元配列で得られるので、列の大きさが2以上であれば閉路と見なすことができます。列の大きさが2以上の各行から最小値を得れば良いです。
Submission #32566831 - Tokio Marine & Nichido Fire Insurance Programming Contest 2022（AtCoder Beginner Contest 256)

geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 256 参加記録

C - Filling 3x3 array

E - Takahashi's Anguish