AtCoder Regular Contest 140

コンテスト前のレート:1994
レート通りのパフォーマンスが得られる順位:361位(1200点、72分35秒)

A - Right String

問題

思考過程
  1. SK回以内の操作で、長さXの文字列をY回繰り返した形に変えられる場合、Xが答えの候補となる。
  2. XとしてNの約数を小さい順に調べていって、初めて達成可能だった値を答えとする。
  3. 達成可能かどうかは、SX文字ごとに分割したY個の文字列のi文字目に最も多く登場する文字を調べ、それがM_i回だとすると、Y-M_i回の操作が必要になるので、1 \leq i \leq XについてのY-M_iの合計がK以下であるかどうかで判定できる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

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]);
        int k = Integer.parseInt(sa[1]);
        char[] s = br.readLine().toCharArray();
        br.close();

        List<Integer> list = divList(n);
        for (int x : list) {
            int y = n / x;
            int[][] cnt = new int[x][26];
            for (int i = 0; i < n; i++) {
                cnt[i % x][s[i] - 'a']++;
            }
            int val = 0;
            for (int i = 0; i < x; i++) {
                int max = 0;
                for (int j = 0; j < 26; j++) {
                    max = Math.max(max, cnt[i][j]);
                }
                val += y - max;
            }
            if (val <= k) {
                System.out.println(x);
                return;
            }
        }
    }

    // 以下ライブラリ(約数列挙)

    static List<Integer> divList(int n) {
        List<Integer> list = new ArrayList<>();
        int end = (int) Math.sqrt(n);
        for (int i = 1; i <= end; i++) {
            if (n % i == 0) {
                list.add(i);
            }
        }
        int i = end * end == n ? list.size() - 2 : list.size() - 1;
        for ( ; i >= 0; i--) {
            list.add(n / list.get(i));
        }
        return list;
    }
}

ここまで8分32秒+0ペナ。252位。


B - Shorten ARC

問題

思考過程
  1. "ARC"→"AC"を行うと、その部分は必ず行き詰まり、それ以上操作を行えることはない。
  2. "ARC"→"R"の場合は、元の文字列が"AAARCCC"のような場合、複数回操作を行える可能性がある。
     
  3. まず上記2.のような形をした箇所ごとに、"ARC"→"R"の操作が何回行えるかを調べ、その回数の集合を求める。
  4. これは、前から1文字ずつスタックに入れていき、"C"が出てきた時点で、前2文字が"R"と"A"ならば取り出して代わりに"R"をスタックに入れ、回数をカウントする。といったことを行う。
     
  5. 回数の集合は、1回のものと2回以上のものに分けて保持しておく。
  6. 偶数回目の操作は、残り2回以上であっても行うと0回になってしまうため、1回の方から優先的に使用する。
  7. 奇数回目の操作は、残り1回であるものの数をなるべく増やしておきたいので、残り2回以上のものの中で少ないものから優先的に使用する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

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();

        // 3
        Deque<Character> que = new ArrayDeque<>();
        List<Integer> list = new ArrayList<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // 4
            if (s[i] == 'C') {
                if (que.size() >= 2) {
                    char r = que.pop();
                    char a = que.pop();
                    if (a == 'A' && r == 'R') {
                        cnt++;
                        que.push('R');
                    } else {
                        que.push(a);
                        que.push(r);
                        que.push(s[i]);
                        if (cnt > 0) {
                            list.add(cnt);
                        }
                        cnt = 0;
                    }
                }
            } else {
                que.push(s[i]);
                if (cnt > 0) {
                    list.add(cnt);
                }
                cnt = 0;
            }
        }
        if (cnt > 0) {
            list.add(cnt);
        }

        // 5
        Queue<Integer> que1 = new ArrayDeque<>();
        PriorityQueue<Integer> que2 = new PriorityQueue<>();
        for (int e : list) {
            if (e == 1) {
                que1.add(e);
            } else {
                que2.add(e);
            }
        }

        int ans = 0;
        for (int i = 0; ; i++) {
            if (i % 2 == 0) {
                // 7
                if (!que2.isEmpty()) {
                    int e = que2.poll();
                    ans++;
                    e--;
                    if (e == 1) {
                        que1.add(e);
                    } else {
                        que2.add(e);
                    }
                } else if (!que1.isEmpty()) {
                    que1.poll();
                    ans++;
                } else {
                    break;
                }
            } else {
                // 6
                if (!que1.isEmpty()) {
                    que1.poll();
                    ans++;
                } else if (!que2.isEmpty()) {
                    que2.poll();
                    ans++;
                } else {
                    break;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで22分10秒+0ペナ。125位。


C - ABS Permutation (LIS ver.)

問題
またしょうもないミスで2ペナ。20分くらい損した。

思考過程
  1. X, (X-1), (X+1), (X-2), (X+2), \cdotsのような形を作るのが基本になりそう。
  2. X = \frac{N}{2}付近であれば、嬉しさが(N-1)になるようにできるが、そうでなければ2番目に\frac{N}{2}付近の値を置くことで嬉しさ(N-2)を達成させることになりそう。
     
  3. これは2番目の値を求めるより、Xを避けながら後ろから1, N, 2, (N-1), \cdotsまたはN, 1, (N-1), 2, \cdotsと決めていった方が楽にできそう。
  4. 両方作ってしまい、LISが大きい方を出力することにする。
     
  5. 隣り合う要素の差ではなく、上記3.の数列そのもののLISを調べていて1ペナ。
  6. 隣り合う要素の差の数列を作ったのに、LISを取得するメソッドに渡す数列が元のままになっていて1ペナ。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

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]);
        int x = Integer.parseInt(sa[1]);
        br.close();

        int l = 1;
        int r = n;
        if (l == x) l++;
        if (r == x) r--;
        List<Integer> list1 = new ArrayList<>(n);
        List<Integer> list2 = new ArrayList<>(n);
        while (l < r) {
            list1.add(l);
            list1.add(r);
            list2.add(r);
            list2.add(l);
            l++;
            r--;
            if (l == x) l++;
            if (r == x) r--;
        }
        if (l == r && l != x) {
            list1.add(l);
            list2.add(r);
        }
        list1.add(x);
        list2.add(x);
        Collections.reverse(list1);
        Collections.reverse(list2);

        List<Integer> list11 = new ArrayList<>();
        List<Integer> list22 = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            list11.add(Math.abs(list1.get(i - 1) - list1.get(i)));
            list22.add(Math.abs(list2.get(i - 1) - list2.get(i)));
        }
        int lis1 = lis(list11);
        int lis2 = lis(list22);
        if (lis1 >= lis2) {
            out(list1);
        } else {
            out(list2);
        }
    }

    static void out(List<Integer> a) {
        StringBuilder sb = new StringBuilder();
        for (int e : a) {
            sb.append(e).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    // 以下ほぼライブラリ(最長増加部分列の長さ)

    static int lis(List<Integer> a) {
        int n = a.size();

        // 長さiの部分列の最後の数値として最小のものを持つ配列
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < n; i++) {
            int idx = Arrays.binarySearch(dp, a.get(i));
            if (idx < 0) idx = ~idx;
            dp[idx] = a.get(i);
        }

        int lis = Arrays.binarySearch(dp, Integer.MAX_VALUE - 1);
        if (lis < 0) {
            lis = ~lis;
            lis--;
        }
        return lis;
    }
}

ここまで47分09秒+2ペナ。185位。



残り時間はほとんどEに使って解けず。
これまで大成功している回が構築系の橙diffを通している時であったため、今回も思い付き一発大成功を狙いに行った。

前日のABC251-Dのように入力が関係なく、500 \times 500固定で作れればよいので、乱択で時間をかけて答えを見つけて埋め込むということも考えたが、それの実装中に時間切れ。



終結果:ABCの3完1200点、57分09秒、276位、パフォーマンス2124
レート変動:1994→2008(+14)


割と普段負けっぱなしなのに、レートが2000を切った時だけ何故か勝てるような。
あと200くらい落ち続けるかと思っていたけど、青に落ちてから4回で黄色に戻ることができた。