AtCoder Regular Contest 134

コンテスト前のレート:2044
レート通りのパフォーマンスが得られる順位:357位(1800点、149分07秒)

A - Bridge and Sheets

問題

思考過程
  1. 全部でN+1個の区間について、位置0またはa_i+Wから続けて設置していくのが最適。
  2. 区間については、\frac{a_i - a_{i-1}}{W}の切り上げから既に設定されている1枚を引くことで必要枚数を求められる。
  3. 実装上は番兵を入れてa_0=-Wとすることで、最初と最後の区間も場合分けせずまとめて処理できる。

下記コード内のmaxは、-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();
        long l = sc.nextLong();
        long w = sc.nextLong();
        long[] a = new long[n + 2];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
        }
        sc.close();
        a[0] = -w;
        a[n + 1] = l;

        long ans = 0;
        for (int i = 1; i < a.length; i++) {
//          ans += Math.max((a[i] - a[i - 1] + w - 1) / w - 1, 0);
            ans += Math.max((a[i] - a[i - 1] - 1) / w, 0);
        }
        System.out.println(ans);
    }
}

ここまで5分48秒+0ペナ。374位。


B - Reserve or Reverse

問題

思考過程
  1. 例3を見ながら考えると、前の方に'a'以外の文字が出てきたら、なるべく多く'a'と入れ替えたいので、最も後ろの'a'と入れ替えていくのが最適。
  2. もっと一般的に言えば、入れ替え対象候補(左側)より後ろで、前回入れ替えた対象(右側)よりも前にある最も後ろの最小の文字が、入れ替え対象候補(左側)よりも小さければ入れ替える。 という貪欲をすればよさそう。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.TreeSet;

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

        // 各文字ごとに分けて登場するindexを保持
        List<TreeSet<Integer>> list = new ArrayList<>(26);
        for (int i = 0; i < 26; i++) {
            list.add(new TreeSet<>());
        }
        for (int i = 0; i < s.length; i++) {
            list.get(s[i] - 'a').add(i);
        }

        int r = n - 1;
        for (int l = 0; l < r; l++) {
            int c = s[l] - 'a';
            // 入れ替え対象候補(左側)より小さい文字だけ調べる
            for (int i = 0; i < c; i++) {
                // 前回入れ替えた対象(右側)より前で最も後ろのindexを取得
                Integer x = list.get(i).floor(r);
                // 入れ替え対象候補(左側)より後ろに存在する場合
                if (x != null && l < x) {
                    char t = s[l];
                    s[l] = s[x];
                    s[x] = t;
                    r = x - 1;
                    break;
                }
            }
        }
        System.out.println(s);
    }
}

ここまで16分49秒+0ペナ。193位。


C - The Majority

問題
いつも貼っているような部分を自力で書いたら下記6.でREを出してしまったが、それをやらかさなくても多分下記8.に気付かずWAを出してしまっていたと思うので、REの方が原因に気付きやすくて結果オーライだったかもしれない。
そもそも最初にTLEになったのが痛手なのだが。(ライブラリに問題があった)

思考過程
  1. 例1の答えが2しかないことから空箱は駄目だとわかるので、まず全ての箱に固定で11個ずつ入れてしまうことにする。
  2. 続いて、過半数であることを維持するために、2N1とセットで入れていくことにすると、残った1については、2Nと同様に自由に入れる箱を決められることになる。
     
  3. 以上により、まずa_1K+\sum_{i=2}^Na_i未満であれば0通り。
     
  4. あとはa_iK個の箱に分ける通り数の総積を求めるだけだが、これはa_i個のボールとK-1個の仕切りの並べ方の通り数なので、_{a_i+K-1}C_{a_i}または_{a_i+K-1}C_{K-1}となる。
  5. 計算量を考慮すると、後者ならばO(K)で求められる。 →4/33ケースTLE
     
  6. 逆元を毎回求めていてO(NKlogK)になっていたので、逆元は一度だけ求めるようにしてO(KlogK+NK)となるようにする。 →6/33ケースRE
     
  7. K=1200を試した結果、K=1の場合に配列外参照をしていたので対策する。
  8. その際N=1, K=1の場合結果が1であるべきところ0になっていることに気付いたので対策する。
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 k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int mod = 998244353;
        // 3
        a[0] -= k;
        for (int i = 1; i < n; i++) {
            a[0] -= a[i];
            if (a[0] < 0) {
                System.out.println(0);
                return;
            }
        }

        // 7. kが1だと配列外参照するためサイズは適当に+1
        long[] pi = new long[k + 1];
        pi[1] = 1;
        for (int i = 2; i < k; i++) {
            pi[i] = pi[i - 1] * modinv(i, mod) % mod;
        }

        long ans = 1;
        for (int i = 0; i < n; i++) {
            long x = a[i] + k - 1;
            long v = 1;
            for (int j = 0; j < k - 1; j++) {
                v *= x - j;
                v %= mod;
            }
            v = v * pi[k - 1] % mod;
            // 8. a[0]が0の場合、xCxは1なのでスキップ
            if (v != 0) {
                ans *= v;
                ans %= mod;
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ(aのmod mでの逆元)

    static long modinv(long a, int m) {
        long b = m;
        long u = 1;
        long v = 0;
        long tmp = 0;

        while (b > 0) {
            long t = a / b;
            a -= t * b;
            tmp = a;
            a = b;
            b = tmp;

            u -= t * v;
            tmp = u;
            u = v;
            v = tmp;
        }

        u %= m;
        if (u < 0) u += m;
        return u;
    }
}

というか後から_nC_rを求めるライブラリの中身を直したら、それだけでも通った。
TLE提出 改善後AC提出
ここまで36分14秒+2ペナ。185位。


D - Concatenate Subsequences

問題
Integer同士を==で比較していたミスで22分溶かした。
Integerとintの比較なら問題ないので、「ans2.get(0)」を変数に入れるとかしていれば・・・。

思考過程
  1. サンプルを見ると、基本的には前半部分について以下のように選択していく感じ。
    1. 最も小さい数を全て選択する。
    2. 上記の最後の要素より後ろの部分だけ見て、最も小さい数を全て選択する。
    3. 以降同様
  2. ただし、上記1-2.以降は、1-1.で選択された後半部分の先頭要素より大きくなった時点で終了する。
     
  3. 小さい場合は選択してよいが、同じときがよくわからない。
  4. というかそもそも(3, 3, 1, 1)のように後半部分の方が小さかったら、(3, 3, 1, 1) \gt (3, 1)なので1-1.で全部選択しては駄目。
  5. まず1-1.で、後半部分の対応要素に前半部分の最小値以下のものが出てきたら、前半の最小値と後半の最小値の2つのみを出力して終了する。
  6. そうでない場合は1-1.で全て選択してよく、以下「前半の最小値\lt答えの後半の先頭要素」を前提とできる。
     
  7. あとは上記3.の「前半の今判別したい要素=答えの後半の先頭要素」のケースが問題。
    例えば(9, 3, 9, 3, 5, 51, 5, 1, 4, 2, 3)(※見やすさのため前半と後半を「/」で区切っている)のような場合、(3, 35, 4)が選択済みのところに、(52)(53)を追加してよいのかどうか。
  8. これは、答えの後半の要素を先頭から調べて、減少するよりも先に増加している箇所があれば全て追加、減少している箇所が先かもしくは全て同じ値の場合は1つも追加しないのが良い。
    上記7.の例では5 \gt 4のため追加しない。
     
  9. 5/95ケースだけWAとなり、考慮漏れケースがないか、N=1は問題ないかなど洗い直すも欠陥は見つからず、オーバーフローなどを疑ってソースをじっくり見直したら、Java特有の判定方法のミスに気付いた。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int n2 = n * 2;
        int[] a = new int[n2];
        for (int i = 0; i < n2; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        // 値、対応するindexリスト
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list = map.get(a[i]);
            if (list == null) {
                list= new ArrayList<>();
                map.put(a[i], list);
            }
            list.add(i);
        }

        Integer[] arr = map.keySet().toArray(new Integer[0]);
        // 5
        List<Integer> list0 = map.get(arr[0]);
        int min = 1000000001;
        for (int i : list0) {
            min = Math.min(min, a[i + n]);
        }
        if (min <= a[list0.get(0)]) { // a[list0.get(0)]はarr[0]でも同じ
            System.out.println(a[list0.get(0)] + " " + min);
            return;
        }

        List<Integer> ans1 = new ArrayList<>();
        List<Integer> ans2 = new ArrayList<>();
        // 1-1
        for (int e : list0) {
            ans1.add(a[e]);
            ans2.add(a[e + n]);
        }

        int idx = list0.get(list0.size() - 1); // 選択済みの最終index
        for (int i = 1; i < arr.length; i++) {
            boolean flg = true;
            // 2
            if (arr[i] > ans2.get(0)) {
                flg = false;
            // 8
            } else if (arr[i].equals(ans2.get(0))) { // 9. ==では駄目
                flg = false; // 全て同じ場合
                for (int j = 1; j < ans2.size(); j++) {
                    // 増加が先
                    if (ans2.get(j) > ans2.get(0)) {
                        flg = true;
                        break;
                    }
                    // 減少が先
                    if (ans2.get(j) < ans2.get(0)) {
                        break;
                    }
                }
            }
            if (!flg) {
                break;
            }
            // 1-2
            List<Integer> list = map.get(arr[i]);
            for (int e : list) {
                if (e > idx) {
                    ans1.add(a[e]);
                    ans2.add(a[e + n]);
                    idx = e;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i : ans1) {
            sb.append(i).append(' ');
        }
        for (int i : ans2) {
            sb.append(i).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで84分53秒+3ペナ。178位。



EとFは問題は読んだが何もわからず。



終結果:ABCDの4完1800点、99分53秒、202位、パフォーマンス2311
レート変動:2044→2074(+30)


十分良い結果なのだが、Dのミスがなければ22分ほど縮まってパフォ2510くらい。
加えてCがTLEにならなければ、さらに20分ほど縮まってパフォ2700くらい。
という可能性もあったかもしれず、もったいなかった。

まあ正直どの問題も解法に完全な自信を持って提出できたわけではなかったので、解法に根本的な誤りがあってのペナが出なかっただけでも上出来だったし、ペナが出たことによってライブラリ整備など得たものもあったので良しとする。