AtCoder Regular Contest 136

コンテスト前のレート：2060
レート通りのパフォーマンスが得られる順位：330位（1300点、84分42秒）

A - A ↔ BB

問題

思考過程

1. "A"と"B"が並んでいるところを"AAAAB"のように変換するのが最適。
2. 一旦全部"A"→"BB"に変換した後、前から"BB"→"A"に変換すればよい。
3. これはreplaceメソッドを使うだけ。

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());
        String s = br.readLine();
        br.close();

        s = s.replace("A", "BB");
        s = s.replace("BB", "A");
        System.out.println(s);
    }
}

ここまで1分45秒＋0ペナ。5位。

B - Triple Shift

問題
下記思考過程3.の後くらいに、何らかの不変量がないかは考えたのだが、転倒数の偶奇なんて全然出てこなかった。

思考過程

1. とを集合として見た時に内訳が一致していればだいたい可能なのでは？
2. 次の段階の考察に分以上かかりそうだったのでとりあえずそれだけで一旦提出。当然WA。
3. ちょっと考えれば、をにできないことくらいはすぐにわかった。。。
   　
4. では、前から貪欲に揃えていって、最後のつが揃わなければ"No"か？
5. 手元で数列をいじってみたところ、位置から位置まで左に移動させた場合、インデックスの差が偶数の場合は～の奇数個をまとめてrotateした結果になる。
6. 偶数の場合は、～をrotateさせた後、～で回操作（実質左にrotate）する。
7. 乗が間に合う制約なので、この愚直シミュレーションをしても計算量は大丈夫そう。
8. これだと例２が通らず、最後のつが揃わなければ末尾つでもう回rotateも試してみる。　→WA
   　
9. 上記5.の位置を決めるのに、前から調べて最初に見つかったものとしていたが、同じ値が複数ある場合は後ろのものを採用した時のみ達成できるケースがありそう。
10. 実験してみると、どうやら何かしら同じ値が個あれば"Yes"になりそう。
11. なんとなく、個セットが必要な気がしたので、個数が偶数の値が存在するかという判定にした。（が、おそらく個以上なら何個でも"Yes"になりそう）

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

        // 1.集合の内訳チェック
        int[] ca = new int[5001];
        int[] cb = new int[5001];
        for (int i = 0; i < n; i++) {
            ca[a[i]]++;
            cb[b[i]]++;
        }
        for (int i = 0; i < ca.length; i++) {
            if (ca[i] != cb[i]) {
                System.out.println("No");
                return;
            }
        }

        for (int i = 0; i < n - 2; i++) {
            if (a[i] != b[i]) {
                for (int j = i + 1; j < n; j++) {
                    if (a[j] == b[i]) {
                        int d = j - i;
                        if (d % 2 == 0) {
                            // 5
                            rotateR(a, i, j);
                        } else {
                            // 6
                            if (d >= 3) {
                                rotateR(a, i + 1, j);
                            }
                            rotateL(a, i, i + 2);
                        }
                    }
                }
            }
        }
        // 4. 最後の2つをチェック
        if (a[n - 2] != b[n - 2] || a[n - 1] != b[n - 1]) {
            for (int i = 0; i < ca.length; i++) {
                // 11. ここは ca[i] >= 2 だけでないと駄目そう
                if (ca[i] > 0 && ca[i] % 2 == 0) {
                    System.out.println("Yes");
                    return;
                }
            }
            System.out.println("No");
            return;
        }
        System.out.println("Yes");
    }

    // 以下ライブラリ

    static void rotateL(int[] val, int beg, int end) {
        int tmp = val[beg];
        for (int i = beg; i < end; i++) {
            val[i] = val[i + 1];
        }
        val[end] = tmp;
    }

    static void rotateR(int[] val, int beg, int end) {
        int tmp = val[end];
        for (int i = end; i > beg; i--) {
            val[i] = val[i - 1];
        }
        val[beg] = tmp;
    }
}

ここまで32分00秒＋3ペナ。446位。

Cは小さい順に処理することをやってみたりしたが、何が悪いのかわからず。
Dは桁ごとに見ようとしても桁間の関連性をどうにもできず、また何らかのDPっぽさも感じてはいたが何もわからず。

最終結果：ABの2完700点、47分00秒、777位、パフォーマンス1582
レート変動：2060→2020（-40）

解説見た限り、AHCの影響で疲れているとか関係なく、CもDも自分には解けない問題だったと思う。
Bも解けたとは言い難く、ペナを1つ2つ減らせる余地はなくはなかったが、10分早まったところでパフォ50程度しか変わらないし、通せただけでもマシだった。