AtCoder Regular Contest 105 - ks2mのブログ

A - Fourtune Cookies
- 思考過程
B - MAX-=min
- 思考過程
C - Camels and Bridge
D - Let's Play Nim
- 思考過程

コンテスト前のレート：1796
レート通りのパフォーマンスが得られる順位：473位（1000点、45分50秒）

A - Fourtune Cookies

問題
例１の影響で2個食べると誤読。
解き直し＋ペナルティで7分近いロスとなる。

思考過程

二重ループを回し、 $2$ 要素の和の $2$ 倍が全部の合計と一致すれば"Yes"。　→ $2$ ケースWA
一重ループを追加し、単独要素の $2$ 倍が全部の合計と一致すれば"Yes"を付け足す。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[4];
        for (int i = 0; i < 4; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int sum = 0;
        for (int i = 0; i < 4; i++) {
            sum += a[i];
        }
        for (int i = 0; i < 4; i++) {
            if (a[i] * 2 == sum) {
                System.out.println("Yes");
                return;
            }
        }
        for (int i = 0; i < 4; i++) {
            for (int j = i + 1; j < 4; j++) {
                int v = a[i] + a[j];
                if (v * 2 == sum) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }
}

ここまで4分01秒＋1ペナ。978位。

B - MAX-=min

問題
人々が解法にたどり着くの早すぎ。
愚直シミュレーションの無駄を省くことばかり考えていてだいぶ遠回りした。

思考過程

単純にシミュレーションしたのでは、 $X=10^9, x=1$ の場合に全然間に合わない。
$a_i \neq x$ の要素を全て $a_i \% x$ に置き換えていくことを考える。
$x$ 未満になる要素が $1$ つ現れた時点で、 $x$ が変わってしまうのでおかしい。
　
$min(a_i, a_i \% x + x)$ に置き換えていって、 $a_i \% x$ の最大値を次の $x$ にするのを繰り返せばよさそうに思えるけどめんどくさい。
適当な小さい数でここまでの流れを手計算で試していたら答えは $1$ になったが、例１は $2$ 。
手元や例１の数値の並びを睨んだ感じや、問題文の「 $X-x$ 」という計算から、最大公約数という単語が頭をよぎる。
若干自信ないが、ただの全要素の最大公約数を例２で試してみたら合っていたので、提出する。

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();

        long ans = a[0];
        for (int i = 1; i < n; i++) {
            ans = gcd(ans, a[i]);
        }
        System.out.println(ans);
    }

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

ここまで14分16秒＋1ペナ。1126位。

C - Camels and Bridge

問題
解けず。前日の反省を全く生かしておらず、一旦中断してD問題を見始めるのも遅い。
$O(N!)$ で順列全列挙はやっていいんだろうけど、毎回全部の橋を判定する $O(N!M)$ だと駄目そうで、先頭を一番重いので固定して $(N-1)!M$ ならいけそうか？とか、順列ごとに、ラクダをまとめて $1$ ～ $N$ 頭とみなせる耐荷重はいくら以上かを前計算して $O(N!Nlog v + M)$ のようにできないかとか、色々考えたが、結局順列ごとの最適解を求める方法がきちんと正当な方法になっておらず、最後まで例４が合わなかった。

D - Let's Play Nim

問題
残り時間2分ほどで思いついて慌てて実装し、動作確認もできずに残り時間2秒で提出したコードが、ほんの些細な実装ミス1つで駄目だった。

思考過程

袋から皿に出し終わった時点をゲーム開始とした場合、各皿のコイン枚数の総xorが $0$ ならば後手勝ち、以外は先手勝ちとなる。
　
まず、袋が $1$ つの場合、 $1 \leq a_i$ なので絶対に前半パート（袋から皿に出す部分）で総xorが $0$ にはならないので、後半パートの先手が必勝。つまり後手必勝。
袋が $2$ つの場合、後手は前半パートで $0$ にしたいが、それは $2$ つとも同じ枚数の場合のみ可能。
とりあえずここまでは間違いなさそうだが、袋が $3$ つ以上の場合はぱっとはよくわからない。
　
$a_i$ が全て $1$ の場合で考えてみると、 $N$ が偶数の場合は $0$ にできて、後半パートが先手からなので後手勝ち、 $N$ が奇数の場合は $0$ にならず、後半パートが後手からなので後手勝ち。　 $0$ になることの方がとても少なそうなので、とりあえず $3 \leq N$ の場合は全部後手勝ちで提出してみる。　→WA
　
$N$ が奇数の場合は、前半パートの最後から $2$ 手目次第で後手がだいたい $0$ にならないようにできそうな気がする。　とりあえず $N$ が奇数の場合は後手勝ち、偶数の場合は先手勝ちで提出してみる　→WA
　
上記5.で、 $a_i$ が全部同じなら真似することで後手が $0$ にできそうなんだった。　 $N$ が偶数の場合について、 $1$ つでも異なる値があれば先手勝ち、それ以外は後手勝ちにしてみる。　→WA
　
真似プレイが成立するためには、全要素が同じ値ではなく、同じ値が偶数個ずつあればいいのではとなる。　→実装ミスでWA
解説を読んで合ってるじゃんとなり、見直したら実装ミスに気付いてAC。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        label:
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            String[] sa = br.readLine().split(" ");
            int[] a = new int[n];
            for (int j = 0; j < n; j++) {
                a[j] = Integer.parseInt(sa[j]);
            }
            // 思考過程2（思考過程の産物であり、ここはなくても通る）
            if (n == 1) {
                pw.println("Second");
                continue;
            }
            // 思考過程3（思考過程の産物であり、ここはなくても通る）
            if (n == 2) {
                if (a[0] == a[1]) {
                    pw.println("Second");
                } else {
                    pw.println("First");
                }
                continue;
            }
            if (n % 2 == 1) { // 思考過程6
                pw.println("Second");
            } else {
                Map<Integer, Integer> map = new HashMap<>();
                for (int j = 0; j < a.length; j++) {
                    map.put(a[j], map.getOrDefault(a[j], 0) + 1);
                }
                for (Integer val : map.values()) { // ここがmap.keySet()になっていた
                    if (val % 2 != 0) { // もしくはここでmap.get(val)にし忘れた
                        pw.println("First");
                        continue label;
                    }
                }
                pw.println("Second");
            }
        }
        pw.flush();
        br.close();
    }
}

最終結果：ABの2完、19分16秒、1424位、パフォーマンス1069
レート変動：1796→1741（-55）

ここ1年間で最低の結果だが、最後にDが通っていれば1800は出ていたので惜しかった。
あと10秒あればあんな実装ミスはしなかったのではとも思うが、思考過程でわかる通り、D問題を自信持って解けているわけでもないので、あんまり言っても仕方ないところ。

とはいえ、こんな時にA問題も誤読していて、B問題も手間取っていて、最初で出遅れた時に自分のレート前後のdifficultyの問題が1問も解けず逆転できないのはなかなか辛い・・。
（先週のARC104はB問題まで似たような推移だったが、黄diffを通すという大逆転があった。）