AtCoder Regular Contest 141

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

A - Periodic Number

問題

思考過程
  1. とりあえず桁数が1つ少ない全桁9は作れる。
  2. N2桁の場合は9 \lt 11なので11も答えの候補として考慮しておく。
     
  3. Nの桁数をLとして、Lの約数iL自身を除く)について、Nの先頭i桁を取った値X\frac{L}{i}回繰り返した値を考える。
  4. 上記3.の値\leq Nならば答えの候補となる。
  5. そうでなければ、X-1\frac{L}{i}回繰り返した値はi桁目がNより小さいことにより必ずN未満なので、それを答えの候補とする。 →サンプル以外誤り
  6. X-1Xより1桁減るケースを除く。
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. A_iA_{i+1}の関係を考えると、2進数でそれらの桁数が同じ場合、B_{i+1}の最上位桁が落ちてしまうことになるため、A_{i+1}は必ずA_iより1桁以上多くなる。
  2. よって、N \gt 60の場合は0通り。
     
  3. A_iとして各桁数の値を1つずつ選んでいくならばあり得る個数を掛けていくだけだが、選ばれない桁数が存在することもあり得るため、そこまで単純ではない。
  4. DP[i][j]:=i桁目まで見た時にj個の数を選択済みである通り数」をする。
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くらい?