東京海上日動　プログラミングコンテスト2020

A - Nickname
- 思考過程
B - Tag
- 思考過程
C - Lamps
- 思考過程
D - Knapsack Queries on a tree
- 思考過程
E - O(rand)
- 思考過程

コンテスト前のレート：1778
レート通りのパフォーマンスが得られる順位：684位

A - Nickname

問題
ABC-Aと同レベルだと思う。

思考過程

substringで連続した部分文字列を取得できる。
最初の3文字にするか最後の3文字にするか一瞬考えて最初の3文字にした。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();

        System.out.println(s.substring(0, 3));
    }
}

ここまで0分46秒＋0ペナ。552位。

B - Tag

問題
平均的なABC-Bより凡ミスが怖い見た目をしている気はするけど、それにしてもちょっと時間かけ過ぎた。

思考過程

$A$ は近付く方向に、 $B$ は遠ざかる方向に動き続けるのが最適。つまり $1$ 秒あたり $V-W$ だけ距離が縮まっていく。
とりあえず $V \leq W$ ならば距離が縮まないので 'NO'。
$T$ 秒間に縮まる距離 $(V-W) \times T$ が最初の $A, B$ 間の距離以上なら 'YES'。
$10^9$ を $2$ 個掛け算するのでオーバーフローに注意。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int v = sc.nextInt();
        int b = sc.nextInt();
        int w = sc.nextInt();
        int t = sc.nextInt();
        sc.close();

        // この判定はいらなかった
        if (w >= v) {
            System.out.println("NO");
            return;
        }

        int d = Math.abs(a - b);
        if ((long) (v - w) * t >= d) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

ここまで4分58秒＋0ペナ。911位。

C - Lamps

問題
こういう問題の計算量見積もりができない。

思考過程

とりあえず愚直にやった場合を考えると、以下の通りでくらい。
- 各電球が照らしている範囲に $+1$ するのが $B_i$ 回。最大 $N$ 。
- 上記の処理を $N$ 回。ここまでが $1$ 回分。
- 上記の処理をさらに $K$ 回。
$B_i$ 回の部分は、いもす法を使えば $O(1)$ となるが、これでも $O(NK)$ 。
数値を適当に変えてみて推移を眺めてみたりするが、特にエスパーできそうな法則は見えてこない。
$K$ が十分に大きければ、最終的には全部 $N$ になる。
推移をもう一度眺めると、各電球の光の強さは、平均的には毎回 $1$ よりはたくさん増えそう？　つまり、全部 $N$ になるまで最悪でも $2 \times 10^5$ まではかからない？
他に計算量落とせる方法も思いつかないので、とりあえずそれに賭けてみる。　→AC

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int k = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        int[] a = new int[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        for (int i = 0; i < k; i++) {
            // 1回分の操作をいもす法で行う
            int[] b = new int[n + 1];
            for (int j = 0; j < n; j++) {
                int l = Math.max(j - a[j], 0);
                int r = Math.min(j + a[j] + 1, n);
                b[l]++;
                b[r]--;
            }
            for (int j = 1; j < b.length; j++) {
                b[j] += b[j - 1];
            }
            a = b;

            // 全部Nなら終了
            boolean all = true;
            for (int j = 0; j < n; j++) {
                if (a[j] < n) {
                    all = false;
                    break;
                }
            }
            if (all) {
                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(a[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで28分17秒＋0ペナ。402位。

D - Knapsack Queries on a tree

問題
30分ほど考えて解けず。

思考過程

クエリ $1$ 回分を普通にナップサックで解こうとすると、それだけで $18 \times L$ くらい。
全部事前計算しておくとすると、 $O(NL)$ は $O(QL)$ よりも悪くて余計に駄目。時間だけでなくメモリも。
クエリを処理する順番を都合よく入れ替えたりしたところで、全部葉付近とかだったら意味はなさそうな気がする。

ナップサックではなく $2^{18}$ 全探索する方向性を全く考えられなかったのが敗因かな・・・。

E - O(rand)

問題
1時間ほど考えて解けず。
結構いいところまで考えた気がしたけど、気がしただけで駄目な方向に向かっていたっぽい。

思考過程

つのビットについて見たときのの組合せ通りを考える。
- $(0, 0)$ の場合、 $0$ しか選べない。
- $(0, 1)$ の場合、 $0$ と $1$ をそれぞれ $1$ 個以上選ぶ。
- $(1, 0)$ の場合、条件は満たせず、 $0$ 通り。
- $(1, 1)$ の場合、 $1$ しか選べない。
$(0, 0)$ については、 $N$ 個の内 $0$ が $X$ 個とすると、 $\sum_{i=1}^K {_XC_i}$ 通りとなりそう。 $(1, 1)$ も同様。
$(0, 1)$ については、全体の $\sum_{i=1}^K {_NC_i}$ 通りから、余事象となる $(0, 0)$ と $(1, 1)$ の分を引けば求められそう。
ここまでをビットごとに求めて掛け合わせれば解けるのでは？と思ったが、そもそもビットごとに独立ではない。
値 $A$ の内、 $i$ ビット目が $j$ になるものの集合を $U_{i,j}$ と表すと、「 $U_{1,0}, U_{1,1}, U_{2,0}, U_{2,1}, \ldots, U_{18,0}, U_{18,1}$ の全集合から $1$ 個以上ずつ選択されているような選択方法は何通りか」という問題になる気がするが、各値は複数（半分）の集合に含まれていてややこしく、解ける気がしない。