全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
Updated:
全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
ボーダー付近になってしまいました。日本人 208 位でした。
Source codes
Solutions
A - Subscribers
$(\max(0, a + b - n), \min(a, b))$ を出力する。
B - Touitsu
貪欲にやる。 ary = [] に文字列を放り込む。 $i = 0, \dots, N - 1$ に対し、 hash = {} を作成する。 $ary[j][i]$ の数を出力する。あとは ans += 3 - hash.values.max とする。
ポイント
実装にミスがないことが重要である。 3 つの項を比較するのは結構面倒であるから上にような解答をした。
C - Different Strokes
解法
$(A _i + B _i, A _i, B _i)$ を sort, reverse して、貪欲にシミュレーションすれば良い。
解法の正しさの証明
$(A _i, B _i)$ というカードではなく、 $(A _i + B _i, 0)$ というカードでこのゲームをやることを考える。ただしゲーム開始前の得点は $- \sum _{i \in N} B _i$ 点であるものとする。すると、このカードを取ることは、高橋君にとっては $A _i + B _i$ 点を取ることになるので、元のゲームでは $A _i$ 点を取ることに等しい。青木さんにとっては高橋君に $A _i + B _i$ 点を取らせないことに相当するので、最初のマイナスを考慮すると、元のゲームでのスコアに $- B _i$ 点を与えたことに等しいので、すなわち $B _i$ 点を青木さんが取ることに等しい。改変されたゲームでは $A _i + B _i$ が大きい方から順に取るのが両者にとって最適戦略である。
ポイント
直感で解法がわかったので実装してそれで通った。入出力例が自明なものばかりだったのでますます確信があった。
D - Restore the Tree
まず逆辺を張るのがポイントである。こうすることで隣接リストでグラフを管理した際に empty であるものが root であることがわかる。
木に、子孫に向かって辺を張ったということであるが、この辺は要するに子を飛び越えているわけだから、そこから「逆算される仮の深さ」は必ず「真の深さ」よりも小さくなる。
そこで root の高さを $0$ とする。再帰関数で深さを求める。逆辺を張っているので、深さをそれぞれ求める。そこで最大の深さになったのが真の親である。こうして正しい深さが決定される。これを繰り返す。
ポイント
こうやって書くととても簡単な問題なんだけど、「辺を削除する」に頭が行き過ぎて、正しい解答になかなか至らなかった。
E - Weights on Vertices and Edges
基本的な着想：貪欲法 $O(NM)$ (TLE)
まず $(Y _ i, A _ i, B _ i)$ を降順に検討していく。この中で $A _ i, B _ i$ を含む連結成分の頂点のコストの和を求める。この和が $Y _ i$ 以下であれば、この辺を採用することができる。そうでなければ削除する。これを繰り返す。これが貪欲法に依る解法である。
高速化
この解法の高速化を試みれば良いわけだが、着眼点は大きく次の 2 つである。
- 「この中で $A _ i, B _ i$ を含む連結成分の頂点のコストの和を求める」のうち辺として採用しているものは、コスト $Y _ i$ 以下の辺である。つまり $Y _ i$ の昇順にグラフを連結していけば Union-Find で高速に頂点のコストの和を求めることができる 。
- 「この和が $Y _ i$ 以下であれば、この辺を採用することができる」の部分で、採用できる辺は、実はこの連結成分に含まれる全ての辺である。つまり $Y _ i$ の降順に DFS していけば $O(N)$ で無駄なくチェックできる 。
実装 $O(N \log N)$
まず typedef tuple<ll, int, int, bool> edge; を定義し、 vector<edge> V; に昇順で突っ込んでおく。次に vector<int> W[100010]; で連結リストを作る。ただし今回は $V$ の添字を入力して辺そのものへのリンクとしておく。 2. のために typedef tuple<ll, int> task; を用意しておき、 vector<task> T; とする。
まず 1. を実行する。 Union-Find の merge tech 版を用いて、初期値を $-X _ i$ にしておく。 $V$ から edge を取り出して繋いでいく。辺のコストが、連結成分の頂点のコストの和以下であれば、あとで DFS をするべきである。ゆえに $T$ に突っ込んでおく。
次に 2. を実行する。 reverse(T.begin(), T.end()); とする。 $T$ から出して DFS をする。使う辺ならば get<3>(V[x]) = true; とする。こうすると後ろの低コストの辺を前の方の高コストの辺でカバーしていることになり、無駄がない。そして最後に $V$ の第 $3$ 成分が false であるものの個数が答えである。
計算量は、 edge のソートに $O(M \log M)$ 、今回の Union-Find はならし $O(N \log N)$ である。 DFS は $O(N + M)$ である。ゆえに計算量は $O((N \log N)$ である。
ポイント
わかってしまえば簡単なんだけど、昇順と降順のいいとこ取りをするところが結構難しいと思った。