AtCoder Regular Contest 120

コンテスト前のレート：2013
レート通りのパフォーマンスが得られる順位：295位（1900点、115分36秒）

A - Max Add

問題
全然わからず、先にBを解いてから戻ってくる。
一応ACはできたが、やっていたことは滅茶苦茶。きちんと丁寧にやらずに適当なことをしてると必ずミスってる。

思考過程

1. 例１ともう1つ適当なサンプルで、数値の並びを観察する。
2. の時の答えから、の時の答えをの差分計算で求められる方法を考える。
3. 数列の元の値の最大値と、足した後の最大値を管理しながら進めていく。

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

        PrintWriter pw = new PrintWriter(System.out);
        long ans = 0;
        long max = 0; // 足した後の値の最大値
        long maxa = 0; // 元の値の最大値
        // a = {1, 2, 3, 6} の場合
        // k = 1： 2
        // k = 2： 3 + 5
        // k = 3： 4 + 6 + 9
        // k = 4： 7 + 9 + 12 + 18
        for (int i = 0; i < n; i++) {
            // 以下の右コメントは、i = 3の時の各変数の変化
            if (a[i] > maxa) {
                ans += (a[i] - maxa) * i; // 4+6+9 → 7+9+12
                max += (a[i] - maxa); // 9 → 12
                maxa = a[i]; // 3 → 6
            }
            max = Math.max(a[i], max);
            a[i] += max; // 6 → 18
            ans += a[i];
            max = a[i]; // 12 → 18
            pw.println(ans);
        }
        pw.flush();
    }
}

BAと解いた時点で35分23秒＋3ペナ。579位。

B - Uniformly Distributed

問題
A問題と比べたら方針はすぐ見えた。
斜めに調べていくfor文を上手く書けなかった。

思考過程

1. 右上から左下に向かう斜めのラインについて、一直線上は全て同じ色である必要がある。
2. それはつまり、が同じマスは同じ色ということ。
3. が同じマスごとに調べていき、赤と青が混在していたら通り。
4. そうでなければ、全て無色の場合のみ通りの選択肢があるので、答えを倍していく。

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

        int mod = 998244353;
        int end = h + w - 2;
        long ans = 1;
        for (int i = 0; i <= end; i++) {
            int r = 0;
            int b = 0;
            int d = 0;
            // 斜めに調べる
            for (int j = 0; j < h; j++) {
                int j2 = i - j;
                if (j2 < 0 || w <= j2) {
                    continue;
                }
                if (s[j][j2] == 'R') r++;
                if (s[j][j2] == 'B') b++;
                if (s[j][j2] == '.') d++;
            }
            // 赤青混在
            if (r > 0 && b > 0) {
                System.out.println(0);
                return;
            }
            // 全て無色
            if (d > 0 && r == 0 && b == 0) {
                ans *= 2;
                ans %= mod;
            }
        }
        System.out.println(ans);
    }
}

Bだけ解いた時点で15分20秒＋1ペナ。629位。

C - Swaps 2

問題
基本的な方針が出てくるまではそれほど時間はかからなかったのだが、転倒数を貼ればよいことに気付かず、自力で数えようとしてこんがらがっていた。
（転倒数と気付かずに転倒数を自力実装するのに、30分以上かかってその間5ペナを出す始末）

思考過程

1. 操作を行ったときの値の変化を見てみると、同じ箇所に回操作を行うと元に戻り、特定の要素を運んでいくような操作をすると、左に動かす度に値がずつ増えていき、右に動かす度にずつ減っていくことがわかる。
2. 各要素を先頭まで動かした場合の値（0-indexedで、）ごとに分けて、まずはその結果の各値の出現数がとで一致しなければ-1。
   　
3. 同じ値が複数ある場合は、前から対応させていくのが最も操作回数が少なくて済む。
4. ここまででの各要素をどの位置に持って行きたいかが決まったが、例４を見ると、単純に現在地と目的地の差の総和ではなさそう。現在地から目的地への動線が交わっていれば、回の操作で回分の効果を得られたりする。
   　
5. 目的地が末尾のものから順に移動回数を調べていく。
6. を目的地に動かしたら、より後ろにある要素が全部つ前にずれる。
7. これを愚直にシミュレーションするとTLEのため、BITを使って、今動かそうとしている要素が何回ずらされているかをで求められるようにする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        // キー：先頭まで動かした時の値、値：該当要素のインデックスリスト
        Map<Integer, List<Integer>> map1 = new HashMap<>();
        Map<Integer, List<Integer>> map2 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int k = a[i] + i;
            List<Integer> list = map1.get(k);
            if (list == null) {
                list = new ArrayList<>();
                map1.put(k, list);
            }
            list.add(i);

            k = b[i] + i;
            list = map2.get(k);
            if (list == null) {
                list = new ArrayList<>();
                map2.put(k, list);
            }
            list.add(i);
        }

        // マップの内容が同一かどうかのチェックと、a[i]の目的地：c[i]の設定
        int[] c = new int[n];
        for (Integer k : map1.keySet()) {
            List<Integer> list1 = map1.get(k);
            List<Integer> list2 = map2.get(k);
            if (list2 == null || list1.size() != list2.size()) {
                System.out.println(-1);
                return;
            }
            for (int i = 0; i < list1.size(); i++) {
                c[list1.get(i)] = list2.get(i);
            }
        }

        // 目的地の降順
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o2.t - o1.t);
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;
            o.t = c[i];
            que.add(o);
        }

        long ans = 0;
        FenwickTree ft = new FenwickTree(n);
        while (!que.isEmpty()) {
            Obj o = que.poll();
            long sum = ft.sum(o.i); // 対象要素より前の要素を移動させた回数
            int v = (int) (o.i - sum); // 対象要素処理時点の現在地
            ans += Math.abs(v - o.t); // 目的地との距離を足す
            ft.add(o.i, 1);
        }
        System.out.println(ans);
    }

    static class Obj {
        int i, t;
    }
}

// 以下ACLを移植したFenwick Tree

提出
ここまで90分53秒＋8ペナ。567位。

残り時間はDとEを両方見てどちらかと言えばDメインでやることにするが、思考がどっちつかずになり破滅。
小さい半分と大きい半分に分けるのが最適であることすら気付いていなかった。

最終結果：ABCの3完、130分53秒、686位、パフォーマンス1459
レート変動：2013→1969（-44）

約3ヶ月黄色でいられたが、最近のABCの出来からしても、ちょっとすぐには復帰できそうにないくらい一気に落ちてしまった。
前回一瞬青落ちした時は1986だったので運良く1回で戻れたが、今回は1800台くらいまで落ちて完全に出直しになると思う。