全国統一プログラミング王予選 参加記
全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder
全国統一プログラミング王予選に参加したので、僕のコンテスト中の思考の過程を垂れ流しておきたいと思います。
A - Subscribers (100)
求めたいのは重複の最大と最小。最大はmin(a,b)。最小は…max(0,a+b-n)。(1:34 AC)
B - Touitsu (200)
求めたいのは3つの文字列を一致させるのに必要な最小編集回数。まずはi文字目を一致させるために何回必要か考える。3つ同じなら0回。2つ同じで1つ違いなら1回。3つ違うなら2回。i文字目の回数の計算方法が分かったのであとはN文字目までの総和を求めればいい。(5:21 AC)
C - Different Strokes (400)
求めたいのは(自分の得点)-(相手の得点)の最大値。制約からDPはできないので貪欲で考える。差を最大化したいのでB-Aでソートだろうか。しかし小さなケースで実験すると、
2
1 2
2 3
のケースは2つの差は同じなのに取る順によって結果が変わる。なので単純に差をとるだけでは優先度はわからなそうだ。いろいろ実験を続けると、
2
1 3
2 2
のケースでは 取る順を変えても結果が変わらない 。なのでこの2つは 同じ価値 だと考えられる。2つに共通しているのはA+B。なので今度はA+Bに注目して考る。すると実際A+Bが大きい順で貪欲するとうまくいった。未証明だけどこれを提出してみる…。(AC 20:18)
D - Restore the Tree (500)
やりたいことは根付き木の復元。サンプルを試してみると一意に復元できなさそうだったが、よく制約を読み直すと、
書き足された各辺
u
→
v
は、ある頂点
u
からその子孫であるような頂点
v
に向かって伸びています。
と書かれていたのでこれなら一意に定まるとわかる。
やることはまず、根の入り次数が0なのでそこを確定させる。次に根からのびる辺を削除する(実際には行先の入り次数を1減らす)。すると根の直接の子の入り次数は0になっているはずなのでそれを確定させる。あとはその子を根とした部分木を考えればいいので再帰的に確定させていく。(AC 45:11)
E - Weights on Vertices and Edges
解けなかったが最小全域木ぽさを感じたので辺を小さい順につないでうまくいくところまでやるのかなと考えていた。ただ辺を除くと非連結になってUF木が壊れるのでうーん...
コメント
結果はABCD4完で順位305位、パフォーマンス2022でした。初の黄パフォが出せて成功回でした。
Cは沼にはまるとなかなか抜け出せず強い方でも時間がかかったり解けなかったりしたそうです。むしろDのほうがグラフ理論の経験があればストレートな解法だったと思います。
(2019/1/29 追記) 予選通過しました！ 本戦もがんばります。
