AtCoder Regular Contest 148 - ks2mのブログ

A - mod M
- 思考過程
B - dp
- 思考過程
C - Lights Out on Tree
- 思考過程

コンテスト前のレート：2038
レート通りのパフォーマンスが得られる順位：358位（2000点、128分30秒）

A - mod M

思考過程

多くても、 $M=2$ とした場合 $2$ 種類にはできる。
$1$ 種類にできるのがどういう場合かを考えると、それは $A_i \% M$ が全て同じになるような $1$ より大きい $M$ が存在する場合。
$|A_i-A_1|$ のGCDを求め、それが $1$ より大きいかを調べる。　→WA
全て同じ値の場合GCDが $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));
        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 g = 0;
        for (int i = 0; i < n; i++) {
            g = gcd(g, Math.abs(a[i] - a[0]));
        }
        if (g != 1) {
            System.out.println(1);
        } else {
            System.out.println(2);
        }
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

ここまで4分31秒＋1ペナ。172位。

B - dp

問題

思考過程

'p'が含まれていない場合は何もしない。含まれている場合を考える。
初めて登場する'p'を'd'に変えるのが最適なので、 $L$ はそこしかない。
$R$ は'p'が多く続くところで終わるように選ぶのが良さそうな感じだが、 $O(N^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 s = br.readLine();
        br.close();

        String ans = s;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'd') {
                sb.append('d');
            } else {
                String s2 = sb.toString();
                for (int j = i; j < n; j++) {
                    StringBuilder sb2 = new StringBuilder();
                    sb2.append(s.substring(i, j + 1));
                    sb2.reverse();

                    StringBuilder sb3 = new StringBuilder(s2);
                    for (int k = 0; k < sb2.length(); k++) {
                        if (sb2.charAt(k) == 'p') {
                            sb3.append('d');
                        } else {
                            sb3.append('p');
                        }
                    }
                    sb3.append(s.substring(j + 1));
                    String t = sb3.toString();
                    if (t.compareTo(ans) < 0) {
                        ans = t;
                    }
                }
                break;
            }
        }
        System.out.println(ans);
    }
}

ここまで14分28秒＋1ペナ。157位。

C - Lights Out on Tree

問題

思考過程

ある頂点を表から裏にしたい場合、その頂点配下が全て裏になっているとすると、まず全ての子に対して操作して配下を全て表にしてから目的の頂点に対して操作を行えばよい。
上記1.の手順で葉から処理していけばよいので、この問題の形式では入力の後ろから処理すればよい。
入力の集合の各頂点に対し、基本的には子の数 $+1$ (自身)の操作回数が必要になるが、親も対象になっている場合は、最後に自身に対して操作をせず部分木を全て表の状態のままにしておけば、親の操作時に子 $1$ つ分の操作を省略できる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
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 n = Integer.parseInt(sa[0]);
        int q = Integer.parseInt(sa[1]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        sa = br.readLine().split(" ");
        int[] p = new int[n];
        p[0] = -1;
        for (int i = 0; i < n - 1; i++) {
            int a = Integer.parseInt(sa[i]) - 1;
            p[i + 1] = a;
            list.get(a).add(i + 1);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < q; z++) {
            sa = br.readLine().split(" ");
            int m = Integer.parseInt(sa[0]);
            int[] v = new int[m];
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < m; i++) {
                v[i] = Integer.parseInt(sa[i + 1]) - 1;
                set.add(v[i]);
            }

            long ans = 0;
            for (int i = m - 1; i >= 0; i--) {
                ans += list.get(v[i]).size();
                if (set.contains(p[v[i]])) {
                    // 親も対象の場合、自身分を加算せず親の回数を-1
                    ans--;
                } else {
                    ans++;
                }
            }
            pw.println(ans);
        }
        pw.flush();
        br.close();
    }
}

ここまで32分35秒＋1ペナ。171位。

残り時間のほとんどはDに使ったが解けず。
全ての要素が偶数個以外に後攻が勝てるケースをずっと考えていたが何もわからず。
最後の方は提出デバッグをしていて $M$ が偶数の場合が問題っぽいことまで絞れたがそこまで。
後で解説を見てもこれは自力では厳しいと思うような内容だった。
400人以上も解いていて辛い。

と思ったが、解説はぱっと見難しそうに見えただけで、要は例えば $M=4$ の時に $0$ ～ $3$ が全部奇数個だったとしたら、 $\{0, 3\}$ と $\{1, 2\}$ に分かれるような取り方だけではなく、 $\{0, 1\}$ と $\{2, 3\}$ でも後手勝ちにできるので、先手 $0$ に対して後手は $2$ を選べばあとは $1$ でも $3$ でもよいということだった。
そして、このような差 $\frac{M}{2}$ の組が偶数個あり、なおかつそれ以外に奇数個存在する数字がなければよいということだった。