NOMURA プログラミングコンテスト 2020
コンテスト前のレート:1793
レート通りのパフォーマンスが得られる順位:724位
前回の100-200-600-配点の時、A問題で1ペナ、C問題が解けずで緑パフォになってしまったので、それと同じような結果だけは回避したいと思いながら参加。
A - Study Scheduling
問題
時間を扱うだけで一瞬ややこしそうな印象を受けたけどそんなことはなかった。
問題概要
時分から時分の間に連続した分の勉強時間を取るとき、勉強を開始することができる時間帯の長さは何分か。
- 時分は時分より分以上前の時刻
- 入力は全て整数
思考過程
- とりあえずを計算してそれぞれ分単位に直す。
- それらの差からさらにを引く。
- 念のためマイナスになった場合はにしておく。
※コンテスト中は時分は時分より前という制約しかまともに目に入っておらず、上記3.は必要はなかったことに後から気付いた。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int h1 = sc.nextInt(); int m1 = sc.nextInt(); int h2 = sc.nextInt(); int m2 = sc.nextInt(); int k = sc.nextInt(); sc.close(); int a = h1 * 60 + m1; int b = h2 * 60 + m2; System.out.println(Math.max(b - a - k, 0)); } }
ここまで1分45秒+0ペナ。412位。
B - Postdocs
問題
落ち着いて考えればほぼABC-Bと変わらないレベル。
完全に灰色難易度っぽくて運営の正気を疑う。
問題概要
'P'、'D'、'?' からなる文字列がある。
に含まれる '?' をそれぞれ 'P' または 'D' のいずれかに置き換えてできる文字列の中で、連続する部分文字列として含む 'D' および 'PD' の個数の和が最大となる文字列を求めよ。
思考過程
- とりあえず 'PD' より 'D' の方が短いので、全部 'D' に変えてみる。
- 変えたところのどれかを 'P' に変えると、 'PD' は0個か1個増え、 'D' は1個減る。
- 全部 'D' に変えるのが最適としか思えなかったが、ペナルティが怖いので見落としがないか1分ほど悩んでから提出。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); String t = sc.next(); sc.close(); System.out.println(t.replaceAll("\\?", "D")); } }
ここまで4分54秒+0ペナ。462位。
Cが300人くらいしか解けないような問題でも大丈夫だろうと一安心。
C - Folia
問題
Bまで終わって順位表確認した時点ではまだ正解者0人だったし、ぱっと見でも結構難しそう。
解けたのは良かったが、正解者数多すぎでスピード足りてなくて辛い。
問題概要
長さの整数列~が与えられる。
深さの二分木であって、に対して深さの葉の個数がちょうどであるものについて、頂点数の最大値を求めよ。
そのような二分木が存在しない場合はを出力せよ。
- 入力は全て整数
思考過程
- 例2で考えてみると、最下層の頂点が個となり、最後の深さ3→4のところで枝分かれするより、もっと浅いところから1本道状態のものを2本作った方が頂点数が増えそう。
- 下から見ていってできるだけ1本道にすることを考えるなら、例5では、10層の頂点数が個、9層は下に続く個と新たな葉の個を足して個、8層は個、のようにを後ろから足していくのが最大となる。
- 上から見ていけば、完全二分木だとしても、0層が個、1層が個、2層が個、が限度。途中に葉を作る場合があるともっと少ない。
- 上から頂点数の限度を求めていこうとすると、各層で葉の数を引いて倍を繰り返せば求まる。途中で限度がマイナスになったら構成不可。
- 上からと下からそれぞれ求めた最大値のminを取る方針で手計算し、例5が合ったのでそれで実装することにする。
- 上からの方は、なので、そのまま2倍していったのではlong型の範囲は余裕でオーバーする。の最大値を超えたらINF(適当にInteger.MAX_VALUE)にしておけばよい? →41ケース中7ケースWA
- 7ケースだけなので大筋は合っていそうな気がするが、何か構成可否の条件が足りないのか?などとしばらく悩んだりもしてようやく、INFが以上くらいは必要なことに気付く。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n + 1]; for (int i = 0; i < a.length; i++) { a[i] = sc.nextInt(); } sc.close(); long inf = 1000000000000000L; // 10^15(適当に10^13以上) long[] max = new long[n + 1]; // 上からのmax max[0] = 1 - a[0]; if (max[0] < 0) { System.out.println(-1); return; } for (int i = 1; i <= n; i++) { max[i] = max[i - 1] * 2 - a[i]; // 1つ上層*2 - 葉 if (max[i] < 0) { System.out.println(-1); return; } // INF以上になったらそれより下層は全部INF if (max[i] >= inf) { for (int j = i; j <= n; j++) { max[j] = inf; } break; } } long ans = 0; long sum = 0; for (int i = n; i >= 0; i--) { sum = Math.min(sum, max[i]); ans += a[i] + sum; sum += a[i]; } System.out.println(ans); } }
ここまで52分55秒+2ペナ。801位。
801位の時点で既に冷え確定で、さらに2ペナ分下がるの辛い。
E問題もチラ見したが、途中の順位表確認時点ではD問題の方が倍くらいの正解者数いたので、残り時間のほとんどはD問題に費やした。
どちらにしろ赤難易度で無理だったが。
D問題は、必要な道の数は連結成分の数なので、連結成分の数ごとに数え上げたいと思い、「:まだ連結成分に取り込まれていない町が個、連結成分の数が個の場合の数」とかを考えてみては、遷移が計算できなかったりして破滅していた。
最終結果:ABCの3完、62分55秒、914位、パフォーマンス1660
レート変動:1793→1781
まあ大事故を回避しただけでもマシだったかなという感じ。
配点からは、最高の場合は「灰-茶-青-黄-橙-赤」くらいの難易度を期待していたけど、実際は「灰-灰-水-赤-赤-赤」。
このセットでちゃんと実力を測れるレートの範囲は一体どこになるのか?