yukicoder No.1095 Smallest Kadomatsu Subsequence
WriterやTester、その他の人の解法がいずれも自分とは違いそうだったので、初めて書いてみます。
解法
- 空の数列に、の値が小さい順に元の位置に挿入していくことを考える。
- 便宜上、「最小値のインデックス番目に小さい値のインデックス」とする。また、答えの門松列をとする。
- 番目に小さい値以降の要素を追加時、毎回既存要素個と追加要素を使用する最適な門松列を求め、それらの最小値を答えとする。
- 追加位置が末尾の場合、全体が単調増加になるため、門松列は作れない。
※この場合のみ実際に要素を追加し、以下のつのケースでは要素を追加しない。単調増加列以外の要素は最適な門松列構築の邪魔になるだけのため。 - 追加位置が先頭の場合、追加要素を、既存要素の先頭つをとした下に凸の門松列が最適。
- 追加位置が先頭と末尾以外の場合、先頭要素を、追加要素を、追加要素が挿入される位置の次の要素をとした上に凸の門松列が最適。
- 追加位置が末尾の場合、全体が単調増加になるため、門松列は作れない。
具体例
入力値:「」とする。
- ・・・を追加するまでは解なし。
- ・・・を追加すると、上記3.のパターンにより、が作られる。※は追加せずに捨てる。
- ・・・を追加すると、上記2.のパターンにより、が作られる。※は追加せずに捨てる。
- ・・・を追加すると、上記2.のパターンにより、が作られる。※は追加せずに捨てる。
- これらの最小値のが答え。
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); } } }