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

コンテスト前のレート:1793
レート通りのパフォーマンスが得られる順位:724位

前回の100-200-600-配点の時、A問題で1ペナ、C問題が解けずで緑パフォになってしまったので、それと同じような結果だけは回避したいと思いながら参加。

A - Study Scheduling

問題
時間を扱うだけで一瞬ややこしそうな印象を受けたけどそんなことはなかった。

問題概要

H_1M_1分からH_2M_2分の間に連続したK分の勉強時間を取るとき、勉強を開始することができる時間帯の長さは何分か。

  • 0 \leq H_1, H_2 \leq 23
  • 0 \leq M_1, M_2 \leq 59
  • H_1M_1分はH_2M_2分よりK分以上前の時刻
  • K \geq 1
  • 入力は全て整数
思考過程
  1. とりあえずH \times 60 + Mを計算してそれぞれ分単位に直す。
  2. それらの差からさらにKを引く。
  3. 念のためマイナスになった場合は0にしておく。

※コンテスト中はH_1M_1分はH_2M_2分より前という制約しかまともに目に入っておらず、上記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'、'?' からなる文字列Tがある。
Tに含まれる '?' をそれぞれ 'P' または 'D' のいずれかに置き換えてできる文字列の中で、連続する部分文字列として含む 'D' および 'PD' の個数の和が最大となる文字列を求めよ。

  • 1 \leq |T| \leq 2 \times 10^5
思考過程
  1. とりあえず 'PD' より 'D' の方が短いので、全部 'D' に変えてみる。
  2. 変えたところのどれかを 'P' に変えると、 'PD' は0個か1個増え、 'D' は1個減る。
  3. 全部 '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人だったし、ぱっと見でも結構難しそう。
解けたのは良かったが、正解者数多すぎでスピード足りてなくて辛い。

問題概要

長さN + 1の整数列A_0A_Nが与えられる。
深さNの二分木であって、d = 0, 1, \ldots , Nに対して深さdの葉の個数がちょうどA_dであるものについて、頂点数の最大値を求めよ。
そのような二分木が存在しない場合は-1を出力せよ。

  • 0 \leq N \leq 10^5
  • 0 \leq A_i \leq 10^8 (0 \leq i \leq N)
  • A_N \geq 1
  • 入力は全て整数
思考過程
  1. 例2で考えてみると、最下層の頂点が2個となり、最後の深さ3→4のところで枝分かれするより、もっと浅いところから1本道状態のものを2本作った方が頂点数が増えそう。
  2. 下から見ていってできるだけ1本道にすることを考えるなら、例5では、10層の頂点数が34個、9層は下に続く34個と新たな葉の21個を足して55個、8層は55+13=68個、\cdotsのようにA_iを後ろから足していくのが最大となる。
  3. 上から見ていけば、完全二分木だとしても、0層が1個、1層が2個、2層が4個、\cdotsが限度。途中に葉を作る場合があるともっと少ない。
  4. 上から頂点数の限度を求めていこうとすると、各層で葉の数A_iを引いて2倍を繰り返せば求まる。途中で限度がマイナスになったら構成不可。
  5. 上からと下からそれぞれ求めた最大値のminを取る方針で手計算し、例5が合ったのでそれで実装することにする。
  6. 上からの方は、N \leq 10^5なので、そのまま2倍していったのではlong型の範囲は余裕でオーバーする。A_iの最大値を超えたらINF(適当にInteger.MAX_VALUE)にしておけばよい? →41ケース中7ケースWA
  7. 7ケースだけなので大筋は合っていそうな気がするが、何か構成可否の条件が足りないのか?などとしばらく悩んだりもしてようやく、INFがN \times A_{max}以上くらいは必要なことに気付く。
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問題は、必要な道の数はN-連結成分の数なので、連結成分の数ごとに数え上げたいと思い、「dp[i][j]:まだ連結成分に取り込まれていない町がi個、連結成分の数がj個の場合の数」とかを考えてみては、遷移が計算できなかったりして破滅していた。



終結果:ABCの3完、62分55秒、914位、パフォーマンス1660
レート変動:1793→1781
まあ大事故を回避しただけでもマシだったかなという感じ。


配点からは、最高の場合は「灰-茶-青-黄-橙-赤」くらいの難易度を期待していたけど、実際は「灰-灰-水-赤-赤-赤」。
このセットでちゃんと実力を測れるレートの範囲は一体どこになるのか?