AtCoder Regular Contest 115

コンテスト前のレート：2035
レート通りのパフォーマンスが得られる順位：302位（1200点、26分14秒）

A - Two Choices

問題
半分以上エスパーだったかも。

思考過程

1. 制約が大きいので、は駄目。
2. 例１を見ると、ある人の間では異なる箇所が奇数の場合に条件を満たしそう。
3. とりあえず例２で、'1'の数を数えてみて何かわからないか考える。
4. 例２では、'1'の数が奇数のものがつ、偶数のものがつある。
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 m = Integer.parseInt(sa[1]);
        char[][] s = new char[n][m];
        for (int i = 0; i < n; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        int[] a = new int[2];
        for (int i = 0; i < n; i++) {
            int c = 0;
            for (int j = 0; j < m; j++) {
                if (s[i][j] == '1') {
                    c++;
                }
            }
            a[c % 2]++;
        }
        System.out.println((long) a[0] * a[1]);
    }
}

ここまで4分10秒＋0ペナ。86位。

B - Plus Matrix

問題

思考過程

1. 行目と行目に注目した時、全ての列についてとの差が一致していなければ"No"。
2. 行と列を入れ替えて同様のチェックを行う。
   　
3. とを一旦として、これまでの差分チェックで求めた差で埋めていく。これで全体的にだけ小さくした場合が構築できた。
   　
4. あとはの値分をとに割り振ればよいが、との全要素は以上である必要があることから、それぞれの最小値が負である場合ににできるだけの値は割り振る必要がある。
5. との最小値のマイナス分が、のプラス分で補填し切れない場合は"No"。
6. そうでなければ、の最小値がになるようにに振り分け、余りは適当にに振り分ける。

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

        // 1
        int[] a = new int[n];
        for (int i = 1; i < n; i++) {
            a[i] = c[i][0] - c[i - 1][0];
            for (int j = 1; j < n; j++) {
                if (c[i][j] - c[i - 1][j] != a[i]) {
                    System.out.println("No");
                    return;
                }
            }
        }

        // 2
        int[] b = new int[n];
        for (int j = 1; j < n; j++) {
            b[j] = c[0][j] - c[0][j - 1];
            for (int i = 1; i < n; i++) {
                if (c[i][j] - c[i][j - 1] != b[j]) {
                    System.out.println("No");
                    return;
                }
            }
        }

        int mina = 0;
        int minb = 0;
        for (int i = 1; i < n; i++) {
            a[i] += a[i - 1]; // 3
            b[i] += b[i - 1]; // 3
            mina = Math.min(mina, a[i]);
            minb = Math.min(minb, b[i]);
        }

        // 5
        long sum = c[0][0] + mina + minb;
        if (sum < 0) {
            System.out.println("No");
            return;
        }

        // 6
        mina -= sum;
        for (int i = 0; i < n; i++) {
            a[i] -= mina;
            b[i] -= minb;
        }

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

ここまで19分27秒＋0ペナ。244位。

C - ℕ Coloring

問題

思考過程

1. 愚直？にやろうとすると、が小さい方から決めていくとして、の値が決まっているときに、がの倍数であるの値がと同じだったらすることで構築できる気がする。
2. 計算量は、調和級数というやつでのはず。
3. の初期値は、全部で初期化するくらいなら、ループ回分節約して、他はにしておくことにする。

import java.util.Arrays;
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();
        sc.close();

        int[] a = new int[n + 1];
        Arrays.fill(a, 2);
        a[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = i * 2; j <= n; j += i) {
                if (a[j] == a[i]) {
                    a[j]++;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(a[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで29分29秒＋0ペナ。223位。

D問題は15分ほど考えてもほぼ何もわからず、あとはほとんどE問題に時間を費やす。

E問題は、「番目まで見て最後がの場合の通り数」というDPをしようとし、例１や他に何パターンか考えてみて、はがある値より小さい時か大きい時かで通りの値しか取らないのではないかと思ったが、例２が合わず。
一応提出してみるも、だけAC。
後でTwitterを見ていて、通りの値を取り得ることがわかった。

最終結果：ABCの3完1200点、29分29秒、335位、パフォーマンス1985
レート変動：2035→2030（-5）

DやEは文字の解説を見てもすぐにはわかりそうになく、できなくても仕方なかったと思う。
今回は解けるべき問題を一応相応の早さで通せたという結果。