AtCoder Regular Contest 108

ARC

コンテスト前のレート：1701
レート通りのパフォーマンスが得られる順位：653位（1200点、60分59秒）

A - Sum and Product

問題

思考過程
  1. 約数を全列挙すれば掛け算の方を全探索できるのでとりあえずそのライブラリを貼る。
  2. ただし、約数の内上半分はいらないので削る。別に残っていても問題はないが。
  3. 約数NとP \div Nが条件を満たしていれば"Yes"。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        long s = Long.parseLong(sa[0]);
        long p = Long.parseLong(sa[1]);
        br.close();

        List<Long> list = divList(p);
        for (long n : list) {
            long m = p / n;
            if (n + m == s) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }

    // 以下ライブラリ

    static List<Long> divList(long n) {
        List<Long> list = new ArrayList<>();
        long end = (long) Math.sqrt(n);
        for (int i = 1; i <= end; i++) {
            if (n % i == 0) {
                list.add((long) i);
            }
        }
//        int i = end * end == n ? list.size() - 2 : list.size() - 1;
//        for ( ; i >= 0; i--) {
//            list.add(n / list.get(i));
//        }
        return list;
    }
}

ここまで2分11秒＋0ペナ。370位。


B - Abbreviate Fox

問題
30分かかってもWAが解決できず、先にCを解く。
戻ってきたら今度は割とすぐにスタックが思いつき、10分ほどでAC。

思考過程
  1. replaceAll("fox", "");を繰り返すような愚直が間に合いそうな制約ではない。
  2. "f"や"fo"の数を適切に管理しながら前から見ていく方針でいく。　→大半がWA
  3. この方針で解くことも不可能ではないと思うのだが、考慮漏れケースがわかりそうにないので別の方針を考える。
  4. "f"→"o"→"x"の順が満たされるときだけ再帰呼び出しされるようなDFSを書けないか試みるが、サンプルすら通らない。
    　
  5. ちょっと考え方を変えれば、再帰的なことをしなくても、スタック（実装上はデック）を使い、1文字追加するごとに後ろから3文字を調べればできそう。
  6. 後ろから2番目や3番目を取得することはできないので、一度3文字取り出してしまって、外れだったら戻す実装にする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

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 cnt = 0;
        Deque<Character> que = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            que.push(s[i]);
            if (que.size() >= 3) {
                char c1 = que.pop();
                char c2 = que.pop();
                char c3 = que.pop();
                if (c1 == 'x' && c2 == 'o' && c3 == 'f') {
                    cnt++;
                } else {
                    que.push(c3);
                    que.push(c2);
                    que.push(c1);
                }
            }
        }
        System.out.println(n - cnt * 3);
    }
}

A、C、Bと解いた時点で64分51秒＋2ペナ。669位。


C - Keep Graph Connected

問題
Bが解けていない焦りであまり集中できなくなっていたが、だいたい15～20分ほどで解けた。

思考過程
  1. UnionFindを使い、異なる連結成分の時だけ一方に辺のラベル、もう一方にはとりあえず何も設定しないといった埋め方をしていくと、既に両側が設定済みで条件を満たせないケースが出てくる。
    　
  2. グラフが木であれば、適当な根から見ていって、子に書き込む数値を以下のようにすることで達成できる。
    • 辺のラベルが親と同じなら適当な他の値でよく、ラベル+1（ラベルがNの場合は1）
    • 辺のラベルが親と異なる場合は、辺のラベル
  3. これは先に全域木に不要な辺を減らしておくとかしなくても、普通にBFSやDFSをすればできそうなのでBFSをする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
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<Hen>> 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 a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            int c = Integer.parseInt(sa[2]);

            list.get(a).add(new Hen(b, c));
            list.get(b).add(new Hen(a, c));
        }
        br.close();

        int[] ans = new int[n];
        Queue<Integer> que = new ArrayDeque<>();
        que.add(0);
        while (!que.isEmpty()) {
            int cur = que.poll();
            if (cur == 0) {
                ans[0] = list.get(0).get(0).c;
            }
            for (Hen h : list.get(cur)) {
                if (ans[h.v] == 0) {
                    if (ans[cur] == h.c) {
                        ans[h.v] = h.c % n + 1;
                    } else {
                        ans[h.v] = h.c;
                    }
                    que.add(h.v);
                }
            }
        }
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }

    static class Hen {
        int v, c;

        public Hen(int v, int c) {
            this.v = v;
            this.c = c;
        }
    }
}

A、Cと解いた時点で53分39秒＋0ペナ。595位。


D - AB

問題
Bに時間がかかりすぎたのがかなり痛く、時間内には解けず。
一応正当でない解法で、コンテスト終了1時間後に通した。（以下の思考過程はその内容）
1時間これを通すことに集中していたわけではないので、実際にはあと20～30分あればいけたかどうかといったところだろうか。

思考過程
  1. とりあえず例１をN=7くらいまで書いてみると、このケースでは"A"が2文字連続しないようだったが、規則性はいまいちつかめない。
  2. "AA"→0、"AB"→1、"BA"→2、"BB"→3のように頂点番号を置き換えて、グラフと捉えてみる。
  3. 例えばC_{AB}='B'とすると、"AB"→"ABB"なので、1→\{1, 3\}のような遷移になる。
  4. 遷移を全部書き出してみると、入力によっては"AA"や"BB"の頂点にたどり着けない場合がある。
  5. 「DP[i][j]：i番目まで見て末尾がjの場合の通り数」を行うが、愚直解と比較していまいち合わない。
  6. 上記の遷移でたどり着けるとしても、先頭の2文字目からいきなり"AA"と"AB"が両方可能とは限らなかった。
    　
  7. BFSをして、頂点0～3のそれぞれにたどり着く最短距離（頂点1を距離1とする）を求め、それ以降に限るようにしてみるが、まだ合わなそう。
  8. たどり着けるとしたらだいたい距離5くらいまでにはたどり着きそうなので、最短距離の求め方を、適当にN \lt 10で愚直に作った文字列内で最初に現れた位置としてみる。　→6ケースだけWA
    　
  9. 適当な手作成ケースで愚直と異なるパターンを探そうとするがすぐには見つからない。
  10. N \lt 10の全てのNと、AとBの組み合わせ2^4通り全てを試し、愚直と異なるパターンを洗い出す。
  11. N \geq 5で、C_{AA}='B'、C_{AB}='A'、C_{BA}='B'の場合のみ、正しい答えの2倍になってしまっていたので、それだけ場合分けする。（DPの中身は2倍になっていっているだけだったので、問題の場合だけ1つ前を出力）
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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));
        int n = Integer.parseInt(br.readLine());
        char[][] c = new char[2][2];
        c[0][0] = br.readLine().charAt(0);
        c[0][1] = br.readLine().charAt(0);
        c[1][0] = br.readLine().charAt(0);
        c[1][1] = br.readLine().charAt(0);
        br.close();

        int end = Math.min(n, 10);
        Set<String> set = new HashSet<>();
        set.add("AB");
        for (int i = 2; i < end; i++) {
            Set<String> wk = new HashSet<>();
            for (String s : set) {
                for (int j = 1; j < s.length(); j++) {
                    int a = s.charAt(j - 1) - 'A';
                    int b = s.charAt(j) - 'A';
                    wk.add(s.substring(0, j) + c[a][b] + s.substring(j));
                }
            }
            set = wk;
        }
//      System.out.println(set.size()); // 愚直解

        int[] x = new int[4]; // 思考過程7
        // 思考過程8
        Arrays.fill(x, Integer.MAX_VALUE);
        for (String s : set) {
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i - 1) == 'A' && s.charAt(i) == 'A') {
                    x[0] = Math.min(x[0], i);
                }
                if (s.charAt(i - 1) == 'A' && s.charAt(i) == 'B') {
                    x[1] = Math.min(x[1], i);
                }
                if (s.charAt(i - 1) == 'B' && s.charAt(i) == 'A') {
                    x[2] = Math.min(x[2], i);
                }
                if (s.charAt(i - 1) == 'B' && s.charAt(i) == 'B') {
                    x[3] = Math.min(x[3], i);
                }
            }
        }

        int mod = 1000000007;
        long[] dpa = new long[n];
        long[] dpb = new long[n];
        dpa[0] = 1;
        for (int i = 1; i < n; i++) {
            if (i >= x[0]) { // 思考過程7
                dpa[i] += dpa[i - 1];
            }
            if (i >= x[1]) { // 思考過程7
                dpb[i] += dpa[i - 1];
            }
            if (i >= x[2]) { // 思考過程7
                dpa[i] += dpb[i - 1];
            }
            if (i >= x[3]) { // 思考過程7
                dpb[i] += dpb[i - 1];
            }
            dpa[i] %= mod;
            dpb[i] %= mod;
        }
        if (n >= 5 && c[0][0] == 'B' && c[0][1] == 'A' && c[1][0] == 'B') { // 思考過程11
            System.out.println(dpb[n - 2]);
        } else {
            System.out.println(dpb[n - 1]);
        }
    }
}

　

EとFは問題読んだだけ。



最終結果：ABCの3完、74分51秒、748位、パフォーマンス1622
レート変動：1701→1693（-8）


B問題が全然解けない間は完全に終わったと思っていたので、まあなんとか傷を最小限にできたかなといったところ。
時間さえあればDまでできた可能性もあったが、茶diff問題にペナ込み1時間近くかけておいてこれで済んだのだから、まだ救われた方。

ちなみに過去茶diffを落としたのは、ABC122-CとAGC032-A（これ本当に茶色？）の2問だけらしい。当時のレートは緑。