AtCoder Regular Contest 141

コンテスト前のレート：2008
レート通りのパフォーマンスが得られる順位：314位（900点、38分42秒）

A - Periodic Number

問題

思考過程

1. とりあえず桁数がつ少ない全桁は作れる。
2. が桁の場合はなのでも答えの候補として考慮しておく。
   　
3. の桁数をとして、の約数（自身を除く）について、の先頭桁を取った値を回繰り返した値を考える。
4. 上記3.の値ならば答えの候補となる。
5. そうでなければ、を回繰り返した値は桁目がより小さいことにより必ず未満なので、それを答えの候補とする。　→サンプル以外誤り
6. がより桁減るケースを除く。

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++) {
            String s = br.readLine();
            long n = Long.parseLong(s);

            int len = s.length();
            long ans = 0;
            // 1
            for (int i = 0; i < len - 1; i++) {
                ans *= 10;
                ans += 9;
            }
            // 2
            ans = Math.max(ans, 11);
            for (int i = 1; i <= len / 2; i++) {
                if (len % i == 0) {
                    // 3
                    String x = s.substring(0, i);
                    StringBuilder sb = new StringBuilder();
                    while (sb.length() < len) {
                        sb.append(x);
                    }
                    long v = Long.parseLong(sb.toString());
                    if (v <= n) {
                        // 4
                        ans = Math.max(ans, v);
                    } else {
                        // 5
                        long y = Long.parseLong(x) - 1;
                        String sy = String.valueOf(y);
                        // 6
                        if (sy.length() != x.length()) {
                            continue;
                        }
                        sb = new StringBuilder();
                        while (sb.length() < len) {
                            sb.append(y);
                        }
                        v = Long.parseLong(sb.toString());
                        ans = Math.max(ans, v);
                    }
                }
            }
            pw.println(ans);
        }
        pw.flush();
        br.close();
    }
}

ここまで22分06秒＋1ペナ。500位。

B - Increasing Prefix XOR

問題

思考過程

1. との関係を考えると、進数でそれらの桁数が同じ場合、の最上位桁が落ちてしまうことになるため、は必ずより桁以上多くなる。
2. よって、の場合は通り。
   　
3. として各桁数の値をつずつ選んでいくならばあり得る個数を掛けていくだけだが、選ばれない桁数が存在することもあり得るため、そこまで単純ではない。
4. 「桁目まで見た時に個の数を選択済みである通り数」をする。

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();
        long m = sc.nextLong();
        sc.close();

        if (n > 60) {
            System.out.println(0);
            return;
        }

        int n2 = (int) n;
        int mod = 998244353;
        long b = 1;
        long[][] dp = new long[61][61];
        dp[0][0] = 1;
        for (int i = 1; i <= 60; i++) {
            long b2 = b * 2;
            // 選べるi桁の値の個数（値の上限はm）
            long v = b2 - b;
            if (m < b2) {
                v = Math.max(m - b + 1, 0);
            }
            v %= mod;
            for (int j = 0; j <= i; j++) {
                // i桁の値を選ばない
                dp[i][j] += dp[i - 1][j];
                // i桁の値を選ぶ
                if (j > 0) {
                    dp[i][j] += dp[i - 1][j - 1] * v;
                }
                dp[i][j] %= mod;
            }
            b = b2;
        }
        System.out.println(dp[60][n2]);
    }
}

ここまで47分18秒＋1ペナ。385位。

とりあえずC～Eを読むだけ読んで、残り時間の7割ほどをCに、3割ほどをDに使ってどちらも全然わからず。

最終結果：ABの2完900点、52分18秒、435位、パフォーマンス1823
レート変動：2008→1991（-17）

A問題慌てすぎ、B問題実装手間取りすぎという感じ。

それにしてもARCの難易度設定一体どうなってるんだろう。
ここのところ1問目から緑近い難易度の回が続いているが、1問目を灰diffにする気がないならRated範囲を上げた方がいいのではないかと思う。
理想的には200-900-1600-2100-2600-3100くらい？