AtCoder Regular Contest 143

コンテスト前のレート：1972
レート通りのパフォーマンスが得られる順位：386位（1400点、93分11秒）

A - Three Integers

問題
下記2.はだけやれば十分だった。

思考過程

1. とし、を必ず選択すれば操作回数に無駄は出ない。
2. まずを回ずつ選ぶことによって相対的にだけ減らすことができ、の形に持っていける。
3. この時点で負になっている数がなければ、あとは回全ての数を選び、回を選べば達成できる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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[] a = new long[3];
        for (int i = 0; i < 3; i++) {
            a[i] = Long.parseLong(sa[i]);
        }
        br.close();

        Arrays.sort(a);
        long x = a[2] - a[1];
        long ans = x * 2;
        a[0] -= x;
        a[1] -= x;
        a[2] -= ans;
        if (a[0] < 0 || a[1] < 0) {
            System.out.println(-1);
            return;
        }

        ans += a[1];
        System.out.println(ans);
    }
}

ここまで4分39秒＋0ペナ。247位。

B - Counting Grids

問題
すぐにはわからず先にCの問題だけ読んだが結局Bから解いていく。
下記4.までで延々合わない言っていて、下記5.に気付くのに10分くらい。

思考過程

1. 素直に条件を満たすものを数えるのと、余事象を数えるのと両方を念頭に置いて考える。
2. 条件を満たさない埋め方を考えてみると、条件を満たさない数は高々つしか作れなさそう。
3. 条件を満たさない数を～全探索し、全体の通り数から引く。
   　
4. 条件を満たさない数をとすると、同一列の埋め方が通り、同一行の埋め方が通り、の置き場所が通りとなり、これらを掛け合わせる。　→だと合うが、で合わない。
5. 残りのマスの埋め方の通り数を掛けていなかった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

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 mod = 998244353;
        int n2 = n * n;
        Kaijou kai = new Kaijou(n2, mod);
        long ans = kai.p[n2];
        int a = n2 - n - n + 1;
        for (int i = 1; i <= n2; i++) {
            long v1 = kai.perm(i - 1, n - 1);
            long v2 = kai.perm(n2 - i, n - 1);
            long val = v1 * v2 % mod * n2 % mod * kai.p[a] % mod;
            ans -= val;
        }
        ans %= mod;
        if (ans < 0) {
            ans += mod;
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static class Kaijou {
        long[] p, pi;
        int m;

        public Kaijou(int n, int mod) {
            n++;
            m = mod;
            p = new long[n];
            pi = new long[n];
            p[0] = 1;
            pi[0] = 1;
            for (int i = 1; i < n; i++) {
                p[i] = p[i - 1] * i % m;
            }
            pi[n - 1] = BigInteger.valueOf(p[n - 1])
                    .modInverse(BigInteger.valueOf(m)).longValue();
            for (int i = n - 1; i > 1; i--) {
                pi[i - 1] = pi[i] * i % m;
            }
        }

        public long comb(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[r] % m * pi[n - r] % m;
        }

        public long perm(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[n - r] % m;
        }
    }
}

ここまで31分38秒＋0ペナ。238位。

C - Piles of Pebbles

問題

思考過程

1. とりあえず例１について個数の遷移を書いてみてそれぞれのGrundy数を求めてみたりするが、それを例２でやろうとするとどうすればいいのかわからない。
   　
2. つの山にのみ注目すると、お互いが取り除く対象に選び続けた場合毎ターン個ずつ減っていく。
3. 最終的に個未満の状態で先手番になれば先手が負け、個未満の状態で後手番になれば後手が負ける。
4. 先手が最初の手目で全ての山についてで未満にできるなら先手勝ちということになりそう。（できなければ、次の後手番で全て未満にできそう。）
5. 例２が合わない。最低つの山は選んだ上で全て未満を達成する必要があった。

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 x = Integer.parseInt(sa[1]);
        int y = Integer.parseInt(sa[2]);
        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 xy = x + y;
        boolean flg = false;
        for (int i = 0; i < n; i++) {
            // 4
            int m = a[i] % xy;
            // 選ばない場合、選ぶ場合いずれもy以上の場合
            if (m >= y && (m - x + xy) % xy >= y) {
                System.out.println("Second");
                return;
            }
            // 5
            if ((m - x + xy) % xy < y) {
                flg = true;
            }
        }
        if (flg) {
            System.out.println("First");
        } else {
            System.out.println("Second");
        }
    }
}

ここまで52分20秒＋0ペナ。118位。

とりあえずDとE両方とも見たが、Dの方が正解者数が多く、とりあえずの方針も割とすぐに立ったのでDを解こうとする。

入力の辺のみからなるグラフから橋を取り除き、残りで連結成分ごとに全頂点を通るサイクルを作る（余った辺は適当に処理する）ということをすればよさそう？などと考え、橋を特定する方法を調べてLowLinkを見つけて写経していたり、サイクルを作るのに怪しいDFSをしていたりした。
（そもそも橋がないグラフに必ず全頂点を通るサイクルが存在するのかどうかがわからない）

結局残り5分になってようやく一旦提出まではできたが、半分以上TLEでWAも1つ出ていた。

LowLinkを写し始める前辺りでEにも10分くらいは割くべきだったかな・・・。

最終結果：ABCの3完1400点、52分20秒、280位、パフォーマンス2136
レート変動：1972→1990（+18）

C→Dが崖にならず、Cを通した直後のパフォから期待したほどの結果にはならず。
でもEまではかなり理想的な難易度だったと思う。

BもCも最初は全然わからなかったので、解けてホッとしている。