AtCoder Regular Contest 142

コンテスト前のレート：2019
レート通りのパフォーマンスが得られる順位：329位（1200点、67分17秒）

A - Reverse and Minimize

問題
注意力なさすぎ。

思考過程

1. の後ろにを追加していく、を反転させたものの後ろにを追加していく、ということを回数をカウントしながらそれぞれを超えるまで行う。　→WA
2. が回文である場合に重複カウントしていたので対策する。　→WA
3. まだ何か重複カウントしてたりする？　よくわからないのでSetを使って確実に重複除去する。　→WA
4. そもそもの反転の場合は通りだった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
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));
        String[] sa = br.readLine().split(" ");
        long n = Long.parseLong(sa[0]);
        long k = Long.parseLong(sa[1]);
        br.close();

        StringBuilder sb = new StringBuilder();
        sb.append(k);
        sb.reverse();
        if (Long.parseLong(sb.toString()) < k) {
            System.out.println(0);
            return;
        }

        Set<Long> set = new HashSet<>();
        while (true) {
            long v = Long.parseLong(sb.toString());
            if (v <= n) {
                set.add(v);
                sb.append("0");
            } else {
                break;
            }
        }
        sb.reverse();
        while (true) {
            long v = Long.parseLong(sb.toString());
            if (v <= n) {
                set.add(v);
                sb.append("0");
            } else {
                break;
            }
        }
        System.out.println(set.size());
    }
}

ここまで10分54秒＋3ペナ。461位。

B - Unbalanced Squares

問題
唯一この問題だけまあまあすんなり解けた。

思考過程

1. とりあえず角や辺は隣接マスが奇数なので考える必要がない。
2. 単純に左上から右に向かって順に埋めていくと、で駄目。
3. 中央から渦巻状に埋めることを考えてみるが、周目くらいで駄目。
4. 上記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());
        br.close();

        int x = 1;
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j += 2) {
                a[i][j] = x;
                x++;
            }
            for (int j = 1; j < n; j += 2) {
                a[i][j] = x;
                x++;
            }
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(a[i][j]).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }
}

ここまで18分40秒＋3ペナ。258位。

C - Tree Queries

問題
延々と1ケース通らず苦しんだ。
一応最終的に通すことはできただけで多分まともに解けておらず、撃墜ケースは普通に作れる気がする。

思考過程

1. 回までということなので、と～、と～の間の距離がわかっているとして特定できるかどうか考える。
2. との位置関係ごとに、どういう値が返ってくるかを考える。
   　
3. との距離が偶数の場合、との中心となる頂点が存在することになり、とどちらからも同じ距離である頂点の中で最小距離であるものが該当し、答えは最小距離の倍。
   　
4. とが直径の両端である場合、～は全て、が等しくなる？　そうでない場合、までの最短パスとまでの最短パスの一方がもう一方を完全に包含するような頂点が存在し、距離の差が答えになる？　→1ケースのみWA。（※パスグラフなら合っているが、一般の木ではそうとは限らない）
   　
5. WAがケースのみなので、駄目そうなケースを探して色々試す。
6. のような形と、のような形が区別できていなかったので、適当にそれを見分けるようにして、あとは怪しさ満載だがケースWAの判定方法をそのままにしておく。

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

        // 1
        int[] d1 = new int[n + 1];
        int[] d2 = new int[n + 1];
        for (int i = 3; i <= n; i++) {
            System.out.println("? 1 " + i);
            d1[i] = sc.nextInt();
            System.out.println("? 2 " + i);
            d2[i] = sc.nextInt();
        }

        // 3
        int min = 1000;
        for (int i = 3; i <= n; i++) {
            if (d1[i] == d2[i]) {
                min = Math.min(min, d1[i]);
            }
        }
        if (min != 1000) {
            sc.close();
            System.out.println("! " + min * 2);
            return;
        }

        int sum = d1[3] + d2[3];
        boolean all = true;
        for (int i = 3; i <= n; i++) {
            int v = d1[i] + d2[i];
            if (v != sum) {
                all = false;
                break;
            }
        }

        int max = 0;
        for (int i = 3; i <= n; i++) {
            max = Math.max(max, Math.abs(d1[i] - d2[i]));
        }

        if (max == 1 && all) {
            // 6
            System.out.println("? 3 4");
            int d = sc.nextInt();
            if (d > 1) {
                System.out.println("! " + 1);
            } else {
                System.out.println("! " + sum);
            }
        } else if (max == 1) {
            System.out.println("! " + max);
        } else if (all) {
            System.out.println("! " + sum);
        } else {
            System.out.println("! " + max);
        }
        sc.close();
    }
}

ここまで70分14秒＋9ペナ。497位。

Dは長さ以上のパスグラフに分解すればよさそうなところまでは分ほどで考えられたが、その木DPが書けず。
実装が煮詰まって途中でEも問題だけ読んで、Eも考えてみたいと思ったが、時間が足りる気がしなかったので解法が見えかけているDに戻った。
最終的に、子の中からつ選ぶのを全通り調べなければならないのでは？となり、にしかならなそうで完全に行き詰まった。（正しいハマり方かどうかは知らない）

最終結果：ABCの3完1200点、115分14秒、675位、パフォーマンス1572
レート変動：2019→1981（-38）

ペナがなければほぼノルマ通りの時間だったので、もっと落ち着ければよかったのかもしれない。