AtCoder Regular Contest 147

ARC

コンテスト前のレート：1968
レート通りのパフォーマンスが得られる順位：416位（1400点、73分39秒）

A - Max Mod Min

問題
通ったなと思わせて最後の1ケースだけTLEになるのイヤらしい。
逆にもしそれがきっちり落としたいケースなのであれば、TLEケースをもういくつかは用意してC++でもちゃんと落ちるようにしてもらいたいところだが・・・。
結局自分も含めてたまたま通っただけな気がする。

思考過程
  1. シミュレーションするだけ？
  2. 最小と最大を取りたいのでPriorityQueueは使えず、TreeMap＜値、個数＞を使うことにする。　→1ケースTLE
  3. TLEだったが2200msではなく2094msなので本当にあと94msっぽい。ちょっと書き方変えてみたら通ったりしないか？　→しない
  4. 最小値が1になった時点で残りはシミュレーションではなく計算で求めてみる。　→1933msでなんとか通った
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeMap;

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

        MultiTreeSet<Integer> set = new MultiTreeSet<>();
        for (int i = 0; i < n; i++) {
            set.add(a[i]);
        }

        int ans = 0;
        while (true) {
            int min = set.first();
            if (min == 1) {
                ans += set.sizeAll() - 1;
                break;
            }
            int max = set.pollLast();
            ans++;
            int val = max % min;
            if (val != 0) {
                set.add(val);
            } else if (set.sizeAll() == 1) {
                break;
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ（未使用メソッド省略）

    static class MultiTreeSet<T> {
        TreeMap<T, Integer> map = new TreeMap<>();
        int size = 0;

        void add(T e) {
            map.put(e, map.getOrDefault(e, 0) + 1);
            size++;
        }

        void remove(T e) {
            if (e != null && map.containsKey(e)) {
                int val = map.get(e);
                if (val == 1) {
                    map.remove(e);
                } else {
                    map.put(e, val - 1);
                }
                size--;
            }
        }

        int sizeAll() {
            return size;
        }

        T first() {
            return map.firstKey();
        }

        T pollLast() {
            T e = map.lastKey();
            remove(e);
            return e;
        }
    }
}

ここまで15分45秒＋2ペナ。1309位。


この時点では緑パフォくらいでひどい出だし。

B - Swap to Sort

問題

思考過程
  1. 1から順番に合わせるとして、目的の位置まで2以上離れているなら操作B、1だけしか離れていないなら操作Aをするだけ？　操作回数はAだけだとオーバーするけどBが多数なら大丈夫では。　→サンプルすら1つ通っていない
  2. 操作Aの回数が最小というのを見落としていた。
  3. 操作Aは値の偶奇と位置の偶奇が合っていない要素同士の交換にしか使えないらしい。
  4. 基本は上記1.の貪欲のままで、左隣が合っていない要素の場合のみ操作Aを優先したらどうか？　→間に合っていない要素がない場合にすり抜けている
    　
  5. まず先に値の偶奇と位置の偶奇を全要素合わせてしまえば、あとは操作Bだけでできるようになる。
  6. 左から見ていって合っていない要素を見つけ、右隣が合っていない要素となるまで、操作Bで上記4.の要素を2つずつ右に移動させていく。　→WAだけでなくREも出ている。2つ先を見て配列外参照になっていそう。
    　
  7. 冷静に考えると、2つ先も合っていない要素の場合は入れ替えても無意味で、2つ先の要素を先に解消してからもう一度元の要素を処理する必要もある。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        List<String> list = new ArrayList<>();
        // 値の偶奇と位置の偶奇が合っていない箇所を解消させる
        for (int i = 0; i < n; ) {
            // 値の偶奇と位置の偶奇が合っていない場合
            if (p[i] % 2 != i % 2) {
                for (int j = i; j < n - 1; j += 2) {
                    // 右隣も合っていない場合、操作Aで解消
                    if (p[j + 1] % 2 != (j + 1) % 2) {
                        list.add("A " + (j + 1));
                        int t = p[j];
                        p[j] = p[j + 1];
                        p[j + 1] = t;
                        break;
                    // 2つ右が合っている場合は現在の要素を2つ右へ
                    // （合っていない場合は入れ替えず2つ右の要素を処理対象に）
                    } else if (p[j + 2] % 2 == (j + 2) % 2) {
                        list.add("B " + (j + 1));
                        int t = p[j];
                        p[j] = p[j + 2];
                        p[j + 2] = t;
                    }
                }
            }
            // 2つ右が合っていて現在の要素を処理できた場合
            if (p[i] % 2 == i % 2) {
                i++;
            }
        }

        // 値の偶奇と位置の偶奇が全て合った後
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (p[j] == i) {
                    int j2 = j;
                    while (j2 > i) {
                        list.add("B " + (j2 - 1));
                        int t = p[j2];
                        p[j2] = p[j2 - 2];
                        p[j2 - 2] = t;
                        j2 -= 2;
                    }
                    break;
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        pw.println(list.size());
        for (String s : list) {
            pw.println(s);
        }
        pw.flush();
    }
}

ここまで50分44秒＋5ペナ。695位。


一瞬ぎりぎり青パフォくらいにはなったがこの先ペナで落ちていくばかりだろうしもうボロボロ。

C - Min Diff Sum

問題

思考過程
  1. とりあえず例１や例３でRの昇順に並べたものとLの降順に並べたものを描いて眺めてみる。
  2. 中央付近の要素は、それより小さい値の個数と大きい値の個数が同じであれば、それらの個数が変わらない範囲内では値を何にしても答えは変わらない。　例１であれば、x_1=3, x_3=5とすると、x_2は3でも4でもよい。
    　
  3. Rの昇順とLの降順から1個ずつ取り出していき、大小関係がR \lt Lの場合はそのまま採用、R \geq Lとなった時点で残りの要素は全て同じ値にできる。
  4. ただし、その値はmax(前回のR, 今回のL)～min(今回のR, 前回のL)である必要がある。
    　
  5. ここまでで各人の座標が全て決まったので、あとは不満度を求める。
  6. これは(x_2-x_1), \cdots, (x_N-x_{N-1})の各区間に寄与数（両側の要素数の積）を掛けて求められる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

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());
        PriorityQueue<Obj> que1 = new PriorityQueue<>((o1, o2) -> o1.r - o2.r);
        PriorityQueue<Obj> que2 = new PriorityQueue<>((o1, o2) -> o2.l - o1.l);
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.l = Integer.parseInt(sa[0]);
            o.r = Integer.parseInt(sa[1]);
            que1.add(o);
            que2.add(o);
        }
        br.close();

        List<Integer> list = new ArrayList<>(n);
        int r = 0;
        int l = 10000001;
        for (int i = 0; i < n; i++) {
            Obj o1 = que1.poll(); // R最小を取り出す
            Obj o2 = que2.poll(); // L最大を取り出す
            int nr = Math.max(r, o1.r);
            int nl = Math.min(l, o2.l);
            if (nl <= nr) {
                int rem = n - list.size();
                int v = Math.max(r, nl);
                for (int j = 0; j < rem; j++) {
                    list.add(v);
                }
                break;
            } else {
                r = nr;
                l = nl;
                list.add(r);
                list.add(l);
            }
        }
        Collections.sort(list);

        long ans = 0;
        for (int i = 1; i < n; i++) {
            int e1 = list.get(i - 1);
            int e2 = list.get(i);
            long val = (long) (e2 - e1) * i * (n - i);
            ans += val;
        }
        System.out.println(ans);
    }

    static class Obj {
        int l, r;
    }
}

ここまで71分48秒＋5ペナ。339位。


とりあえずぎりぎり黄パフォに乗ったくらいにはなり、このまま終わっても大きなマイナスにはならないだろうというところまでは来られた感じ。
実際のところこのまま終わっていたらパフォ1850程度だった模様。


Dは何もわからず。少しして一応Eも見てみる。
なんかEの方が考えやすそうな見た目をしているのでEに賭けることにする。


E - Examination

問題

思考過程
  1. まずA_i \lt B_iとなっている人を全てピックアップする。
  2. ピックアップされず残っている人の内、Aが上記1.のBの最大値以上である人を入れ替え可能な人とする。
  3. 入れ替え可能な人の内Bが最小の人を入れ替え対象に選択する。
  4. 入れ替え対象のAと上記1.の最大のBを組にする。
  5. という貪欲をやっていけば損することはないように思える。
  6. あとはO(N^2)とかにならないようPriorityQueueを駆使して実装する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

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());
        // ピックアップされていない人（Aの降順）
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o2.a - o1.a);
        // ピックアップされているA（降順）
        PriorityQueue<Integer> qa = new PriorityQueue<>(Collections.reverseOrder());
        // ピックアップされているB（降順）
        PriorityQueue<Integer> qb = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[0]);
            o.b = Integer.parseInt(sa[1]);
            if (o.a < o.b) {
                // 1
                qa.add(o.a);
                qb.add(o.b);
            } else {
                que.add(o);
            }
        }
        br.close();

        // 入れ替え可能な人（Bの昇順）
        PriorityQueue<Obj> que2 = new PriorityQueue<>((o1, o2) -> o1.b - o2.b);
        while (!qb.isEmpty()) {
            int b = qb.poll();
            int a = qa.peek();
            // それぞれ最大値を取り出し、組にできるならする
            if (a >= b) {
                qa.poll();
                continue;
            }
            // 2. Bの最大値以上の人を入れ替え可能キューに移動
            while (!que.isEmpty()) {
                Obj o = que.peek();
                if (o.a < b) {
                    break;
                }
                que.poll();
                que2.add(o);
            }
            if (que2.isEmpty()) {
                System.out.println(-1);
                return;
            }
            // 3. 4. o2.aとbを組にする
            Obj o2 = que2.poll();
            qa.add(o2.a);
            qb.add(o2.b);
            qa.poll();
        }
        System.out.println(que.size() + que2.size());
    }

    static class Obj {
        int a, b;
    }
}

ここまで98分34秒＋5ペナ。72位。


ケース数が多いにもかかわらずジャッジの進行を見守り、通った瞬間大喜び。


残り時間は一応やんわりとDを考え直すも、集合の作り方が2^M \times M^{N-1}通り？くらいしかわからず。



最終結果：ABCEの4完2200点、123分34秒、114位、パフォーマンス2531
レート変動：1968→2038（+70）


自身8回目の橙パフォ（内3回がABCカンスト）で8回目の入黄。
-35, -47, -42と急落しておれはもうだめだと思ったところから+57, -17, +70でほぼ回復しており、なんかもう上下幅が100程度なら大したことないように思えてきた。

今回AやBが穴だらけの考察しかできていなくて、一番しっかり解けたのがEだった気がする。（気付いていないだけで実は嘘とかでなければ）