AtCoder Grand Contest 058

コンテスト前のレート：2052
レート通りのパフォーマンスが得られる順位：404位（1100点、165分26秒）

A - Make it Zigzag

問題

思考過程

1. 前から見ていって条件を満たしていなければスワップしていくだけ？　→1ケースWA
2. 前からで回を超えてしまった場合は後ろから同様のことをやってみる？　→1ケースWA
   　
3. 要素をまとめて見てみると、その範囲内では回の操作で条件を満たせるように操作が可能。
4. 少なくとも前の要素については問題なくなるとして、個飛ばしに要素ずつ見ていくようにする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
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());
        int n2 = n * 2;
        String[] sa = br.readLine().split(" ");
        int[] p = new int[n2];
        for (int i = 0; i < n2; i++) {
            p[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n2 - 2; i++) {
            if (i % 2 == 0) {
                // 1, 2, 3 -> 1, 3, 2
                if (p[i] < p[i + 1] && p[i + 1] < p[i + 2]) {
                    list.add(i + 1);
                    swap(p, i + 1);

                // 2, 1, 3 -> 2, 3, 1
                } else if (p[i + 1] < p[i] && p[i] < p[i + 2]) {
                    list.add(i + 1);
                    swap(p, i + 1);

                // 3, 1, 2 -> 1, 3, 2
                } else if (p[i + 1] < p[i + 2] && p[i + 2] < p[i]) {
                    list.add(i);
                    swap(p, i);

                // 3, 2, 1 -> 2, 3, 1
                } else if (p[i + 2] < p[i + 1] && p[i + 1] < p[i]) {
                    list.add(i);
                    swap(p, i);
                }
            }
        }
        if (p[n2 - 2] > p[n2 - 1]) {
            list.add(n2 - 2);
        }

        System.out.println(list.size());
        if (!list.isEmpty()) {
            StringBuilder sb = new StringBuilder();
            for (int i : list) {
                sb.append(i + 1).append(' ');
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
        }
    }

    static void swap(int[] p, int i) {
        int t = p[i];
        p[i] = p[i + 1];
        p[i + 1] = t;
    }
}

ここまで20分15秒＋2ペナ。449位。

とりあえずBを見て、区間DPっぽさを感じてはそれだとで駄目だとか、の昇順や降順に見ていくことも考えてはDPの定義も遷移もわからないとかやっていて、経過時間70分辺りで飛ばしてCへ。

Cの方がやっていて考察が進むような感じがしたので、配点がBより高いこともあり、残り時間はCに集中していた。
雰囲気で言えば、同じ数字の連続は同一視した上での並びがの並びより多ければ可能っぽいような感じになってきていたが、最終的に半分程度のケースしか通らず。

最終結果：Aの1完400点、30分15秒、699位、パフォーマンス1648
レート変動：2052→2017（-35）

多分DPが弱い自分としてはBを捨ててCに行ったのは正解だったのだろうとは思うが、解説の考え方とちょっとズレていたのをどうすればよかったのか・・・。