NIKKEI Programming Contest 2019 参加記録＆解説（A～E）

Dまでがまずい感じでしたが、無事Eを通して予選突破！

f:id:betrue12:20190128201220p:plain

A～Eの5問を振り返ります。

A - Subscribers

解法

最大値については、新聞 $X, Y$ を取る人をなるべく被らせたいので $\min(A, B)$ が答えです。

最小値については、新聞 $X, Y$ を取る人をなるべく被らせたくないので、 $A+B$ が $N$ 以下であれば0。 $N$ を超えている場合はどうしても $A+B-N$ 人は被ってしまうので、これが答えです。

ACコード

（Ruby）Submission #4096948 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

Touitsu

B - Touitsu

解法

同じ位置（インデックス）の文字3つを比較し、これらを全て一致させるための操作回数を考えます。全部同じであれば0回、2つだけが同じであれば1回、全て違っていれば2回の操作回数が必要です。これを全インデックスについて足し合わせると答えになります。

ACコード

（Ruby）Submission #4097798 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

C - Different Strokes

解法

こういった問題を考える上では、まず「2つの要素があったとき、取るべきなのはどちらか」を考えるとよいです。より汎用的には「2つの要素を交換したらどうなるか？」と言うこともできます。

仮に料理が番号 $1, 2$ の2つしかなくて、今が高橋くんのターンだとします。高橋くんが1を取ると青木さんが2を取り、高橋くんの利得は $A_{1} - B_{2}$ です。高橋くんが2を取り青木さんが1を取ると、高橋くんの利得は $A_{2} - B_{1}$ です。

このことから、高橋くんが2よりも1を取ったほうが良い条件は $A_{1} - B_{2} \ge A_{2} - B_{1}$ と定式化され、これを移項して料理1の要素と料理2の要素に分離すると $A_{1} + B_{1} \ge A_{2} + B_{2}$ となります。この条件が満たされるとき、高橋くんは料理2よりも料理1を取るべきです。

一方青木さんのターンで同じことを考えると、やはり同様に $A_{1} + B_{1} \ge A_{2} + B_{2}$ のとき青木さんは料理2よりも料理1を取るべきだという結果になります。

この結果を一般化すると、高橋くん・青木さんどちらも「残っている料理の中で $A_{i} + B_{i}$ が最大のものを取る」という戦略が最適であることが分かります。料理の総数が一般の $N$ 個であっても、もし $A_{i} + B_{i}$ が最大のものを取らない場合は、相手にそれを取られてより損をしてしまうからです。

あとはソートしてシミュレーションすれば高橋くんの利得が求められます。この問題のように複数の料理にまたがるような利得がない場合は、2つの要素で比較した結果を要素数 $N$ のときに一般化する、という解法が有効であることが多いです。

ACコード

D - Restore the Tree

解法

まずは根を探したいです。元の根付き木の性質として、根の入次数は0であり、それ以外の頂点の入次数は1です。さらに書き加えた辺は先祖から子孫に伸びているため、根に辺が向いていることはありません。そのため頂点の中で入次数が0である頂点はちょうど1つ存在するはずで、それが根です。

根が見つかったら、元からあった木を復元します。このとき書き加えた辺が先祖から子孫に伸びていて、また制約から多重辺がないので、書き加えた辺は元の木を「ショートカット」するように生えているはずです。以下は入力例2に対応するグラフですが、赤で記載した追加辺は確かにショートカットになっています

f:id:betrue12:20190128210448p:plain

このことから根から各頂点への最長経路を辿っていけば、そのときに通った経路が求めたい木であり、遷移元を記録しておけば出力すべき「各頂点の親」を求めることが出来ます。

DAG（閉路のない有向グラフ）における最長経路問題は、トポロジカルソート順でDPをすることで解けます。こちらの資料が分かりやすいです。

動的計画法入門(An introduction to Dynamic Programming)

ACコード

（C++）Submission #4104614 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

E - Weights on Vertices and Edges

解法

問題文の通りに考えると、以下のような操作をすればよいです。

最初はグラフが連結なので、全ての頂点の重み和を計算し、それを超える重みの辺を削除する。
これによって連結成分が分断されてしまった場合、各連結成分の頂点重み和は減ってしまうので再計算をする。それぞれの連結成分ごとに、頂点重み和を超える重みの辺はやはり削除する。
これを全ての辺が削除されなくなるまで繰り返す。

ただしこれを処理しようとすると、連結成分の分断を考える必要があり面倒です。

そこで処理を逆から考え、辺がない状態から始めて使う辺をなるべく多くすることを目指します。辺を追加していく方向で考えると、連結成分の分断ではなくて併合を扱うのでUnion-Findを利用することが出来ます。

辺を追加していく場合、どのような順序で辺を考えていけばよいでしょうか。辺が追加されることで連結成分が広がり条件が緩くなるので、それぞれの辺を独立に考えることはできません。また「1本辺を追加するごとに、他の辺を追加できるようになったかを1本1本判定する」等のアルゴリズムでは間に合いません。

ここで問題文の条件に注目すると、連結成分の頂点重みの和が、その連結成分で一番重い辺以上であればよいということが書いてあります。そのため、ある重み $w$ 以下の辺だけで構成される連結成分1つの頂点和が $w$ 以上であるときには、その辺たちは全て使って良いことが分かります。

このことから、以下のような手順で使う辺を決めていくことが出来ます。

Union-Findを用意し、辺の重みが小さい順に辺を「仮で」追加し、頂点を併合していく。この追加は、必ずしもこの辺が使えるということを意味しない。
もし重み $w$ の辺を追加したときに、Union-Findにおいてその辺が属する連結成分の頂点重み和が $w$ 以上だったとする。このとき辺の重みが小さい順に追加しているので、その連結成分に含まれる辺の重みは全て $w$ 以下であり、先ほどの考察よりその連結成分に今まで追加した辺を全て使うことができる。
この操作を、全ての辺を追加し終わるまで続ける。

この手順で使う辺を決めてしまえば、使えなかった辺の数が答えになります。

手順の2. で「その連結成分の頂点重み和を取り出す」「その連結成分に今まで追加した辺の本数を取り出す」という処理が必要になりますが、これはUnion-Findに今まで追加した頂点の重み和や辺の本数を記憶させておくことで実現することが出来ます。連結成分のサイズを持たせておく実装はよくあると思いますが、それと要領は同じです。