全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

更新日時:

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

ボーダー付近になってしまいました。日本人 208 位でした。

ソースコード

解法のメモ

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

ポイント

F - Jewels

ポイント

その他