yukicoder No.1095 Smallest Kadomatsu Subsequence

WriterやTester、その他の人の解法がいずれも自分とは違いそうだったので、初めて書いてみます。

問題

解法
  • 空の数列に、A_iの値が小さい順に元の位置に挿入していくことを考える。
  • 便宜上、「最小値のインデックス<2番目に小さい値のインデックス」とする。また、答えの門松列をX, Y, Zとする。
  • 3番目に小さい値以降の要素を追加時、毎回既存要素2個と追加要素を使用する最適な門松列を求め、それらの最小値を答えとする。
    1. 追加位置が末尾の場合、全体が単調増加になるため、門松列は作れない。
      ※この場合のみ実際に要素を追加し、以下の2つのケースでは要素を追加しない。単調増加列以外の要素は最適な門松列構築の邪魔になるだけのため。
    2. 追加位置が先頭の場合、追加要素をX、既存要素の先頭2つをY, Zとした下に凸の門松列が最適。
    3. 追加位置が先頭と末尾以外の場合、先頭要素をX、追加要素をY、追加要素が挿入される位置の次の要素をZとした上に凸の門松列が最適。
具体例

入力値:「9, 6, 1, 2, 5, 4」とする。

  • 1, 2, 4・・・4を追加するまでは解なし。
  • 1, 2, 5, 4・・・5を追加すると、上記3.のパターンにより、1+5+4=10が作られる。※5は追加せずに捨てる。
  • 6, 1, 2, 4・・・6を追加すると、上記2.のパターンにより、6+1+2=9が作られる。※6は追加せずに捨てる。
  • 9, 1, 2, 4・・・9を追加すると、上記2.のパターンにより、9+1+2=12が作られる。※9は追加せずに捨てる。
  • これらの最小値の9が答え。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeMap;
import java.util.TreeSet;

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

        // キー:Ai、値:Aiのindex
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            map.put(a[i], i);
        }

        TreeSet<Integer> set = new TreeSet<>();
        boolean inc = false; // 最小値のindex<2番目のindex かどうか
        int ans = Integer.MAX_VALUE;
        // Aiの小さい順に処理
        for (Integer k : map.keySet()) {
            if (set.size() == 0) {
                set.add(map.get(k));
            } else if (set.size() == 1) {
                if (set.last() < map.get(k)) {
                    inc = true;
                }
                set.add(map.get(k));
            } else {
                // 単調増加列 かつ 挿入位置が末尾以外
                if (inc && set.last() > map.get(k)) {
                    int f = set.pollFirst(); // パターン2.に対応するため一旦取り出す
                    int x = a[f]; // 先頭
                    int y = a[map.get(k)]; // 追加要素
                    int z = a[set.higher(map.get(k))]; // 追加要素の次
                    ans = Math.min(ans, x + y + z);
                    set.add(f);
                // 単調減少列の場合は逆のことをする
                } else if (!inc && set.first() < map.get(k)) {
                    int f = set.pollLast();
                    int x = a[f];
                    int y = a[map.get(k)];
                    int z = a[set.lower(map.get(k))];
                    ans = Math.min(ans, x + y + z);
                    set.add(f);
                // パターン1.
                } else {
                    set.add(map.get(k));
                }
            }
        }
        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}