NOMURA プログラミングコンテスト2020

NOMURAプログラミングコンテスト2020に参加しました。

ABC169と順番が前後しましたが、このコンテストではそれなりに結果がよかったので後回しになりました。

ABCの三完でした。Dはコンテスト中にはどうしていいのか分からずに諦めましたが、今日明日中には解説を見てACしておきたいです。

NOMURA Programming Competition 2020 - AtCoder

All Submissions - NOMURA Programming Competition 2020

A-Study Scheduling

ABCよりかはさすがに難しいですね。制約があるので、寝る時刻から起きる時刻を引いて、さらに勉強時間を引いて出力します。

たったそれだけのはずなんですが、コードを書くのに手間取って出遅れてしまいました。

B-Postdocs

一見するとDの前にはPを置いた方がいいような気がしますが、よく考えてみると？を全てDにしたものでも博士・PD指数を最大化できます。具体的には、？Dとなっていたときは、？がPでもDでも指数は2になりますが、？Pとなっていたときは、？がDのときのみ指数が1になります。最大のものを1つ求めるだけなので、全ての？をDに置き換えて出力します。

C-Folia

グラフの問題は正直得意ではないと思っていたのですが、D以降も軽く目を通してみてCが一番解けそうだったので考えてみることにしました。

パッと見てすぐに分からない時は、具体的な数字を用意したりサンプルの数字を使ったりして実際に書いてみることにしています。今回は二分木ということなので、各頂点はそれぞれ子を0個1個2個のいずれかの数だけ持つことができます。子の数が0個の頂点(葉)の数は各深さですでに決められています。なので、次の深さに子を持てる数は、頂点から葉を引いたものになります。頂点数を最大化したいので、葉以外の頂点はそれぞれ2個の子を持つようにできれば答えになると考えてグラフを書いてみました。すぐにこの方法では深さNのところで葉の数が入力を超えることが分かりました。グラフを眺めていると、当たり前のことなのですが各頂点が子を辿ってグラフの下にどんどん降りていくと最終的に葉にたどり着かないといけない(子がある場合はまだ下に行くことになる)、ということが分かります。つまり、子の数によってその元の頂点(親？)の数がある程度制限されます。深さNには葉しか存在しないため(子を持つ場合は深さがN+1になるから)、深さNの頂点の数は確定しています。深さNの頂点の数が決まっているので、深さN-1の頂点の数もある程度範囲を絞ることができます。具体的には((深さNの頂点の数+1)/2+深さN-1の葉の数)から(深さNの頂点の数+深さN-1の葉の数)までです。この要領で、グラフの下から順に各深さで取ることのできる頂点の数の範囲が決まっていきます。これをあらかじめ求めておけば、深さ0では頂点は一つしかなく、1つ下の深さに行くときには子は2つまでしか持てないので(二分木のなので)、上から順に先に求めた範囲の中で最大になるように頂点を取っていくことで、頂点数の最大値を求めることができます。

上記のコードを何とか書き上げて終了10分前に何とかACできました。

Cまで何とか解くことができてよかったです。少しずつできることが増えていると実感すると嬉しいです。