AtCoder Regular Contest 123

コンテスト前のレート:2129
レート通りのパフォーマンスが得られる順位:305位(1400点、124分04秒)

A - Arithmetic Sequence

問題

思考過程
  1. 基本的には真ん中で調整すると半分の回数で済む?と思ったが、操作は増やすのみで、減らすことはできなかった。
  2. 等差数列になっているかどうかは、A_1+A_3=2A_2かどうかで判定でき、成り立たないならば少ない方を増やすことになる。
  3. A_1+A_3 \gt 2A_2の場合、まず左辺が奇数ならば1加算し、あとはA_21増やすごとに差が2縮まるので、両辺の差\div 2を求める。
  4. A_1+A_3 \lt 2A_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));
        String[] sa = br.readLine().split(" ");
        long a = Long.parseLong(sa[0]);
        long b = Long.parseLong(sa[1]);
        long c = Long.parseLong(sa[2]);
        br.close();

        long ac = a + c;
        long b2 = b * 2;
        long ans = 0;
        if (ac > b2) {
            if (ac % 2 == 1) {
                ac++;
                ans++;
            }
            ans += (ac - b2) / 2;
        } else {
            ans = b2 - ac;
        }
        System.out.println(ans);
    }
}

ここまで5分33秒+0ペナ。195位。


B - Increasing Triples

問題

思考過程
  1. とりあえず典型的な考え方として、真ん中(B)に注目してみる。
  2. あらかじめA, B, Cをソートし、B_1から順に処理していく構造にする。
  3. Bのある要素B_Yについて、それが条件を満たす組として使用可能な場合、Aからは未使用の中から最小を、Cからは未使用かつB_Yより大きい中で最小を使うようにすれば、損をすることはなさそう。
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));
        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]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        int x = 0;
        int z = 0;
        int ans = 0;
        for (int y = 0; y < n; y++) {
            while (z < n && b[y] >= c[z]) {
                z++;
            }
            if (z < n && a[x] < b[y] && b[y] < c[z]) {
                ans++;
                x++;
                z++;
            }
        }
        System.out.println(ans);
    }
}

ここまで10分48秒+0ペナ。97位。


C - 1, 2, 3 - Decomposition

問題

思考過程
  1. 33 \cdots 33で引けるだけ引いて、33 \cdots 32で引けるだけ引いて、\cdotsという貪欲をしたらどうなるか調べてみると、例えば43の場合に(22, 21)とできるところが(33, 3, 3, 3, 1)となってしまう。
     
  2. 答えをaとしたとき、Nの各桁da個のグループに分けられるか(a \leq d \leq 3aであるか)という方向性で下の方の桁から調べていくことを考える。
  3. 10000などの場合は繰り下がりさせる必要があるので、d10+dを考慮するようにする。
  4. サンプルの314が通らず、必ずしも全ての桁をaグループに分けるのではなく、グループ数は一番下の桁から広義単調減少していく形になっていることがわかる。
     
  5. この時点で答えは最大でも45だろうという雰囲気を感じており、単調減少のさせ方を全探索しても_{23}C_5通りくらいかなと思うが、これだと計算量ぎりぎりそうで、実装も簡単にできそうになかったので、単調減少のさせ方全探索の方針は捨てる。
     
  6. ある桁について、d10+dそれぞれ、分けるグループ数を前の桁のグループ数から0まで試すDFSでできそう。
    (試し漏れがあったり、10+dの場合に上の桁から1引き忘れたりしてWA。)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        for (int z = 0; z < t; z++) {
            long n = Long.parseLong(br.readLine());
            pw.println(solve(n));
        }
        pw.flush();
        br.close();
    }

    static int solve(long n) {
        for (int a = 1; a < 7; a++) {
            if (dfs(n, a)) {
                return a;
            }
        }
        throw new RuntimeException();
    }

    static boolean dfs(long x, int m) {
        if (x == 0) {
            return true;
        }
        long d = x % 10;
        x /= 10;

        for (int i = m; i >= 0; i--) {
            if (i <= d && d <= i * 3) {
                if (dfs(x, i)) {
                    return true;
                }
            }
        }

        if (x > 0) {
            d += 10;
            x--;
            for (int i = m; i >= 0; i--) {
                if (i <= d && d <= i * 3) {
                    if (dfs(x, i)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

ここまで66分00秒+2ペナ。269位。



D以降は解けず。残り時間の大半はDに費やしていた。
とりあえず、マイナスが含まれている場合は、A_iの最小値を各要素から引いて、全部0以上にしても問題なさそうで、その上でB, Cに含まれるマイナスを少なくする問題になりそうとか考えていたくらいで、それ以上のことはほぼ何もわからず。



終結果:ABCの3完1300点、76分00秒、423位、パフォーマンス1966
レート変動:2129→2114(-15)


多分D問題は時間かけて解説読まないとできそうにないくらいだったので、C問題までちゃんと解けただけでもまあ良かったかなと思う。
現在のレートは実力と比べて過剰だと思っているので、2050切るくらいまでは慌てない。