NIKKEI Programming Contest 2019
10分で３完したあとは椅子を温めて、ぎりぎり青パフォ(1639)でした。
A - Subscribers (100点)
問題: A - Subscribers
新聞 X を購読している人が全員新聞 Y を購読している場合と、それの X と Y を逆にした場合に、両方の新聞を購読している人が最大になって、人。
逆に、両方の新聞を購読している人が最小の時は、なるだけ全員どちらかの新聞を購読していることにして辻褄を合わせると、人。
これらを出力してAC。ベン図を描くとわかりやすいと思う。
拙解 (C++):
Submission #4097313 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
B - Touitsu (200点)
問題: B - Touitsu
について一文字ずつ順に見ていく。
が相異なら、どれか二つを他一つと同じ文字に変えるのに２回操作が必要。
のどれか２つが同じで１つだけ違うなら１回の操作で３つ揃う。
がすべて同じなら何もしなくてよく、０回の操作で済む。この操作回数を足していった総和を出力すればAC。
拙解 (C++): Submission #4098593 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
C - Different Strokes (400点)
問題: C - Different Strokes
この食事会は、高橋くんから見ると「料理を食べると自分が幸福度
を得て、相手が幸福度
を失う」ものとなり、青木さんから見ると「料理
を食べると自分が幸福度
を得て、相手が幸福度
を失う」ものとなる。そして互いに「(自分の得る幸福度) - (相手が得る幸福度)」を最大化する。
したがって、この食事会の最適戦略はどちらから見ても「が高い順に料理を食べる」となるので、最初の料理から
を１つ飛ばしで足していって、その総和から
の総和を引いた値を出力するとAC。
つまり、青木さんが全部食べると求める値がになり、そこから高橋くんが青木さんの妨害をして
を得ていく、と考えるとすんなり解ける。
拙解 (C++): Submission #4100297 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
D - Restore the Tree(500点)
問題: D - Restore the Tree
コンテスト中にトポロジカルソートじゃないか？と思いつつ解いたが、頭の中でトポロジカルソートとヒープソートを混同しており、TLEを連発した。結局解けたのはコンテスト終了後20分ほど後になってからだった。
要するに、木の親子関係は変わらないようにDAGに冗長な辺が足されるので、これをトポロジカルソートしてノードの親子関係を求める。具体的には、この問題の制約下では根は一つしかないので、各ノードの入次数を計算してこれが０になるものを探して、これが根になる。その根を除去して、繋がっているノードのうち入次数が０になるものがもともとの木でのその根のもともとの子になる。これを頂点がなくなるまで繰り返して、制約の通りに各ノードのもともとの親を1-indexedで出力してAC。
拙解 (C++, コンテスト後解説AC): Submission #4110871 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019
まとめ
早解きばっかして序盤のいっときだけ橙パフォで100位付近とかいうふざけた立ち回りをしていました
一時だけとはいえ予選突破順位に入って草
— Ganmodokix (@AprilGanmo) January 27, 2019
そろそろ水色も中位にさしかかっている(レート1337)ので、ちゃんとアルゴリズムを覚えないとだめなことを
400点をぱぱっと解いて500点がコンスタントに解ければ青も遠くはないと信じています
