M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)(Rated範囲外)

ABC

コンテスト前のレート：2051
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：253位（2000点、80分24秒）

A - QQ solver

問題

思考過程
  1. 入力から1文字目と3文字目を取り出したい。
  2. スペースの代わりに"x"で区切られていると思えば、いつもの「A B」を受け取るのと同様になる。
  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));
        String[] sa = br.readLine().split("x"); // 2
        int a = Integer.parseInt(sa[0]);
        int b = Integer.parseInt(sa[1]);
        br.close();

        System.out.println(a * b);
    }
}

ここまで1分13秒＋0ペナ。1076位。


B - Caesar Cipher

問題
下記思考過程2.までで提出した後、Cで手が止まった時に結果を見たらWAになっていたので、Cを中断して戻ってくる。
4-1.の一致判定も、String化してequalsメソッドに頼ればいいのに自力で頑張ってしまっている。

思考過程
  1. Sの先頭が'a'となるように、Sの各文字から(S_1 - 'a')を引く。
  2. Tも同様に処理し、S=Tとなった場合のみ"Yes"。　→WA
  3. 'a'の前は'z'となることを考慮していなかった。
    　
  4. ここまでの方針を捨て、以下の処理を26回繰り返すことにする。
    1. S=Tならば"Yes"を出力して終了。
    2. Sの各文字を1つ後ろの文字に変更する。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        char[] t = sc.next().toCharArray();
        sc.close();

        for (int k = 0; k < 26; k++) {
            // 4-1
            boolean flg = true;
            for (int i = 0; i < s.length; i++) {
                if (s[i] != t[i]) {
                    flg = false;
                }
            }
            if (flg) {
                System.out.println("Yes");
                return;
            }
            // 4-2
            for (int i = 0; i < s.length; i++) {
                s[i] = next(s[i]);
            }
        }
        System.out.println("No");
    }

    static char next(char a) {
        a++;
        if (a > 'z') {
            a = 'a';
        }
        return a;
    }
}

ここまで12分10秒＋1ペナ。2020位。


後から思えば、1つ後ろの文字を得るのにきちんとnextメソッドを作るのであれば、最初からprevメソッドを作れば捨てた方針でもできただろうし、なんなら'a'未満なら+26するだけでもよかった。（WA提出に★の2行を追加でAC）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        char[] t = sc.next().toCharArray();
        sc.close();

        int a = s[0] - 'a';
        int b = t[0] - 'a';
        for (int i = 0; i < s.length; i++) {
            s[i] = (char) (s[i] - a);
            t[i] = (char) (t[i] - b);
            if (s[i] < 'a') s[i] = (char) (s[i] + 26); // ★
            if (t[i] < 'a') t[i] = (char) (t[i] + 26); // ★
            if (s[i] != t[i]) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

　

C - Graph Isomorphism

問題
実際は下記3.で10分くらい頭こんがらがってる。

思考過程
  1. とりあえず、N \le 8という制約を見て順列全探索することを考える。
  2. 高橋君のおもちゃのボールiと青木君のおもちゃのボールP_iを対応付けた時に同じ形になっている。という順列Pが存在すれば"Yes"。あとは同じ形かどうかの判定をどうするか。
    　
  3. 例えば例１でP=\{3, 2, 1, 4\}の場合、Aを\{1, 1, 1, 3\}から\{3, 3, 3, 1\}に、Bを\{2, 3, 4, 4\}から\{2, 1, 4, 4\}に書き換えた上で、全てのi (1 \leq i \leq M)について(A_i, B_i)と一致する(C_i, D_i)が存在するかどうかを調べればよい。
  4. なお、存在判定時には、(A_i, B_i) = (C_i, D_i)と(A_i, B_i) = (D_i, C_i)の両方を試す必要がある。
import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] a, b, c, d;
    static String ans = "No";

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[m];
        b = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt() - 1;
            b[i] = sc.nextInt() - 1;
        }
        c = new int[m];
        d = new int[m];
        for (int i = 0; i < m; i++) {
            c[i] = sc.nextInt() - 1;
            d[i] = sc.nextInt() - 1;
        }
        sc.close();

        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = i;
        }
        permutation(x, 0, 0, new int[n]);
        System.out.println(ans);
    }

    static void permutation(int[] org, int used, int idx, int[] wk) {
        if (idx == org.length) {
            // a, bを順列に従って書き換えた配列
            int[] aa = new int[m];
            int[] bb = new int[m];
            for (int i = 0; i < m; i++) {
                aa[i] = wk[a[i]];
                bb[i] = wk[b[i]];
            }

            // 全ての(aa[i], bb[i])が条件を満たすか
            boolean flg = true;
            for (int i = 0; i < m; i++) {
                // (aa[i], bb[i])に対応する(c[j], d[j])または(d[j], c[j])が存在するか
                boolean flg2 = false;
                for (int j = 0; j < m; j++) {
                    if (aa[i] == c[j] && bb[i] == d[j]
                            || aa[i] == d[j] && bb[i] == c[j]) {
                        flg2 = true;
                        break;
                    }
                }
                if (!flg2) {
                    flg = false;
                    break;
                }
            }
            if (flg) {
                ans = "Yes";
            }
            return;
        }

        for (int i = 0; i < org.length; i++) {
            if ((used >> i & 1) == 0) {
                wk[idx] = org[i];
                permutation(org, used | 1 << i, idx + 1, wk);
            }
        }
    }
}

ここまで25分40秒＋1ペナ。1275位。


D - Weak Takahashi

問題
1ペナ出したが、それ込みでもBやCより早く解けてる。

思考過程
  1. 「DP[i][j]:=マス(1, 1)からマス(i, j)まで移動した時の答え（たどり着けない場合は0）」とする。
  2. マス(i, j)が空きマスの場合、DP[i][j]は基本的にはDP[i-1][j]とDP[i][j-1]の大きい方に1を足したものになる。
  3. 遷移元マスが壁の場合は0としているので、Maxを取る上では気にする必要はなく、1行目、1列目の処理で配列外参照しないようにだけ注意する。　→WA
  4. 壁で完全に分断されている場合、壁を越えた先の空きマスがまた1となってしまっていた。
    　
  5. 1加算するのを、遷移元のいずれかが壁でない場合と、マス(1, 1)の場合のみとすることで回避する。
import java.util.Scanner;

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

        int[][] dp = new int[h][w];
        int ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i][j] == '.') {
                    if (i > 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                    }
                    if (j > 0) {
                        dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
                    }
                    // 5
                    if (dp[i][j] > 0 || i == 0 && j == 0) {
                        dp[i][j]++;
                    }
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
        System.out.println(ans);
    }
}

ここまで31分46秒＋2ペナ。918位。


E - Rook Path

問題

思考過程
  1. 例３を手作業で移動させてみると、現在位置や移動先が(x_2, y_2)と同じ行や同じ列であるかどうかをかなり意識させられる。
  2. 「DP[k][i][j]:=k回操作してマス(i, j)に移動する通り数」とすると数えることはできるが、オーダーにHやWが入ってしまってはTLE。
  3. そこで上記DPのi, jを、(x_2, y_2)と同じ行や列なら0、異なるなら1とする。これならばO(K)となる。
  4. あとは遷移を1つずつ解決していく。（ソース内コメント参照）
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        sc.close();

        int mod = 998244353;
        long[][][] dp = new long[k + 1][2][2];
        dp[0][x1 == x2 ? 0 : 1][y1 == y2 ? 0 : 1] = 1;
        for (int i = 0; i < k; i++) {
            // ※A≠A'≠x2、B≠B'≠y2

            // (x2, y2) ← (x2, B)、(A, y2)
            dp[i + 1][0][0] = (dp[i][0][1] + dp[i][1][0]) % mod;

            // (x2, B)への移動
            dp[i + 1][0][1] += dp[i][0][0] * (w - 1) % mod; // (x2, y2)から
            dp[i + 1][0][1] += dp[i][0][1] * (w - 2) % mod; // (x2, B')から
            dp[i + 1][0][1] += dp[i][1][1]; // (A, B)から
            dp[i + 1][0][1] %= mod;

            // (A, y2)への移動
            dp[i + 1][1][0] += dp[i][0][0] * (h - 1) % mod; // (x2, y2)から
            dp[i + 1][1][0] += dp[i][1][0] * (h - 2) % mod; // (A', y2)から
            dp[i + 1][1][0] += dp[i][1][1]; // (A, B)から
            dp[i + 1][1][0] %= mod;

            // (A, B)への移動
            dp[i + 1][1][1] += dp[i][0][1] * (h - 1) % mod; // (x2, B)から
            dp[i + 1][1][1] += dp[i][1][0] * (w - 1) % mod; // (A, y2)から
            dp[i + 1][1][1] += dp[i][1][1] * (w - 2 + h - 2) % mod; // (A, B')、(A', B)から
            dp[i + 1][1][1] %= mod;
        }
        System.out.println(dp[k][0][0]);
    }
}

ここまで50分38秒＋2ペナ。406位。


F - Simple Operations on Sequence

問題

思考過程
  1. 制約がO(2^N)と言っているので、ビット全探索や、集合をパラメータとしたDPができないかを考える。
  2. 場所を変えるインデックスの集合を全探索を考えてみると、移動させるかどうかを特定しただけでは、どこに移動させるのが最適かまではわからない。
    　
  3. 「DP[S]:=Aのインデックス集合Sと、Bの先頭からbitcount(S)=c番目までを対応させた時の最小値」とすると、SからSに含まれていない1箇所を足した集合への遷移コストが計算できる。
  4. 具体的には、追加する1箇所に該当するA_jとB_{c+1}の差\times Xと、jからc+1までの移動距離\times Yの和。
  5. と思ったが、A_jの位置はSまでの操作で既に動いている場合がある。
  6. j \lt c+1の場合を見てみると、Sまでの操作でAの後ろの方を前に移動してきていることになり、Sに入っていないAの要素は、順番を保ったまま後ろにずれている。
  7. Sからの最初の追加候補がちょうど位置c+1まで後ろにずれてきている状態になっているので、結局求めたい移動距離は、Sからの追加候補何番目であるかとイコールになる。
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();
        long x = sc.nextLong();
        long y = sc.nextLong();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        sc.close();

        long inf = 1000000000000000000L;
        int end = 1 << n;
        long[] dp = new long[end];
        Arrays.fill(dp, inf);;
        dp[0] = 0;
        for (int i = 0; i < end; i++) { // 文章中のS=i
            int c = Integer.bitCount(i);
            int cnt = 0; // 追加候補数をカウント
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 0) { // jが集合に入っていない場合
                    int next = i + (1 << j);
                    long val = x * Math.abs(a[j] - b[c]) + y * cnt;
                    dp[next] = Math.min(dp[next], dp[i] + val);
                    cnt++;
                }
            }
        }
        System.out.println(dp[end - 1]);
    }
}

ここまで73分04秒＋2ペナ。230位。


Gは無駄な遷移を省いてダイクストラをしたいとは思ったが、無駄の省き方が全然できてなさそう。
Hは問題を開いてもいない。


最終結果：ABCDEFの6完2000点、83分04秒、266位、パフォーマンス2030相当
レート変動：2051（Unrated）


今回もまた序盤でコケてE、Fで挽回した形。比較的苦手分野だと思っているDPがちゃんと拾えたのは良かった。
BとDの1ペナがあまりにお粗末すぎ。
Cみたいなのでこんがらがらないようになりたい。