NOMURA プログラミングコンテスト 2020
2020-06-03
コンテスト中に挑戦した問題についての感想とか.
A - Study Scheduling
２つの時刻の間の時間を分単位で求めてそこから与えられた時間を引く.
いろんなケースを考えなくて良い問題設定がされているので, それだけ.
B - Postdocs
?をDに変えるだけ. 点数計算には高々連続した2文字について考慮すれば良い.
?の前後を考えると, P?, D?, ?D, ?Pの4パターンで尽くせる. ?をPにした場合は3つ目のみ1点加点となるが, ?をDにするとすべての場合で1点加点となるので, すべてDにすれば良い.
例1の様に, 上記の3のパターンでPとするのも間違いではないが判定めんどいので, 全部Dに置き換えた.
C - Folia
C問題解けると思っていなかったので嬉しかった.
深い方から数えるのが良いのか, 浅い方から数えるのが良いのか迷って, 最初は深い方から数えていたが, 途中から根側から数えることに変更.
- 深さが1浅いノードのうち親になりうる数の倍
- 深さが1深い葉の数と考えている深さの葉の数の和
- 深さの2乗
のうち最も小さいものが最大のノード数
- 深さが1深い葉の数割る2(1未満は切り上げ)
が最小のノード数として
指定された葉の数と合わせて比較して木が構成可能かどうかを判断し, 木が構成可能であれば最大ノード数を採用して, 次の深さを調べる.
これを繰り返せばいい.
一番最後に気付いたのは1深い葉の数が最大値にも関係するという点で, これを入れることで例の全ケースを通すことが出来たので提出.
この問題も例として与えられているものが優しかったと思う.