ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Regular Contest 052 D - 9

D - 9

公式Editorialと違う解法で解いたので記録。

計算量多めのゴリ押し解法なのでRuby・PyPyでは通りませんでした…

解法

まず桁DPを考えました。以下のように状態を考えることができます。

 dp\lbrack i \rbrack\lbrack k \rbrack\lbrack d \rbrack\lbrack l \rbrack = 上から  i 桁目までの数字まで決めて、そこまで決めた値を  K で割った余りが  k で、そこまでの桁和を  K で割った余りが  d で、上限値  M より小さいことが確定している( l=1)/いない( l=0)ような場合の数

これで桁DPできます。状態数は

  •  i M が最大11桁なので初期状態含めて12通り
  •  k K で割った余りなので  K 通り
  •  d:これも  K で割った余りなので  K 通り…と思いきや、 10^{10} 以下の非負整数の桁和は最大90なので  \min(K, 91) 通り
  •  l:2通り

です。1状態あたりの遷移は桁1つの数字の取り方で高々10通りなので、高速な言語に限れば  K \le 10^{4} くらいまでなら通る見込みがあります。  (12\times 10^{4}\times 91\times 2 \times 10 = 2.184\times 10^{8})

ただし制約は  1 \le K \le M \le 10^{10} であり、  K が大きいときには破綻します。そこで、 K が大きいときには  M \div K の商が小さいことを利用します。

 M \div K の商を  q 、余りを  r とします。さきほど見たように桁和は90以下なので、 r としてもこの範囲しか調べる必要はありません。  K \gt 10^{4} であれば商  q としてとり得る値は高々  10^{6} 通りなので、 (q, r) を全探索します。こちらも速い言語でないと厳しいですが何とか通ります。

ACコード

Submission #6437619 - AtCoder Regular Contest 052

CPSCO2019 Session2 E - Mogu Mogu Gummi

お題箱より。

E - Mogu Mogu Gummi

解法

木DPを考えてみる

「連結成分の個数」よりも「切った辺の本数」のほうが遷移を組みやすいので、そっちで考えます。連結成分の個数は切った辺の本数に1を足したものです。

シンプルなグラフを例にして考えてみましょう。頂点0が根です。

f:id:betrue12:20190719005533p:plain

このグラフにおいて、 H_{2} H_{3} の辺を切ろうとして頂点2や3を操作するときには必ず  H_{1} の辺がダメージを受けます。その途中で  H_{1} の辺のほうが切れてしまった場合、もうそれ以上頂点2や3は操作できません。

上側の辺が切れてしまうともう下側を操作できない…と考えると、例えば頂点1に注目したときには「なるべく上の辺  H_{1} に与えるダメージを少なくしつつ、下側の辺  H_{2}, H_{3} を多く切りたい」という気持ちになります。これを元に以下のようなDPを考えます。

  •  dp\lbrack i \rbrack\lbrack j \rbrack = 頂点  i 以下の部分木で辺を  j 本切るために必要な、頂点  i から根までの辺に与える最小のダメージ

ここでは最小のダメージしか覚えておく必要はありません。ダメージが小さいぶんには、頂点  i 自身を操作することでダメージを追加で与えることができるからです。

例えば上の図において頂点1についてこのDPを考えると、

  •  dp\lbrack 1 \rbrack\lbrack 0 \rbrack = 0
  •  dp\lbrack 1 \rbrack\lbrack 1 \rbrack = \min(H_{2}, H_{3})
  •  dp\lbrack 1 \rbrack\lbrack 2 \rbrack = H_{2} + H_{3}

こんな感じです。

遷移を詰める

より一般的にDPの遷移を詰めていきます。

頂点  i についてのDPの値を求めるときには、まず頂点  i を頂点数1の木とみなし  dp\lbrack i \rbrack\lbrack 0 \rbrack = 0 とします。その他の  j については  dp\lbrack i \rbrack\lbrack j \rbrack = \infty としておきます。 \infty はその部分木で辺を  j 本切るのが不可能であることを示します。ここに1つずつ子の情報をマージしていきます。

親頂点を  i 、子頂点を  c とします。親側で既に切っている辺の本数  j_{i} と子側で既に切っている辺の本数  j_{c} の組み合わせそれぞれについて遷移を試します。

f:id:betrue12:20190719021136p:plain

このとき遷移のパターンとしては、

  •  dp\lbrack c \rbrack\lbrack j_{c} \rbrack \gt H_{c} のとき:これは  c 以下で操作をしている途中で  H_{c} の辺が切れてしまうことを意味する。そのため、そもそもこの遷移は不可能。
  •  dp\lbrack c \rbrack\lbrack j_{c} \rbrack \le H_{c} のとき、以下の2つがあり得る:
    •  H_{c} の辺を切らない:切った辺の本数が  j_{i} + j_{c} になり、 H_{i} には合計で  dp\lbrack i \rbrack\lbrack j_{i} \rbrack + dp\lbrack c \rbrack\lbrack j_{c} \rbrack のダメージが入る。
    •  H_{c} の辺を切る:切った辺の本数が  j_{i} + j_{c} + 1 になり、 H_{i} には合計で  dp\lbrack i \rbrack\lbrack j_{i} \rbrack + H_{c} のダメージが入る。

このようにすればマージ後のDPテーブルを計算できます。同じ  (i, j) に対して複数の遷移が来た場合にはダメージが少ない方を採用すれば良いです。

このDPを根0まで計算します。そうすると最終結果である  dp\lbrack 0 \rbrack\lbrack j \rbrack は、「 dp\lbrack 0 \rbrack\lbrack j \rbrack \ne \infty のときは、木全体で辺を  j 本切ることが可能である」と捉えることができます。これで答えを求めることができます。

「二乗の木DP」の話

今回組んだDPは、実装を適切にしてあげると全体計算量  O(N^{2}) で動作します。通称「二乗の木DP」と呼ばれているものです。

こちらの記事で計算量解析がされていますが、まずは知識として覚えてしまって良いと思います。適用できる問題の特徴として、以下の点が挙げられます。

  • 木DPのテーブルに、どの頂点まで見たかだけでなく「頂点や辺の個数」に関するようなインデックスがある。
  • 遷移において子を1つずつマージする際に、さきほどの「頂点や辺の個数」を親子それぞれについて回す2重ループがある。
  • 実装においてこの2重ループを毎回  N N-1 まで回すのではなく、その部分木のサイズまでしかループしないようにすることができる。

つまりDPの状態を「頂点  i 以下の部分木で、○○な頂点が  j 個であるときの△△」や「頂点  i 以下の部分木で、○○な辺が  j 本であるときの△△」のように取れる時に適用しやすいです。このようなDPが組めて、かつ制約上  O(N^{2}) が許容されそうであれば、二乗の木DPを疑ってみましょう。

ACコード

Submission #6435777 - CPSCO2019 Session2

変数名はある程度は上記の解説に合わせています。再帰関数の中でコメントを付けているところが二乗の木DPのキモで、どの問題でも割と似たような実装になるので慣れておくと良いと思います。

細かい実装上の注意として、子をマージするときに  dp\lbrack i \rbrack から  dp\lbrack i \rbrack を更新するような格好になるので、遷移元と遷移先が混ざらないようにしないといけません。例えばナップサックDPを一次元配列でやろうとする時と似たような注意が必要です。

単純なのは上記コードのように別途一時配列を用意して遷移先をそっちに書き、後でコピーする方法。または今回の遷移であれば  j_{i}, j_{c} についてループの方向を逆順にすることで一時配列なしで上手くできたりしますが、慣れないうちは混乱しにくい前者がオススメです。

天下一プログラマーコンテスト2016予選A B - PackDrop

お題箱より。

B - PackDrop

解法

まずは問題をシンプルに

 0.99^{n} みたいなのがややこしいですね。まずは問題をシンプルに言い換えましょう。

ネットワーク全体は機器を頂点、その間を接続する経路を辺とするグラフとみなせます。より具体的には機器0を根とする根付き木になります。子機器を持たない  M 台の機器は葉であり、機器0から各葉  B_{i} への到達率が  0.99^{C_{i}} と指定されています。

間に複数辺がある場合の到達率を考えましょう。仮に機器0と葉  B_{i} の間に直列に辺が2本あり、それぞれPackDropが  a 個、 b 個含まれているとします。このときそれぞれの辺における到達率は  0.99^{a} 0.99^{b} であり、機器0と葉  B_{i} の間の到達率は問題文より掛け算になるので  0.99^{a} \times 0.99^{b} = 0.99^{a+b} となります。これは指数法則によるものであり、辺の本数が3本以上になっても同様のことが成り立ちます。

f:id:betrue12:20190713162811p:plain

つまり機器0から各葉  B_{i} への到達率を  0.99^{C_{i}} にしたいのであれば、経路上の辺に含まれているPackDropの個数を全て足し算したものを  C_{i} にすることが必要十分となります。これで  0.99^{n} のようなものを考えずに問題を言い換えることができます。

  • 頂点0を根とする頂点数  N の根付き木が与えられる。
  • それぞれの葉  B_{i} について、頂点0からの「距離」  C_{i} が指定されている。
  • 上記距離を満たすように、各辺に非負整数値の「長さ」を割り当てる。(元々、PackDropの個数だったもの)
  • 全ての辺の長さ合計を最小にしたい。その最小値はいくつか?

これで整数で考えられるグラフの問題になりました。

最小値の求め方を考える

実際にどのような割り当て方をすれば長さ合計を最小にできるのか考えてみます。

シンプルな例として、以下のグラフを考えてみましょう。

f:id:betrue12:20190713165429p:plain

これを実現する長さの割り当て方として以下のようなものが考えられます。

f:id:betrue12:20190713165439p:plain

これらは全て条件を満たしていますが、辺の長さ合計が違います。この例を見ると、できるだけ根に近いところに長さを大きく割り当てたほうが長さ合計を節約できそうです。

これはより複雑なグラフでも一般的に成り立ち、根に近いところに長さをできるだけ大きく割り当てるのが常に最適です。図の左側のように根以外の頂点から下に伸びる辺が全て正の重みを持っている場合は、図の右側のように上の辺に移すことで条件を満たしたまま長さ合計を減らせる(少なくとも増えはしない)からです。これはグラフが根付き木であることから成り立ちます。

そのため根に近いところから順番に辺の長さを決めていって、それぞれの長さは許される最大値まで割り当てることにしましょう。その辺の下にいる葉について、葉と根の距離が与えられた値  C_{i} を超えてはいけないので、それを超えないギリギリまで取ります。つまり辺の長さは、

 (その辺の下にいる葉についての C_{i} の最小値) - (根からその辺までの距離)

として決めることができます。

あとはこれを実際に計算していきます。各辺について、その辺の下にいる葉についての  C_{i} の最小値を求めておかないといけないので、これは下から順番に木DPのように求めておきましょう。それを予め求めた後で、辺の長さは上から順番に決めていきます。実装上は2回DFSをすることになります。

ACコード

Submission #4570032 - 天下一プログラマーコンテスト2016予選A

Codeforces Round #573 (Div. 1) C. Tokitsukaze and Duel

Problem - C - Codeforces

問題概要

0または1からなる  n 文字の文字列  S と整数  k が与えられ、それを用いて2人がゲームをする。交互にターンが回り、それぞれのターンで各プレイヤーは「連続する  k 文字を選び、それらを全て0または全て1にする」という操作を行う。プレイヤーの操作後に全ての文字が同じになったとき、そのプレイヤーが勝利する。

2人が最適に行動した時に先攻と後攻のどちらが勝つか、または  10^{9} ターン経過しても決着が付かない(引き分け)か、判定せよ。

制約

  •  1 \le k \le n \le 10^{5}
  •  S は0または1からなる  n 文字の文字列

解法

ゲームの展開を以下のように分類しましょう。

パターン1:先攻が1ターン目で勝つ場合

入力例3のようなケースです。あるいはもっと分かりやすい例だと、

8 4
01111000

などが該当します。4個並んでいる1を全て0に変えると勝ちです。

先攻が1ターン目で勝てるかどうかの判定は次のようにできます。左端から連続して0が並んでいる個数を  L_{0} 、右端から連続して0が並んでいる個数を  R_{0} として、もし  L_{0} + k + R_{0} \ge n であれば間を0に変えることで勝てます。同様に1についても判定できます。

このように、次に1回操作することで勝てるような文字列の状態を「リーチ状態」と呼ぶことにします。

※既に全文字が一致している場合も「リーチ状態」に含めます。テストケース5~8などにあるように、これが初期状態として与えられた場合も先攻の勝ちになります。

パターン2:後攻が1ターン目で勝つ場合

入力例1のようなケースです。

4 2
0101

入力例1では、先攻1ターン目では勝てません。そして先攻が操作した後の文字列として考えられるものは 0001 0100 1101 0111 です。これらは全てリーチ状態であり、どれを渡しても後攻が次の操作で勝つことができてしまいます。

もし操作後の文字列でリーチ状態でないものが1つでもあれば、先攻はそれを渡すことでひとまず負けを免れます。つまり「先攻が1ターン目で勝てないとき、後攻が1ターン目に勝てるかどうか?」は、「先攻1ターン目の操作の結果として考えられるもの全てがリーチ状態であるか?」と言い換えられます。これを調べるために、「先攻が操作する場所」×「0にするか1にするか」を全探索しましょう。

先攻の操作が0に変更するものだったとすると、判定に必要な情報は先ほどと同じく、先攻の操作後に左右端からそれぞれいくつ0が連続で並んでいるかの値です。これを先ほどと同じく  L_{0}, R_{0} と表記します(これらは操作位置に依存します)。これを任意の操作位置について高速に計算したいです。

これは前もって、全ての位置について「そこから左/右に連続で0がいくつ並んでいるか?」を調べておくことで可能です。この前計算は端から順番に見ていくことで  O(n) でできます。インデックス  i の位置から左に連続で0がいくつ並んでいるかを  l_{i, 0}、右に連続で0がいくつ並んでいるかを  r_{i, 0} と表記します。

この情報を持っておけば、先攻が0に変更する区間 \lbrack i, i+k-1\rbrack と決めた時に、左端から0が連続している個数  L_{0}

  • 左端から操作位置まで0が繋がっていない場合、つまり  r_{1, 0} \lt i-1 であるときには、単に元の状態のまま  L_{0} = r_{1, 0}
  • 左端から操作位置まで0が繋がっている場合、つまり  r_{1, 0} \ge i-1 であるときには、操作位置のさらに右まで繋がるので  L_{0} = i+k-1+r_{i+k, 0}

となります(1-indexedです)。

同様の方法で  R_{0} も計算することができて、 L_{0} + k + R_{0} \ge n かどうかでリーチ状態であるかどうかを判定できます。これを1に変更する場合についても全部試して、先攻の全ての操作についてリーチ状態であれば後攻が勝ちです。

パターン3:それ以外の場合

それ以外の場合はどうなるでしょうか。これは実は必ず引き分けになります。

重要な性質として、「1回操作された後の文字列は、直前の相手の操作と全く同じ操作をすることで、文字列を変えないようにできる」ということが言えます。このことから、もし「不利な」文字列があったとして、それが相手から渡されてきた場合は、そっくりそのまま相手に返すことができます。これを永遠に繰り返して引き分けになります。

もう少しちゃんと書くと、後退解析の考え方を用います。

ゲームを解く!Educational DP Contest K, L 問題の解説 - Qiita

つまり、「自分の操作前にどうなっていれば勝ちか/負けか」観点で以下のように状態を分類します。

  • リーチ状態は、もらうと操作1回で勝てるので「勝ち状態(ゲーム終了)」
  • パターン2のように勝ち状態しか相手に渡せない状態は「負け状態」
  • 相手に負け状態を渡す操作が1つでも存在する状態は「勝ち状態」
  • 勝ち状態でも負け状態でもない状態は「引き分け状態(無限ループ)」

として状態(今回は文字列)を分類していきます。

先攻も後攻も1ターン目で勝てなかった場合、先攻が操作した後の文字列は勝ち状態とも負け状態とも言えません。もし負け状態であればその負け状態自身を相手に渡せるので負け状態の定義に合いません。負け状態が存在しない以上、リーチ状態でない勝ち状態も存在しません。

このことからこれは引き分け状態であり、ゲームの結果としては引き分けになることが分かります。

ACコード

Submission #56916660 - Codeforces

複数ターンに渡る操作を考えようとするとものすごく大変なので、まずは「1ターン目で決着がつかなかったら必ず引き分け」ということに気づけるか。そしてパターン2の判定を効率的な計算量で実現できるか。この2点がキモでした。

AtCoder Beginner Contest 133 F - Colorful Tree

F - Colorful Tree

解法

木の2点間距離たくさん→LCA

長さの変更についていったん無視すると、この問題は「木の2点間距離をたくさん求めてください」というものです。これはLCA(最小共通祖先)というものを用いると効率的に求めることができます。

根付き木における2頂点のLCAとは、それらの共通祖先のうち最もその2頂点から近い頂点のことです。2頂点からそれぞれ根までのパスを考えた時に合流するところ、とイメージしてもよいです。

これを用いると、2点間の距離は以下のように求めることができます。

  • 前計算
    • 適当に根を決める。
    • あらかじめ、根から全点への距離を求めておく。根と頂点  v の距離を  d_{v} と表す。
    • 2点のLCAを効率的に求めるための前準備をしておく。
  • 頂点  u, v の距離の計算
    • 頂点  u, vLCAを求める。これを  l とする。
    • 頂点  u, v 間の距離を、 d_{u} + d_{v} - 2d_{l} と求める。

f:id:betrue12:20190707233844p:plain

LCAを効率的に求める方法としてはダブリングなどがあります。(仕組みや実装例は蟻本などを参照してください)

各クエリで辺の値が変わるときにもこのテクニックは使えます。つまり各クエリ  (x, y, u, v) に対しては、 l u, vLCAとして「色  x の辺の長さを全て  y に変えた時の、ある1頂点と根との距離を求める」ことを  u, v, l の3頂点について求めればよいことが分かりました。これ以降は根との距離を上手く求めることを考えていきます。

長さ変更の影響を考える

 x の辺の長さを  y に変えた時の、頂点  v から根までの距離は

  • 頂点  v から根までの経路の…
    • 初期状態における距離  D_{v}
    • 経路中にある色  x の辺の長さ合計  d_{v, x}
    • 経路中にある色  x の辺の本数  n_{v, x}

これらを用いて  D_{v} - d_{v, x} + yn_{v, x} と求めることができます。

これらの値のうち、 D_{v} を全点について求めることはDFSなどで根から順に計算していけば  O(N) で可能です。一方色に依存する  d_{v, x} n_{v, x} は、色ごとに計算すれば求めること自体は  D_{v} と同様にDFSでできるものの、全ての頂点×色の組み合わせが  O(N^{2}) 個あるので全部求めるとTLE/MLEなどになってしまいます。

クエリ先読み!

そこでまず、DFSをしながら「今見ている頂点についての  d_{v, x}, n_{v, x} はいくつか?」という値を全ての色  x について管理していくことを考えましょう。DFSで1歩進む・戻るときに通る辺は1本なので、その辺の色についての情報だけを変更すればよいです。

これを全ての頂点×色について記憶するとTLE/MLEになりますが、クエリは事前に分かっているので必要なところだけを記憶しておくことができます。各クエリに対して必要な頂点と色のペアは3個なので、必要になるのは全部で最大でも  3Q 個のペアです。あらかじめこれを列挙して頂点ごとに分類しておき、DFSしながら各頂点を通る時に必要な色についての値だけ記憶しておくようにすれば、DFSと差分更新に  O(N) 、値の記憶に(mapなどを使うことを想定して) O(Q\log Q) の時間計算量で前計算をすることができます。

あとはこの前計算結果を使って、各クエリに対してこれまで書いてきた計算式を用いれば答えを求めることができます。

ACコード

Submission #6301894 - AtCoder Beginner Contest 133

AtCoder Regular Contest 085 E - MUL

お題箱より。

E - MUL

解法

私自身、この問題は解説を読んで衝撃を受けた記憶があります。知らないと自力で思いつくのは相当難しいので、テクニックとして覚えてしまいましょう。

先人の知恵

競プロでは俗称「燃やす埋める問題」と言われている問題カテゴリです。この言葉で調べると競プロ関連の情報が出てくると思いますが、特に以下の2つの解説がオススメです。

私の解説もだいたいこの2つの解説と同じような説明になりますが、今回の問題でどのように解いていくかを具体的に書いていこうと思います。

「燃やす埋める問題」の定式化

「燃やす埋める問題」は、以下のように表現できる問題、およびそれを解くテクニックの呼び方です。これは基本形で、上記リンク先(特に診断人さんのスライド)には色々な応用が紹介されています。

  •  N 個の要素があり、それぞれについてAとBの2択の選択肢がある。

今回の問題では、各宝石を「残す」と「割る」の2択です。

  • 各要素の選択肢それぞれについて、報酬や罰金が設定されている。

今回の問題では、残すと  a_{i} 円の報酬(負なら罰金)。割るとプラマイ0円。

  • 以下のような条件がたくさん存在する。
    • ある2要素  x, y について、" x はBだけど  y はA" という選び方にすると罰金が発生する。もしくは、この選び方にすることができない。

この条件への対応付けは少し言い換えが必要です。今回の問題の「正整数  x を選ぶ。 x の倍数が書かれた宝石を全て叩き割る。」という条件は、「2以上の整数  k について、 x を割って  kx を残すことはできない」と言い換えることができて、この条件の形になります。

  • 罰金の最小化(報酬の最大化)をしたい。

こんな問題です。

グラフを作る(仮)

このように表現できる問題を、以下のようなグラフの最小カット問題に帰着させて解きます。 N=4 とします。

f:id:betrue12:20190705005603p:plain

f:id:betrue12:20190705005611p:plain

グラフの作り方を言葉で書くと以下のようになります。

  • 各条件を真ん中に並べて、始点  S からの辺と終点  T への辺をそれぞれ張る。
  • 始点側の辺には選択肢A(残す)の罰金を、終点側の辺には選択肢B(割る)の罰金を重みとして設定する。報酬は全て罰金に言い換える。
  • 「" x はBだけど  y はA" という選び方にすると罰金」という条件それぞれについて、AからBにその罰金を重みとする辺を張る。「できない」場合は罰金  \infty とする。

このグラフにおける最小カット、つまり「始点から終点まで到達できないようにするために切る辺集合」(これをカットと呼びます)の重み合計の最小値が、この問題における罰金の最小値になります。

ここで真ん中の頂点それぞれについて、始点側と終点側の2辺のうち必ず一方は切らないといけません。この辺を「切る」ことが、対応する選択肢を「選ぶ」ことに対応します。繋がっている方を採用するわけではないことに注意してください。

※ここで「両方切ったほうがトータルで得になる可能性はないの?」という疑問が浮かぶかもしれません。最後に補足します。

そして「" x はBだけど  y はA" という選び方にすると罰金」という条件については、そっちの辺を切ったときにカットが成立しない方向に辺を張る、と覚えましょう。

f:id:betrue12:20190705013402p:plain

「解ける」ように条件を整える

この最小カット問題を解くために、いくつか条件を変形して整える必要があります。先ほど既に書いたものもありますが、確認していきましょう。

まずは全部罰金にして最小化問題に

先ほども書いたように、これは罰金を辺の重みとするグラフの最小カット問題になります。そのため「  a_{i} 円の報酬」を「 -a_{i} 円の罰金」と言い換えることで全条件を罰金にして、罰金を最小化する問題にします。

「できない」は  \infty 円の罰金に置き換える

先ほど書いた通りです。実装上は十分大きい数とします。

全部の罰金を非負にする

最小カット問題をよく知られたアルゴリズムで高速に解くためには、全ての辺重みが非負である必要があります。例えば正の報酬を罰金に置き換えると負の罰金が生まれてしまうので、これを上手く非負の罰金に変換します。

今回の場合は、 a_{i} が正のときに「残すと  -a_{i} 円の罰金、割ると0円の罰金」となって負の罰金が登場します。これを

  • 無条件で  a_{i} 円もらえる。 その上で、残すと0円の罰金だが、割ると  a_{i} 円の罰金(もらったものを没収されるイメージ)

と置き換えます。こうすると罰金を非負にすることができます。これは今回の問題に限らずよく使うテクニックです。

グラフを作る(改)

具体的に、入力が

4
1 -3 1 2

の時のグラフを描いてみましょう。先ほどの方法で罰金を非負にしないようにすると、以下のグラフを得ます。

f:id:betrue12:20190705005624p:plain

あとは最小カット問題を解きます。この解は「最大フロー最小カット定理」より最大フロー問題の解と一致するので、最大フロー問題を効率的に解くDinic法などのアルゴリズムで解くことができます。

例えば先ほどの入力例では、以下が答えになります。

f:id:betrue12:20190705005633p:plain

おまけ:「両方切る」可能性は考えなくて良い?

先ほど書いた、「始点側と終点側の辺を両方切ったほうがトータルで得になる可能性はないの?」という話です。もし仮にこれが最適解になってしまうと、「 N 個の要素の2択を選んでいく」元の問題との対応が取れません。

これは両方切ることが得になりそうなグラフを実際に考えてみると分かります。ある頂点  i について、始点からの辺と終点への辺がどちらも正の重みを持ち、最小カットにおいてどちらも切られているとします。

まず最適解において始点からの辺が切られている場合、以下のような経路が存在しているはずです。もしこのような経路がない場合は、単にこの辺を切らないようにして値を改善できるからです。

f:id:betrue12:20190705012238p:plain

同様に終点への辺が切られている場合は、以下のような経路が存在しているはずです。

f:id:betrue12:20190705012250p:plain

これをつなげると…以下のように始点から終点への経路ができてしまいます。

f:id:betrue12:20190705012307p:plain

これは最小カットだという仮定で出発したのに、カットになっていません。つまりこのことから、「始点からの辺と終点への辺がどちらも正の重みを持ち、最小カットにおいてどちらも切られている」ということは有り得ないことが分かります。

ただしこれはあくまで、今回紹介した方法で構成したグラフに限定した証明です。私自身、別の問題で最小カットに帰着したときに「余分に切ったほうが得になる場合がある」ようなグラフを作ってしまってACできなかった経験があるので、とても重要な着眼点だと思います…。

ACコード

Submission #6238817 - AtCoder Regular Contest 085

ちゃんと手元で図を描いて、どっち側の辺を切ることがどっちの選択肢に対応しているかも書いて、グラフを構成していくのが慣れるコツだと思います。

類題

比較的考察がやさしい類題です。AtCoderだとフローに帰着するまでが難しい問題が多いので、Codeforcesから。

Problem - 1082G - Codeforces

Codeforces Round #570 (Div. 3) F. Topforces Strikes Back

ちょっと変わった解き方をしたので記録。

Problem - F - Codeforces

(追記)公式Editorial もこの解き方でした。

問題概要

以下の問題を  q ケース解け。

  •  n 個の正整数  a_{1}, ..., a_{n} が与えられる。この中から3個以下の整数を「どの2要素も約数・倍数の関係にない」という条件を満たすように選んだ時の、合計値の最大値を求めよ。

制約

  •  1 \le q \le 2\times 10^{5}
  • 各ケースについて、
    •  1 \le n \le 2\times 10^{5}
    •  2 \le a_{i} \le 2\times 10^{5}
  • 全ケースの  n の合計は  2\times 10^{5} 以下

解法

「どの2要素も約数・倍数の関係にない」ことを単に「条件を満たす」と書くことにします。

同じ整数を2個以上選ぶことはできないので、とりあえず重複要素を除いておきます。以降は全要素が異なっているとします。

貪欲で行けないか?

 O(n^{2}) 以上の解法は通りそうになく、DPを組むのも難しそうなので、貪欲を疑ってみます。大きい方の要素から決められると嬉しいので、試しに「一番大きい要素を取ると決めてしまって良いだろうか?」「もしそれがダメなら、どのような反例が考えられるか?」を考えてみましょう。

具体的には、一番大きい要素を  M として、 M より小さい3個以下の要素を条件を満たすように選んだと仮定します。ここから  M を選ぶように変更することで、ほとんどの場合では値をより良くできることを示します。

選んだ要素の中に  M の約数が何個含まれるかで場合分けします。

 M の約数が0個の場合

この場合、どれか1個の要素を選ばないことにして代わりに  M を選ぶことで値が改善します。どれも  M の約数でないので条件に違反することはありません。

 M の約数が1, 2個の場合

この場合、 M の約数であるものを選ばないことにして代わりに  M を選ぶと、条件に違反せずに必ず値が改善します。なぜなら  M の約数で  M でないものは  \frac{M}{2}, \frac{M}{3}, \frac{M}{4}, ... のいずれかであり、この中から1個または2個を選んだ和は必ず  M よりも小さくなるからです。

 M の約数が3個の場合

同様に「 M の約数を全部外して代わりに  M を選ぶと値が改善する」と言いたいところですが、3個ある場合は少しだけ事情が違います。3個の和が  M を超えるものが1パターンだけ存在し、それは  \frac{M}{2} + \frac{M}{3} + \frac{M}{5} = \frac{31}{30}M の3個を選んでいる場合です。これは親切にサンプルにも含まれています。

これ以外に和が  M を超えるパターンがないことを示します。先ほどと同様に、 M の約数で  M でないものは  \frac{M}{2}, \frac{M}{3}, \frac{M}{4}, ... のいずれかであることを使います。

まず、3個全てが  \frac{M}{3} 以下だと和が  M を超えられないので、 \frac{M}{2} は必ず含まれている必要があります。そうすると  \frac{M}{2} の約数となる  \frac{M}{4}, \frac{M}{6}, \frac{M}{8}, ... は採用できません。

あと2個で残りの  \frac{M}{2} を超える必要があるので、同様の理由で  \frac{M}{3} が必ず含まれる必要があります。そうなると最後の1個はどちらの約数でもない  \frac{M}{5}, \frac{M}{7}, \frac{M}{11}, ... から選ぶ必要があり、 \frac{M}{2} + \frac{M}{3} + \frac{M}{7} =  \frac{41}{42}M \lt M であることから、最後の1個は  \frac{M}{5} しかありえません。

以上の考察を踏まえて

つまり、答えは以下の2通りのどちらかに絞られます。

  1. 最大要素  M を使うと仮定したときに実現できる最大値。
  2.  \frac{M}{2}, \frac{M}{3}, \frac{M}{5} が全て含まれている時に限り、これら3個を選んだ合計値  \frac{31}{30}M

最大要素を使うと仮定すれば、あとは  M の約数を全て消した上で、約数・倍数関係でない残り2個の合計を最大化する問題になります。これは先ほどの「 M の約数が2個以下」のときの議論がそのまま使えて、やはり選べるものの中で最大のものを2個目として選ぶのが最適となります。さらに残ったものの中から3個目を選べば良いので、結局3個とも大きい方から貪欲で選べます。

 \frac{M}{2}, \frac{M}{3}, \frac{M}{5} が全て存在する場合は貪欲解と  \frac{31}{30}M の大きい方を採用し、存在しない場合は貪欲解をそのまま答えとすれば良いです。ソートやsetの利用などを考慮して、ケースごとに計算量  O(n\log n) で解けます。

ACコード

Submission #56104187 - Codeforces