AtCoder Beginner Contest 196(Rated範囲外)

A - Difference Max
- 思考過程
B - Round Down
- 思考過程
C - Doubled
- 思考過程
D - Hanjo
- 思考過程

コンテスト前のレート：2035
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：311位（1500点、68分19秒）

今回もD→C→B→A→E→Fの順にやってみようとするが、Dがすぐにわからなくて結局前から順に解く。

A - Difference Max

思考過程

こういう問題はとりあえず両端の組み合わせ $4$ 通りを全部試せばよさそう。

なお、実際は $B-C$ だけでよかった。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        sc.close();

        int ans = a - c;
        ans = Math.max(ans, a - d);
        ans = Math.max(ans, b - c);
        ans = Math.max(ans, b - d);
        System.out.println(ans);
    }
}

ここまで2分26秒＋0ペナ。3335位。

B - Round Down

問題
後から思えば、入力をBigDecimalで受け取って問題文通りの処理をするのでもよかった。

思考過程

前から $1$ 文字ずつ見てそのまま出力していき、'.'が出てきた時点で終了する。
今のAtCoderではいらないのかもしれないが、古い問題ではよく最後に改行を求めているので、念のため改行しておく。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String x = sc.next();
        sc.close();

        for (int i = 0; i < x.length(); i++) {
            if (x.charAt(i) == '.') {
                break;
            }
            System.out.print(x.charAt(i));
        }
        System.out.println();
    }
}

ここまで3分40秒＋0ペナ。1328位。

C - Doubled

問題

思考過程

前半の文字列としては最大 $10^6$ 通りあるので、それを全部試す。
$1$ ～ $10^6$ の数値を文字列化し、 $2$ つつなげ、もう一度数値化した値が $N$ 以下なら答えにカウント。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();

        int ans = 0;
        for (int i = 1; i <= 1000000; i++) {
            String s = String.valueOf(i);
            long a = Long.parseLong(s + s);
            if (a <= n) {
                ans++;
            } else {
                break;
            }
        }
        System.out.println(ans);
    }
}

ここまで6分13秒＋0ペナ。291位。

D - Hanjo

問題

思考過程

盤面の状態数がそれほど多くなさそうなので、メモ化再帰をしてみようとするが、次の1枚の置き方を全通り試して再帰すると、重複もたくさん出て駄目な気がする。
　
各マスが長方形のタイルで埋まっているか、正方形のタイルで埋まっているか、 $2^{HW}$ 通りを全探索し、その中で $2A+B=HW$ の条件を満たし、かつ可能な置き方であるものをカウントしていく方針で実装していく。
ところが、この「可能な置き方」が、例２を見ただけでも明らかに $1$ 通りとは限らない。
　
一応上記2.の全探索により、正方形の置き場所は決められているので、残ったスペースを長方形だけで埋める方法が何通りあるかをメモ化再帰で求めることにする。
次の1枚は必ず一番左上に置くことにすれば、縦向きと横向きの $2$ 通りを調べながら再帰していくことで、重複なくカウントができる。

import java.util.Scanner;

public class Main {
    static int h, w, a, b;
    static int cnt;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        h = sc.nextInt();
        w = sc.nextInt();
        a = sc.nextInt();
        b = sc.nextInt();
        sc.close();

        int ans = 0;
        int n = h * w;
        int end = 1 << n;
        for (int i = 0; i < end; i++) {
            // 2A + B ≠ HW の場合
            if (Integer.bitCount(i) != b) {
                continue;
            }

            String s = Integer.toBinaryString(i);
            StringBuilder sb = new StringBuilder(s);
            while (sb.length() < n) {
                sb.insert(0, '0');
            }

            // '0'：これから長方形で埋める箇所
            // '1'：正方形で埋まっている箇所
            // '2'：再帰中に長方形で埋めた箇所
            char[][] c = new char[h][w];
            for (int j = 0; j < n; j++) {
                c[j / w][j % w] = sb.charAt(j);
            }
            cnt = 0;
            dfs(c);
            ans += cnt;
        }
        System.out.println(ans);
    }

    static void dfs(char[][] c) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // まだ埋まっていない最初のマス
                if (c[i][j] == '0') {
                    // 縦向き
                    if (i < h - 1 && c[i + 1][j] == '0') {
                        c[i][j] = '2';
                        c[i + 1][j] = '2';
                        dfs(c);
                        c[i][j] = '0';
                        c[i + 1][j] = '0';
                    }
                    // 横向き
                    if (j < w - 1 && c[i][j + 1] == '0') {
                        c[i][j] = '2';
                        c[i][j + 1] = '2';
                        dfs(c);
                        c[i][j] = '0';
                        c[i][j + 1] = '0';
                    }
                    return;
                }
            }
        }
        // 全部埋まっている場合
        cnt++;
    }
}

ここまで30分03秒＋0ペナ。311位。

E問題は、合成関数を前計算して $O(N+Q)$ で解く方針でやってはいたが、おそらく何らかの値の管理に失敗していて7ケースほど通らない状態から抜け出せず。

F問題は愚直以外の解法を何も思いつかず。
解説見たら未習得事項だったので、これは解けなくても仕方ない。

最終結果：ABCDの4完、30分03秒、841位、パフォーマンス1582相当
レート変動：2035（Unrated）

黄色になってからというもの、ABC193は黄パフォ相当出ていたが、ABC194以降3回連続4完しかできず、パフォも緑、水、水相当とボロボロ。
F問題は黄diffあるのでまあ解けなくても仕方ないが、E問題でやらかし続けているのはいい加減まずい気がする。

今回のE問題は、Unratedなおかげで細かい考察が雑になりすぎていたところもあったかもしれない。
Ratedだったら焦ってしまってやっぱり解けなかったのかもしれないが・・・。