AtCoder Regular Contest 113

ARC

コンテスト前のレート：2021
レート通りのパフォーマンスが得られる順位：410位（1800点、63分53秒）

A - A*B*C

問題

思考過程
  1. とりあえず1 \leq A \leq Kを全探索する。
  2. あり得るBの最大値Xは\frac{K}{A}となるので、1 \leq B \leq Xを全探索する。
  3. あり得るCの最大値Yは\frac{X}{B}となるので、それを答えに足す。
  4. 計算量はよくわからないが、K^2よりはだいぶ小さそう。実際に手元でK=2 \times 10^5を試して十分早く終了したので提出。
import java.util.Scanner;

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

        int ans = 0;
        for (int a = 1; a <= k; a++) {
            int x = k / a;
            for (int b = 1; b <= x; b++) {
                int y = x / b;
                ans += y;
            }
        }
        System.out.println(ans);
    }
}

ここまで2分39秒＋0ペナ。190位。


B - A^B^C

問題

思考過程
  1. 1の位だけを見るとして、Aは何乗かすれば同じ値に戻る周期性がある。
  2. その周期Mを求めつつ、M乗までの値を求めておく。Mはだいたい5以下。
  3. あとは、B^Cがmod Mでいくつであるかがわかればよい。
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();
        sc.close();

        int[] x = new int[10];
        x[0] = 1;
        x[1] = a % 10;
        int m = 0;
        for (int i = 2; i < x.length; i++) {
            x[i] = x[i - 1] * x[1] % 10;
            if (x[i] == x[1]) {
                m = i - 1;
                break;
            }
        }

        long y = power(b, c, m);
        if (y == 0) {
            y += m;
        }
        System.out.println(x[(int) y]);
    }

    // 以下ライブラリ

    // xのn乗をmで割った余り
    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }
}

ここまで10分14秒＋0ペナ。88位。


C - String Invasion

問題

思考過程
  1. サンプルを眺める限り、後ろから貪欲でよさそう。
  2. 例３が17になりそうな気がしたが、16なのは7文字目の'r'がカウントされないせい。
    　
  3. 後ろからやるのは実装しにくいので、まず反転させる。
  4. 同じ文字dが2連続出てきたところで、それより前のd以外の個数を答えに足し、個数の情報を更新する（全部dで他は0個）。
import java.util.Scanner;

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

        int n = s.length;
        reverse(s);

        long ans = 0;
        int[] cnt = new int[26];
        for (int i = 0; i < n - 1; i++) {
            int d = s[i] - 'a';
            if (s[i] == s[i + 1]) {
                ans += i - cnt[d];
                for (int j = 0; j < cnt.length; j++) {
                    if (d == j) {
                        cnt[j] = i;
                    } else {
                        cnt[j] = 0;
                    }
                }
            }
            cnt[d]++;
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    // 配列を反転させる
    static void reverse(char[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            char tmp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = tmp;
        }
    }
}

ここまで17分16秒＋0ペナ。42位。


D - Sky Reflector

問題
Cまで十二分に早くて安心していたのだが、結果的にはこれも早解きしなければならない問題だった。

思考過程
  1. とりあえず例１の構成を考えてみるが、特に何も見えてこない。
  2. まずはN行1列の場合を考えて、そこから1列ずつ増やしてみる。
    　
  3. N行1列の場合、B_1がiになる場合の通り数はi^N - (i-1)^N・・・などと考えたりもしたが、結局トータルではK^N通り。
  4. A_i = 1列目の値として適当に固定化して2列目を増やしてみると、2列目の各行の値は1列目より小さくできないので、B_1 \gt B_2とはならないことがわかる。
  5. 逆に、M \geq 2ならば、B_2以降はB_1以上の値なら何にすることもできる。
    　
  6. まず、B_1の値を1からKまで全部試す。
  7. B_1 = iとなる1列目の埋め方が、「i以下を自由に使える通り数」-「iを1個も使わずi-1以下しか使っていない通り数」なので、i^N - (i-1)^N通り。
  8. 行と列を逆にして、iを1個以上使う縛りでi～Kから選ぶ通り数を求めて、上記7.の結果と掛ければよいかと思ったりもしたが（ソースのコメント部分）、例１が合わない。
  9. 上記5.をちゃんと考えたら、N, M \geq 2ならば、i～Kから自由に選んでも、それが必ず構築できるので、(K-i+1)^Mでよかった。
    　
  10. M=1の場合しか例外処理しておらず2ケースWAになったので、N=1の場合もちゃんと処理する。
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();
        int m = sc.nextInt();
        int k = sc.nextInt();
        sc.close();

        int mod = 998244353;
        long ans = 0;
        // 3
        if (m == 1) {
            ans = power(k, n, mod);
            System.out.println(ans);
            return;
        }
        // 10
        if (n == 1) {
            ans = power(k, m, mod);
            System.out.println(ans);
            return;
        }

        // 6
        for (int i = 1; i <= k; i++) {
            // 7
            long x1 = power(i, n, mod);
            long y1 = power(i - 1, n, mod);
            long v1 = x1 - y1 + mod;
            v1 %= mod;

            // 8, 9
            long x2 = power(k - i + 1, m, mod);
//          long y2 = power(k - i, m, mod);
//          long v2 = x2 - y2 + mod;
//          v2 %= mod;

            long val = v1 * x2 % mod;
            ans += val;
        }
        ans %= mod;
        System.out.println(ans);
    }

    // 以下ライブラリ

    // xのn乗をmで割った余り
    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }
}

ここまで53分53秒＋1ペナ。311位。


E - Rvom and Rsrev

問題
正解者数的に解ける気がしなかったし、4完までで十分なパフォが出そうだったので、あまりやる気がなかった。
一応40分くらいはゆるく考えたがもちろん解けず。

考えたこと
  • 'a'が偶数ならだいたい末尾以外の'a'を全部消せばよさそう。
  • 'b'は極力消さないが、例の2ケース目のように消すこともある。
  • 最初に"aa"が出てくるところと、最後に"ba"が出てくるところの'a'を使い続ければだいたいできそうだが、やっぱり'b'を使うケースもあってどうすればいいのか・・・。

などなど。
解説見たら場合分けがたくさんあって長くてそっと閉じた。



最終結果：ABCDの4完、58分53秒、353位、パフォーマンス2092
レート変動：2021→2029（+8）


なんとか1日で青に戻るなんてことにはならず、無事黄色保持。
というわけでこの先最低2回はUnratedのABCとなることが確定したっぽい。
なお、自分はちょうどABCが4問制から6問制に変わる間で緑から水色になったので、レート上限によりABCがUnratedになるのは初めて。

それにしても、これまで黄パフォ以上は最大2連続だったのに、現在6連続とは、一体何がそんなに急に変わったのだろうか。
ABC188／ARC111以降、青diff以下を1問も落としていないので、だいぶ安定している感じにはなっているが。