AtCoder Regular Contest 145 - ks2mのブログ

A - AB Palindrome
- 思考過程
B - AB Game
- 思考過程
D - Non Arithmetic Progression Set
- 思考過程

コンテスト前のレート：2026
レート通りのパフォーマンスが得られる順位：304位（1500点、63分59秒）

A - AB Palindrome

問題
下記1.までで11分、3.までで20分かかっていて出だしからボロボロ。

思考過程

両端から見ていって、左側が'A'かつ右側が'B'ならアウト、左側が'B'かつ右側が'A'なら操作を行って合わせていく感じ？　→4割しか合っていない
　
そもそも両端以外はだいたい任意の文字列にできそうな気がしてくる。
'A'から始まって'B'で終わる以外は全部可能そう。　→1ケースWA
コーナーケースを考えてみると、他にあと"BA"だけ駄目なことに気付く。

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());
        char[] s = br.readLine().toCharArray();
        br.close();

        if (s[0] == 'A' && s[n - 1] == 'B' ||
                n == 2 && s[0] == 'B' && s[1] == 'A') {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

ここまで24分41秒＋2ペナ。1034位。

B - AB Game

問題

思考過程

$A \leq B$ ならば、最初にAliceが取れるだけ取れば余りは $A$ 未満であり、 $B$ 未満でもあるので必ず勝てる。
$N \lt A$ の場合だけ一度も取れずに負けるので、その分は引いておく。
　
$A \gt B$ の場合は、 $A=5, B=3$ とかで実験してみると、 $N=5, 6, 7, 10, 11, 12, 15, 16, 17, \cdots$ の時に勝てる。
取れるだけ取った余りが $B$ 未満なら勝てる模様。
また、上記1.の考察により、取れるだけ取らないことで勝てるようになることもない。
　
勝ちと負けの並びは $A$ 周期で繰り返すので、答えはおおよそ $B \times \frac{N}{A}$ になるが、最後の $1$ 周期分は余りが出る可能性があるため、余りと $B$ のminを取る。
　
WAが出たがすぐに原因がわかりそうにないので、提出デバッグをして駄目なところを絞り込む。
$A \gt B$ の中でREを発生させてみると、ACは減らなかったため、間違っていたのはなんと $A \leq B$ の方。
とりあえずちゃんと動かしてみると、答えがマイナスになったりしている。
入力が $N \lt A$ の場合に $0$ としていなかった。

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 n = Long.parseLong(sa[0]);
        long a = Long.parseLong(sa[1]);
        long b = Long.parseLong(sa[2]);
        br.close();

        if (n < a) {
            System.out.println(0);
        } else {
            if (a <= b) {
                System.out.println(n - a + 1);
            } else {
                long x = n / a;
                long v1 = b * (x - 1);
                long y = n % a + 1;
                long v2 = Math.min(y, b);
                System.out.println(v1 + v2);
            }
        }
    }
}

ここまで39分42秒＋4ペナ。607位。

Cは解けず。
とりあえず $1 \times 2 + 3 \times 4 + \cdots$ を作ればよいことはすぐわかったが、それを重複なく数える方法が全然わからず。
括弧列に対応させるというのも全然出てこなかった。

経過時間70分くらいからDも考え始め、90分経過する頃にはもうCが500～600人に通されていたのでDに賭けることにする。

D - Non Arithmetic Progression Set

問題
いつの間にかブラウザ右下に表示されている時刻が実際の時刻より20秒ほど進んでいて、まだ時間が残っているのに諦めそうになった。

思考過程

とりあえず合計が $M$ の条件は一旦忘れて、最小の要素を $0$ として任意の $3$ 要素が等差数列になっていない集合の作り方を考える。
これが作れれば、あとは程よく各要素から同じ値を足し引きし、最後の $1$ つだけ極端な値にして合計を合わせることでできそう。
　
しばらく手作業をしていたが埒が明かないので、可能な最小の値を集合に入れていく貪欲を書いてみる。
単純な貪欲では、最大の要素を $X$ とすると $O(XN)$ かかり、 $N=10^4$ では $10$ 秒ほどかかって $X=1679656$ を求められた。
数列を全部出力してみると $80000$ 文字には収まるくらいだったので、埋め込めるか？と思ったが、少なくとも自分の環境では65536バイト以上だとエラーになってしまい断念。もしかしたらちょっと分割すればいけたかもしれないが。
　
貪欲の出力結果は $1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, \cdots$ のようになっており、手作業の時から薄々気付いていたが、 $1, 2, 4, 8, \cdots$ 個ごとに一気に $2$ 倍になっている形。
それなら、 $1$ の次は $2$ から調べる、 $4$ の次は $8$ から調べる、 $13$ の次は $26$ から調べる、 $\cdots$ のようにしてやれば、無駄がほとんどなくなって $O(N^2)$ になるのではないか。
手元では $N=10^4$ でもなんとか $2$ 秒には収まっていそう。
　
あとは上記2.の部分を具体的にどうするかだが、貪欲の結果より、最後の要素に $2X$ （余裕をもって $4X$ としておく）以上を足せば非等差数列の条件は守られるはず。
よって、合計がだいたい $M-4X$ 程度になるように調整し、最後の要素に $M$ から実際の合計を引いた値を加算する。
　
調整値を足すか引くかを実装ミスしていてサンプル以外全てWA。
符号を直しつつ、残り時間を確認しながらゆっくり動作確認していたら急にコンテスト終了のお知らせが出てくる。
でも自分の時計ではまだあと $20$ 秒くらいあるはず？と思って一応慌てて提出してみたら、119:45でACとなった。

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(" ");
        int n = Integer.parseInt(sa[0]);
        long m = Long.parseLong(sa[1]);
        br.close();

        int[] a = new int[n];
        Set<Integer> set = new HashSet<>();
        set.add(0);
        int x = 1;
        int next = 1;
        int cnt = 0;
        // 3
        for (int i = 1; i < n; i++) {
            while (true) {
                boolean flg = true;
                for (int j = i - 1; j >= 0; j--) {
                    int val = a[j] - (x - a[j]);
                    if (val < 0) {
                        break;
                    }
                    if (set.contains(val)) {
                        flg = false;
                        break;
                    }
                }
                if (flg) {
                    a[i] = x;
                    set.add(a[i]);
                    break;
                }
                x++;
            }
            // 7
            cnt++;
            if (cnt == next) {
                x *= 2;
                cnt = 0;
                next *= 2;
            }
        }
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
        }
        // 4, 5
//      System.out.println(Arrays.toString(a));
//      System.out.println(sum);

        // 10
        long g = m - x * 4;
        long g2 = (g - sum + n - 1) / n;
        long sum2 = 0;
        for (int i = 0; i < n; i++) {
            a[i] += g2; // 11
            sum2 += a[i];
        }
        long add = m - sum2;
        a[n - 1] += add;

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

ここまで119分45秒＋5ペナ。223位。

EとFは問題を開いてもいない。

最終結果：ABDの3完1600点、144分45秒、224位、パフォーマンス2262
レート変動：2026→2052（+26）

2完59分42秒で終わっていたらパフォは1430ほどだったので、今回は立ち回りでパフォ800を稼いだ感じ。
1600点の人はたった14人しかおらず、時間が全然関係なくなったのもおいしかった。

カタラン数とか全然頭に入ってなかったし、自分はやっぱり知識寄りの問題に弱くて構築で時々大当たりがあるタイプなんだなと思う。