AtCoder Beginner Contest 244(Rated範囲外)

A - Last Letter
- 思考過程
B - Go Straight and Turn Right
- 思考過程
C - Yamanote Line Game
- 思考過程
D - Swap Hats
- 思考過程
E - King Bombee
- 思考過程
F - Shortest Good Path
- 思考過程

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

A - Last Letter

思考過程

$S$ の（ $0$ 始まりで） $N-1$ 文字目を出力する。

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();
        String s = sc.next();
        sc.close();

        System.out.println(s.charAt(n - 1));
    }
}

ここまで0分28秒＋0ペナ。121位。

B - Go Straight and Turn Right

問題

思考過程

現在地と向いている方向を管理しながら順番に処理していく。
方向については、進んだ時の $(x, y)$ の増分が $(+1, 0), (0, -1), (-1, 0), (0, +1), \cdots$ を繰り返していることを表せるようにする。

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();
        char[] t = sc.next().toCharArray();
        sc.close();

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, -1, 0, 1};
        int x = 0;
        int y = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (t[i] == 'R') {
                k++;
                k %= 4;
            } else {
                x += dx[k];
                y += dy[k];
            }
        }
        System.out.println(x + " " + y);
    }
}

ここまで2分35秒＋0ペナ。53位。

C - Yamanote Line Game

問題

思考過程

基本的には $1$ から順に出力していく。
ただし、既に入力があった値と重複する限りはスキップし続けてその次の値を出力したい。
boolean型配列を $1$ つ用意しておけば、既に入力があったかどうか判定ができる。

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

        boolean[] b = new boolean[n * 2 + 2];
        int x = 1;
        for (int i = 0; i < n; i++) {
            System.out.println(x);
            b[x] = true;
            int a = sc.nextInt();
            b[a] = true;
            while (b[x]) {
                x++;
            }
        }
        System.out.println(x);
        sc.close();
    }
}

ここまで5分56秒＋0ペナ。76位。

D - Swap Hats

問題
過去最も簡単なレベルのD問題だったのにお粗末すぎる3ペナ。

思考過程

初期状態からどこかを交換してまた初期状態に戻すには偶数回の操作が必要になる感じ。
$10^{18}$ 回というのは要するに、十分大きな偶数回の操作をするということ。
転倒数の偶奇といったことも思い浮かんだが、そんな大げさなことをしなくても状態が $6$ 通りしかないので、実際に書き出してみて $2$ グループの間を行ったり来たりする遷移をすることを一応確認する。
　
同一グループに入っているものは、元の並びをrotateしたものになっていたので、 $S$ をrotateした $3$ 通りのいずれかと $T$ が一致するかどうかを調べる。　→WA
　
"No"の出力を忘れていたので追加する。　→WA
もしかして何かを見落としていて、実は必ず"Yes"だったりする？　→WA
添え字を間違えている箇所があったので直す。　→AC

後から思えば、 $S$ を $2$ 回繰り返した文字列を作って、その中の連続する $3$ 文字の部分文字列の中に $T$ と一致するものがあるかという判定方法の方が楽そうだった。

import java.util.Scanner;

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

        for (int i = 0; i < 3; i++) {
            boolean flg = true;
            for (int j = 0; j < 3; j++) {
                if (s[j] != t[j]) { // 7.ここがiになっていた
                    flg = false;
                    break;
                }
            }
            if (flg) {
                System.out.println("Yes");
                return;
            }
            rotateR(s, 0, 2);
        }
        System.out.println("No"); // 5.ここが抜けていた
    }

    static void rotateR(char[] val, int beg, int end) {
        char tmp = val[end];
        for (int i = end; i > beg; i--) {
            val[i] = val[i - 1];
        }
        val[beg] = tmp;
    }

}

ここまで15分25秒＋3ペナ。382位。

E - King Bombee

問題

思考過程

$0$ 回の場合、 $2$ 回の場合、 $\cdots$ と順にやっていったらどうかと思ったりするが、全然できる気がしない。
　
こういうのはだいたい「 $DP[i][j][k]:=i$ 回移動して頂点 $X$ を $j$ 回通って頂点 $k$ にいる通り数」とかでは？とDPを考え始めるが、これでは空間計算量だけで $O(K^2N)$ になる。
$j$ は偶奇だけわかればよいのでサイズ $2$ で十分。
遷移は辺の数だけ処理すればよく、移動先が $X$ の場合だけ $j$ の $0, 1$ を入れ替える形。

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]);
        int k = Integer.parseInt(sa[2]);
        int s = Integer.parseInt(sa[3]) - 1;
        int t = Integer.parseInt(sa[4]) - 1;
        int x = Integer.parseInt(sa[5]) - 1;
        int[] u = new int[m];
        int[] v = new int[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            u[i] = Integer.parseInt(sa[0]) - 1;
            v[i] = Integer.parseInt(sa[1]) - 1;
        }
        br.close();

        int mod = 998244353;
        // 思考過程に記載のk, jだけ持つ
        long[][] dp = new long[n][2];
        dp[s][0] = 1;
        for (int i = 0; i < k; i++) {
            long[][] wk = new long[n][2];
            for (int j = 0; j < m; j++) {
                if (v[j] == x) {
                    wk[v[j]][1] += dp[u[j]][0];
                    wk[v[j]][0] += dp[u[j]][1];
                } else {
                    wk[v[j]][0] += dp[u[j]][0];
                    wk[v[j]][1] += dp[u[j]][1];
                }
                if (u[j] == x) {
                    wk[u[j]][1] += dp[v[j]][0];
                    wk[u[j]][0] += dp[v[j]][1];
                } else {
                    wk[u[j]][0] += dp[v[j]][0];
                    wk[u[j]][1] += dp[v[j]][1];
                }
            }
            for (int j = 0; j < n; j++) {
                wk[j][0] %= mod;
                wk[j][1] %= mod;
            }
            dp = wk;
        }
        System.out.println(dp[t][0]);
    }
}

ここまで28分48秒＋3ペナ。237位。

F - Shortest Good Path

問題
すぐにはわからず、Gと行ったり来たりしていた。

思考過程

そもそも最短の良いパスというのをどうやって求めるのかよくわからない。Gを見てみたら問題設定がほとんど同じで、Gが解けたらこれも解けるのでは？とか一瞬思ったりもするが、制約が全然違うので考え方を変えた方がよさそう。
　
巡回セールスマン問題のようなDPを考えてみたらどうか？
訪問済みの頂点集合（ただし偶数回訪問したところは未訪問とみなす）を $S$ とすればそのまんま問題文の $S$ と同じことになり、 $S$ と現在地で状態が表せる。
あとはBFSをすれば各状態へ最短でたどり着く方法 $=$ 最短の良いパスがわかることになる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

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]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int u = Integer.parseInt(sa[0]) - 1;
            int v = Integer.parseInt(sa[1]) - 1;
            list.get(u).add(v);
            list.get(v).add(u);
        }
        br.close();

        int n2 = 1 << n;
        int[][] dp = new int[n2][n]; // 訪問状態、現在地
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < n2; i++) {
            Arrays.fill(dp[i], -1);
        }
        // どこも訪れておらず、現在地n通りが初期状態
        for (int j = 0; j < n; j++) {
            dp[0][j] = 0;
            que.add(j);
        }

        while (!que.isEmpty()) {
            int cur = que.poll();
            int cx = cur / 100;
            int cy = cur % 100;
            for (int ny : list.get(cy)) {
                int nx = cx ^ (1 << ny);
                if (dp[nx][ny] == -1) {
                    que.add(nx * 100 + ny);
                    dp[nx][ny] = dp[cx][cy] + 1;
                }
            }
        }

        long ans = 0;
        for (int i = 0; i < n2; i++) {
            // dp[i][0]～dp[i][n-1]の最小値
            int min = 1000000007;
            for (int j = 0; j < n; j++) {
                min = Math.min(min, dp[i][j]);
            }
            ans += min;
        }
        System.out.println(ans);
    }
}

ここまで62分50秒＋3ペナ。255位。

残り時間はGのみ考えていて、Hは開いてもいない。
01が交互になったパスグラフとかでできないのでは？と思ったが、合ってなければ $1$ つ戻るということをしながら進んでいけばできそう。
それならば、適当に木にしてオイラーツアーに対してその処理をやれば？と思ってやってみたが、7割くらいTLE。
無限に行ったり来たりを繰り返してしまったのだろうか・・・。考えがおかしいのか実装ミスがあるのかもよくわからず。

最終結果：ABCDEFの6完2000点、77分50秒、335位、パフォーマンス1787相当
レート変動：2017（Unrated）

このくらいの順位ならいつもはパフォ1900台くらいありそうな気がするんだけど、何でこんなに低いんだろう。

今回はDが適当過ぎたのはさておき、EとFは素直にDP考え始めるまでが遅いな・・・。