AtCoder Regular Contest 131

コンテスト前のレート：2017
レート通りのパフォーマンスが得られる順位：344位（1200点、38分16秒）

A - Two Lucky Numbers

問題
デバッグを消し忘れて余計に1ペナ。

思考過程

1. とを文字列にして連結した後、すればよさそう。　→1ケースだけWA
2. 色々試して、が奇数の場合した時に後ろのの部分がにならないことがわかる。
3. と"0"とを連結することにより、より前を偶数にしての部分が影響を受けないようにする。
4. 桁増えて心配だったが、最大ケースでに収まっていることを確認して提出。

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();
        String sb = br.readLine();
        br.close();

        long a = Long.parseLong(sa);
        long a2 = a * 2;
        String ans2 = sb + "0" + String.valueOf(a2);
        System.out.println(Long.parseLong(ans2) / 2);
    }
}

ここまで12分08秒＋2ペナ。1238位。

B - Grid Repainting 4

問題

思考過程

1. 左上から順番に見ていって、まだ塗られていないマスだったら、周囲マスを調べて使われていない色で塗る。　とするだけで特に落とし穴があるとも考えられないので、あとは配列外参照に気を付けて実装する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i][j] == '.') {
                    // Setに1～5を入れる
                    Set<Character> set = new HashSet<>();
                    for (char k = '1'; k <= '5'; k++) {
                        set.add(k);
                    }
                    // Setから周囲4マスに使われている色を取り除く
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (0 <= nx && nx < h && 0 <= ny && ny < w) {
                            if (s[nx][ny] != '.') {
                                set.remove(s[nx][ny]);
                            }
                        }
                    }
                    // Setに残った任意の色を使う
                    s[i][j] = set.iterator().next();
                }
            }
            System.out.println(s[i]);
        }
    }
}

ここまで17分05秒＋2ペナ。693位。

C - Zero XOR

問題
下記1.の掃き出し法から離れるまでに20分以上はかかった。
20分ほどしてDとEも問題を読んだが、すぐにはわかりそうになく、正解者数の多さを信じてやっぱりCからやることにした。

思考過程

1. 掃き出し法を使って、の偶奇で決まる？　いや全然違いそう。というか掃き出し法の結果を見るとそもそも元の問題が崩れている。
   　
2. 途中でにすることができない場合、が奇数なら先手勝ち、偶数なら後手勝ちとなるが、途中でになる可能性の有無が全然わからない。
3. 最大ケースだと計算量オーバーだが、一旦サンプルで通りを全探索してみて、個でXORがになる組合せが存在するならば、上記2.と勝敗が入れ替わる可能性はなくはない。
   　
4. とりあえず全部のXORを取ってみると、例１ではとなり、確かにとなるが、や以外を選んだ時のことはよくわからない。
5. 例３では全部のXORはとなり、これは手で終わらせられるので、手で終わらない場合の参考にはならないサンプルであることが判明する。
   　
6. なんかもうよくわからないが、上記3.のケースがあり得るにしても、両者が最適に行動したらその個が残るようなケースはまず間違いなく回避できる気がする。
7. そうすると、基本的には上記2.の通りで、途中でになるケースは、初手でにできるケース以外はないものとしてよいのではと思われる。

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 xor = 0;
        for (int i = 0; i < n; i++) {
            xor ^= a[i];
        }
        // 初手で0にできるものが存在する場合
        for (int i = 0; i < n; i++) {
            if (a[i] == xor) {
                System.out.println("Win");
                return;
            }
        }
        // 上記以外はnの偶奇
        if (n % 2 == 1) {
            System.out.println("Win");
        } else {
            System.out.println("Lose");
        }
    }
}

ここまで68分11秒＋2ペナ。590位。

E - Christmas Wreath

問題
DとEを両方見て、Eの方が希望がありそうだと判断。正解だった。
閃くまで割と早かったのに、実装に手間取ってしまった。

思考過程

1. がで割り切れない場合は条件1が満たせないので"No"。つまり、の場合は、が共にの倍数でないので"No"。
   　
2. とりあえず以下のような二次元表を作り、右上三角形部分を3種類同じ個数ずつ使って埋めていくことを考える。
3. 条件2は、右上を直角部分とした直角三角形の位置関係にある箇所（例えば表内の"A"）が、全て異なる色になっていては駄目ということになる。

   	1	2	3	4
   1	－		A	A
   2	－	－
   3	－	－	－	A
   4	－	－	－	－

4. は明らかに条件2を満たさない。は例１より"No"。は上記1.より"No"なので、の場合を考える。
5. を白、を赤、を青として、行目からのように埋めていくか、行目を全部にしてみるかといったことを考え、後者のように同じ行を全て同じ色にすれば、直角三角形の内点が必ず同じ色になって必ず条件2を満たすことに気付く。

   	1	2	3	4	5	6
   1	－	0	0	0	0	0
   2	－	－	1	1	1	1
   3	－	－	－	2	2	2
   4	－	－	－	－	2	2
   5	－	－	－	－	－	1
   6	－	－	－	－	－	－

6. これにより、～を合計が等しくなるようにグループに分ける問題になった。
   　
7. から順に、その時点で最も合計が少ないグループに割り当てていく貪欲をしてみると、の場合、と分けられた時点で残りがだけになって詰む。
8. の場合、各グループの和はになればよいので、と分けた次のを処理する際、のように目標値になるグループが存在すれば、優先的にそこに入れることにする。　これでおそらく詰まなくなるはず？

公式解説を確認し、がいずれも問題ないので、この方法で構成不可能なケースはなさそう。

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());
        br.close();

        if (n < 6 || n % 3 == 2) {
            System.out.println("No");
            return;
        }

        int m = n * (n - 1) / 6;  // 各グループの目標合計値
        int[] a = new int[n - 1]; // 割り当てるグループ
        int[] c = new int[3];     // 各グループの割り当て済み分の合計
        for (int i = n - 1; i > 0; i--) {
            int min = c[0];
            int idx = 0;
            // 目標値ぴったりになる場合は優先
            boolean flg = false;
            for (int j = 0; j < 3; j++) {
                if (c[j] + i == m) {
                    idx = j;
                    flg = true;
                    break;
                }
            }
            // 優先しない場合は現在の合計が最小のグループへ
            if (!flg) {
                for (int j = 0; j < 3; j++) {
                    if (c[j] < min) {
                        min = c[j];
                        idx = j;
                    }
                }
            }
            a[i - 1] = idx;
            c[idx] += i;
        }

        System.out.println("Yes");
        for (int i = n - 2; i >= 0; i--) {
            char ch = 'W';
            if (a[i] == 1) ch = 'R';
            if (a[i] == 2) ch = 'B';
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j <= i; j++) {
                sb.append(ch);
            }
            System.out.println(sb.toString());
        }
    }
}

ここまで96分02秒＋2ペナ。164位。

残り時間で一応Dの続きをやるが、解けず。

まずは中央の最高得点エリアの左端を中心に距離ごとに刺す。
以降全体をずつ右に動かしていきたいが、だと駄目なので、距離いくつ動かしたら点数いくつ変わるかを管理して差分計算をしようとし、実装間に合わず。
そもそもこれでちゃんと計算量落ちているかもよくわからず実装始めていた。

最終結果：ABCEの4完1800点、106分02秒、180位、パフォーマンス2313
レート変動：2017→2051（+34）

昨日今日とA問題の構築に苦しめられているが、最後に爆死の危機から救ってくれたのも構築だった。
構築は閃ければ楽しい。

それにしても、C問題解かれ過ぎでは？
ABで完全に出遅れた挙句、Cを解いても傷が半減するだけにしかならないのにそれすらもなかなか解けなくてだいぶ辛い状況だった。