AtCoder Regular Contest 125

コンテスト前のレート：2101
レート通りのパフォーマンスが得られる順位：297位（1400点、83分33秒）

A - Dial Up

問題
最初以外もあると勘違いしていて何もわからなかった。

思考過程

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

        int inf = 1000000007;
        int min0 = inf;
        int min1 = inf;
        int max0 = -1;
        int max1 = -1;
        for (int i = 0; i < n; i++) {
            if (s[i] == 0) {
                if (min0 == inf) {
                    min0 = i;
                }
                max0 = i;
            } else {
                if (min1 == inf) {
                    min1 = i;
                }
                max1 = i;
            }
        }

        boolean t0 = false;
        boolean t1 = false;
        for (int i = 0; i < m; i++) {
            if (t[i] == 0) {
                t0 = true;
            } else {
                t1 = true;
            }
        }

        // 1
        if (t0 && max0 == -1) {
            System.out.println(-1);
            return;
        }
        if (t1 && max1 == -1) {
            System.out.println(-1);
            return;
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            if (t[i] == s[0]) {
                // 2
                ans++;
            } else {
                // 3
                if (t[i] == 0) {
                    ans += Math.min(min0, n - max0);
                } else {
                    ans += Math.min(min1, n - max1);
                }
                ans++;

                // 4
                int p = t[i];
                for (int j = i + 1; j < m; j++) {
                    if (t[j] == p) {
                        ans++;
                    } else {
                        ans += 2;
                    }
                    p = t[j];
                }
                break;
            }
        }
        System.out.println(ans);
    }
}

ここまで16分03秒＋0ペナ。419位。

まさかのB以降何も解けず。

B問題は、～について、となるの範囲を二分探索で求めるような感じでやってみたが、ではTLEだった。手元実行では最大ケースで秒くらい。
longでもオーバーフローするので、絶対にこんな解法じゃないだろうとは思いつつ、一応BigIntegerで書くだけ書いてみたがやっぱり駄目だった。

C問題は手作業でなら、に含まれていない数を挿入する位置を小さい順に決めていけそうであったが、大小関係のパターンが色々ありそうで上手く実装に落とし込めず。

D問題は雰囲気でDPをしてみたが、例３が合わず。

最終結果：Aの1完300点、16分03秒、1102位、パフォーマンス1147
レート変動：2101→2034（-67）

約10ヶ月ぶりの緑パフォ。緑パフォはもう二度と取らないだろうと思ってるのに未だに取ってしまうとは・・・。

B問題でちゃんと式変形しようとしていないのとか、C問題で必死になって実装詰め切れないのとかが駄目だったところか。