AtCoder Grand Contest 060

コンテスト前のレート：2057
レート通りのパフォーマンスが得られる順位：338位（1100点、122分15秒）

A - No Majority

問題

思考過程

1. 例えば"abcabcabc・・・"はよい文字列。前後文字以内に同じ文字が存在しなければよい。
2. 「文字目まで見て、つ前の文字が、つ前の文字がの場合の通り数」でできそう。
3. あとは、文字目をとするとして、からへの遷移を頑張って書く。

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());
        char[] s = br.readLine().toCharArray();
        br.close();

        int mod = 998244353;
        long[][][] dp = new long[n][26][26];
        char c0 = s[0];
        char c1 = s[1];
        // 最初の2文字
        for (int j = 0; j < 26; j++) {
            if (c0 != '?' && c0 - 'a' != j) {
                continue;
            }
            for (int j2 = 0; j2 < 26; j2++) {
                if (c1 != '?' && c1 - 'a' != j2) {
                    continue;
                }
                if (j == j2) {
                    continue;
                }
                dp[1][j][j2] = 1;
            }
        }

        // 2文字目～n-1文字目
        // i→i+1文字目へ配るDP
        for (int i = 1; i < n - 1; i++) {
            c0 = s[i - 1];
            c1 = s[i];
            for (int j = 0; j < 26; j++) {
                if (c0 != '?' && c0 - 'a' != j) {
                    continue;
                }
                for (int j2 = 0; j2 < 26; j2++) {
                    if (c1 != '?' && c1 - 'a' != j2) {
                        continue;
                    }
                    if (j == j2) {
                        continue;
                    }
                    char c2 = s[i + 1];
                    for (int k = 0; k < 26; k++) {
                        if (c2 != '?' && c2 - 'a' != k) {
                            continue;
                        }
                        if (k == j || k == j2) {
                            continue;
                        }
                        dp[i + 1][j2][k] += dp[i][j][j2];
                        dp[i + 1][j2][k] %= mod;
                    }
                }
            }
        }

        long ans = 0;
        for (int j = 0; j < 26; j++) {
            for (int j2 = 0; j2 < 26; j2++) {
                ans += dp[n - 1][j][j2];
            }
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで21分57秒＋0ペナ。495位。

B - Unique XOR Path

問題

思考過程

1. よいパスを全部とし、よいパスから外れたら必ず総XORが以外になるようにすることを考える。
2. とりあえずよいパス内の曲がり角の内側のマスには以外を置く必要がある。
   　
3. 「マスまでのパスであり得るXORの集合」を管理するDPで、よいパス以外に来た時にを含んでいたらそのマスの値を集合のMexにする感じ？　→さすがに全ケースTLE
4. Mexはべきとしてもよい？　→WA
5. よいパスに戻る直前のマスでだけが含まれないことを担保すればよいのでは？　→WA
6. よいパスから出るところででなくした方が少なく済む場合がある。行数または列数の少ない方とを比較するだけだったり？　→WA
   　
7. 曲がり角から内側方面に斜めに同じ値を配置していくと、曲がり角の個数分だけで済む。　→WA
8. 曲がり角の内側マスの位置関係次第（両方のマスを通れない場合）では、異なる曲がり角に同じ値を使うこともできる。
9. 最初の方で書いていたDPとほぼ同じ感じで「マスまでのパスで通れる曲がり角内側マスの集合」を管理するDPをする。　→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));
        int t = Integer.parseInt(br.readLine());
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            int n = Integer.parseInt(sa[0]);
            int m = Integer.parseInt(sa[1]);
            int k = Integer.parseInt(sa[2]);
            char[] s = br.readLine().toCharArray();

            if (solve(n, m, k, s)) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
        br.close();
    }

    static boolean solve(int n, int m, int k, char[] s) {
        // よいパス
        boolean[][] a = new boolean[n][m];
        int x = 0;
        int y = 0;
        a[x][y] = true;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == 'D') {
                x++;
            } else {
                y++;
            }
            a[x][y] = true;
        }

        // よいパスの曲がり角内側マス
        boolean[][] b = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!a[i][j]) {
                    if (i < n - 1 && j > 0 && a[i + 1][j] && a[i][j - 1]) {
                        b[i][j] = true;
                    }
                    if (i > 0 && j < m - 1 && a[i - 1][j] && a[i][j + 1]) {
                        b[i][j] = true;
                    }
                }
            }
        }

        int[][] dp = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int val = 0;
                if (i > 0) {
                    val |= dp[i - 1][j];
                }
                if (j > 0) {
                    val |= dp[i][j - 1];
                }
                if (b[i][j]) {
                    boolean ok = false;
                    for (int v = 0; v < k; v++) {
                        if ((val >> v & 1) == 0) {
                            int v2 = 1 << v;
                            val += v2;
                            ok = true;
                            break;
                        }
                    }
                    if (!ok) {
                        return false;
                    }
                }
                dp[i][j] = val;
            }
        }

        // デバッグ用
//      for (int i = 0; i < n; i++) {
//          StringBuilder sb = new StringBuilder();
//          for (int j = 0; j < m; j++) {
//              sb.append(dp[i][j]).append("\t");
//          }
//          System.out.println(sb.toString());
//      }
        return true;
    }
}

ここまで161分59秒＋5ペナ。400位。

2時間経過した辺りでEまでは問題を見ていたが、CもDもぱっと見苦手なタイプの数え上げで、Eは一発逆転を狙える構築ではあったが、さすがにBの方が可能性がありそうでおとなしくBに戻っていた。
その後はもう一度Eを見ていたが、1時間はじっくり色々試してみないと何も見えて来そうになく、時間が足りないので少し早めに諦め。

最終結果：ABの2完1100点、186分59秒、412位、パフォーマンス1907
レート変動：2057→2043（-14）

2完内で下から5番目で、残り時間20分で今更B通せても・・・と思ったが、A解けたのがそんなに早くはなく、1完で終わっていたら611位でパフォ1592だったので十分救われていた。