AtCoder Regular Contest 137 - ks2mのブログ

A - Coprime Pair
- 思考過程
B - Count 1's
- 思考過程
C - Distinct Numbers
- 思考過程

コンテスト前のレート：2020
レート通りのパフォーマンスが得られる順位：366位（1300点、81分20秒）

A - Coprime Pair

問題
for文がすんなり書けなかった。

思考過程

素数がそれなりの密度で存在することを考えると、 $(y-x)$ が大きい順に全探索していってもTLEする前には答えが見つかりそう。
具体的には例２であれば、
$(14, 21),$
$(14, 20), (15, 21),$
$(14, 19), (15, 20), (16, 21),$
$\cdots$
のように試していく。

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(" ");
        long l = Long.parseLong(sa[0]);
        long r = Long.parseLong(sa[1]);
        br.close();

        long d = r - l;
        for (int i = 0; ; i++) {
            for (long y = r - i; y <= r; y++) {
                long x = y - d + i;
                if (gcd(x, y) == 1) {
                    System.out.println(y - x);
                    return;
                }
            }
        }
    }

    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

ここまで8分19秒＋0ペナ。486位。

B - Count 1's

問題

思考過程

空の部分列を選んだ場合、 $A$ の合計 $S$ を取れる。
$S$ から、 $A$ の連続した部分の「 $1$ の個数 $-0$ の個数の最大値」を引いた値が最小スコアで、「 $0$ の個数 $-1$ の個数の最大値」を足した値が最大スコアとなる。
最大または最小スコアを得られる操作対象から、端の要素だけ除外することを考えれば、間のスコアは全て取れそう。
　
あとは上記2.のカギ括弧内の値だが、これは $1$ を $+1$ 、 $0$ を $-1$ として累積和を取っていった時の、「これまでの最大/最小値から最大どれだけ下がって/上がっているか」で求められる。

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));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int min = 0; // 過去の最小値
        int max = 0; // 過去の最大値
        int mind = 0; // 最大の下がり幅
        int maxd = 0; // 最大の上がり幅
        int val = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                a[i] = -1;
            }
            val += a[i];
            min = Math.min(min, val);
            max = Math.max(max, val);
            mind = Math.min(mind, val - max);
            maxd = Math.max(maxd, val - min);
        }
        int ans = maxd - mind + 1;
        System.out.println(ans);
    }
}

ここまで16分43秒＋0ペナ。243位。

C - Distinct Numbers

問題
CとDの正解者数が同じくらいだったので、Cに15分使って解けず→Dに30分使って解けず→Cに戻ってくるという動きをしていた。
最終的には実験エスパーをした。

思考過程

$N=3$ くらいで適当に色々試してみるが、先手の勝率が高そうなことくらいしか見えてこない。
$N=2$ で $A$ の値が小さい方から網羅的に実験してみると、 $(A_1, A_2)=(0, 1), (2, 3), (4, 5), \cdots$ のような場合以外は全て先手勝ち。
これだけでは $N$ が多い時の法則まではわからないので、 $N=3$ もなんとか網羅的に実験する。
すると、 $A_3 \leq 6$ の範囲では、
$(0, 1, 2),$
$(0, 3, 4), (1, 3, 4), (2, 3, 4)$
$(0, 5, 6), (1, 5, 6), (2, 5, 6), (3, 5, 6), (4, 5, 6)$
以外は全て先手勝ち。
ここまでで、最後の要素と $N$ の偶奇が異なることと、最後の $2$ 要素の差が $1$ であることが後手勝ちの条件なのだろうと当たりを付ける。

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));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        if (a[n - 1] % 2 != n % 2 && a[n - 2] + 1 == a[n - 1]) {
            System.out.println("Bob");
        } else {
            System.out.println("Alice");
        }
    }
}