AtCoder Grand Contest 054

コンテスト前のレート：2074
レート通りのパフォーマンスが得られる順位：324位（1900点、119分14秒）

A - Remove Substrings

問題

思考過程

1. なら回。以下、とする。
2. 前から見ていって、最初にとなるところで必ず切る貪欲をしてみた時のことを考えてみる。
3. そうすると、となった時点で終了することができ、ならば継続することになる。
4. 結局、かつとなる箇所が出てこない限り、終了することがない。
5. 逆に、そのような箇所があれば、その部分で切ることによって、回の操作で終了させることができる。

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] != s[n - 1]) {
            System.out.println(1);
            return;
        }

        for (int i = 2; i < n; i++) {
            if (s[0] != s[i - 1] && s[i] != s[n - 1]) {
                System.out.println(2);
                return;
            }
        }
        System.out.println(-1);
    }
}

ここまで6分08秒＋0ペナ。332位。

B - Greedy Division

問題
初め5～10分考えても何もわからず、先にCを解く。
下記8, 10は計算量に余計なlogを付けただけだったかもしれない。

思考過程

1. は当然駄目。各をどちらに振り分けるかを全探索するでも駄目。
2. そもそもまずの合計が奇数なら通り。
3. ナップサックのようなDPをして、の合計の半分（以下）になる選び方が何通りか求めてみる？とかしてもその先どうすればいいのかよくわからない。
   　
4. とりあえず例３で、合計がになる集合をつ固定してみる。
5. を並べる順番と、残りの集合を並べる順番を決めたら、その通りに取れる全体の並び順が一意に決まる。
6. つまり、つのについて、答えは通り。（は集合の要素数）
   　
7. あとは、「番目まで見て、その内個を選んで合計がとなる通り数」をしたいが、これだと空間計算量だけでとなり、厳しそう。
8. DPテーブルは上記のだけ持つことにし、さらに遷移する時に見る必要がある箇所しか見ない工夫をしてみる。
9. 以外の値が出てくる箇所のみをSetに入れていく。Setのサイズが倍々になっていきそうにも思えるが、DPテーブルのサイズを超えることはないので大丈夫なはず。
10. 個数無制限ナップサック状態になるのを避けるため、各についての降順に処理するようにTreeSetにする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.TreeSet;

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());
        String[] sa = br.readLine().split(" ");
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int mod = 998244353;
        // 2
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += w[i];
        }
        if (sum % 2 == 1) {
            System.out.println(0);
            return;
        }

        int m = sum / 2;
        int m1 = m + 1;
        long[][] dp = new long[n + 1][m1];
        dp[0][0] = 1;
        TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
        set.add(0);
        for (int i = 0; i < n; i++) {
            TreeSet<Integer> set2 = new TreeSet<>(Collections.reverseOrder());
            set2.addAll(set);
            for (int e : set) {
                int cx = e / m1;
                int cy = e % m1;
                int nx = cx + 1;
                int ny = cy + w[i];
                if (ny <= m) {
                    dp[nx][ny] += dp[cx][cy];
                    dp[nx][ny] %= mod;
                    set2.add(nx * m1 + ny);
                }
            }
            set = set2;
        }

        // 階乗を前計算
        long[] p = new long[n];
        p[0] = 1;
        for (int i = 1; i < n; i++) {
            p[i] = p[i - 1] * i % mod;
        }

        long ans = 0;
        for (int i = 1; i < n; i++) {
            // 6
            ans += dp[i][m] * p[i] % mod * p[n - i] % mod;
        }
        ans %= mod;
        System.out.println(ans);
    }
}

A,C,Bと解いた時点で60分08秒＋0ペナ。130位。

C - Roughly Sorted

問題

思考過程

1. 数列の長さをくらいにして色々いじってみると、が移動させられている可能性があるのは、より前により大きい要素がちょうど個存在する場合のみ。
2. 上記のような各は、元の順列において、～のどこにでも配置可能。
3. よって、条件を満たすについて、（0-indexedだとは不要）を掛け合わせていけばよい。（単純な掛け算でよさそうなことは、少し実験した）
4. より前により大きい要素がいくつ存在するかは、BITを用いて値の大きい順に処理していくことで求められる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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]);
        sa = br.readLine().split(" ");
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;
            o.p = Integer.parseInt(sa[i]);
            arr[i] = o;
        }
        br.close();

        int mod = 998244353;
        Arrays.sort(arr, (o1, o2) -> o2.p - o1.p);

        FenwickTree ft = new FenwickTree(n);
        long ans = 1;
        for (Obj o : arr) {
            long s = ft.sum(o.i);
            if (s == k) {
                int v = n - o.i;
                ans *= v;
                ans %= mod;
            }
            ft.add(o.i, 1);
        }
        System.out.println(ans);
    }

    static class Obj {
        int i, p;
    }
}

// 以下ACLを移植したFenwickTree

提出
A,Cと解いた時点で30分23秒＋0ペナ。170位。

残り1時間半は、Dに30分、Eに1時間くらい費やしていたと思う。
Cまでで十分すぎる結果だし、正解者数からして解けるとも思えなかったので、まったりと実験などしていた。

最終結果：ABCの3完1900点、60分08秒、138位、パフォーマンス2529
レート変動：2074→2129（+55）

最近大成功か大失敗かになることが多い気がする。
多分知識不足で弱点に当たると失敗して、方針がたまたま当たれば成功する感じだと思う。

自分のことはずっとエセ黄色だと思っていて、本当は青の実力しかないとか、本物の黄色は2100からとか思っていたが、とうとう2100の壁を突破したし、初めて黄色になってからもう4ヶ月経つし、4ヶ月間青には瞬間的にしか落ちてないし、そろそろきちんと黄色を名乗ってもいいのかもしれない。

・・・まあすぐ次で爆死しなければ。