第二回 アルゴリズム実技検定

はじめに

プログラミング関連では初めて記事を書きます。ks2mです。
2019年1月にAtCoderを始め、緑色最下層くらいから徐々にレートを上げて現在青色。
黄色以上の人の記事と比べ、解法の正当性やコードの簡潔さなど劣ると思いますが、解いたときの実際の思考過程も踏まえつつ、飛躍し過ぎない内容が書ければいいなと思っています。
ソースコードの言語はJavaです。

A - エレベーター

問題
どうするのが一番楽なのかちょっと悩んだが、時間をかけすぎても仕方ないので適当にやった。
一番楽な方法がぱっと出てくるようにしたい。。

問題概要

B9, B8, ... , B1, 1F, 2F, ... , 9Fの18のフロアを持つ建物がある。
この18フロアの内、異なる2つのフロアを表す文字列とが与えられるので、その距離を出力せよ。

考察

1. とをそれぞれ数値化して差を取りたいと思う。
2. しかし、数値部分が1文字目だったり2文字目だったりで、条件分岐しつつ数値化するのはなんかめんどくさそう？
3. べた書き過ぎて嫌だが、"B9"～"9F"をその順に持った文字列の配列を作り、一致するインデックスを取得した。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        sc.close();

        String[] a = {
                "B9",
                "B8",
                "B7",
                "B6",
                "B5",
                "B4",
                "B3",
                "B2",
                "B1",
                "1F",
                "2F",
                "3F",
                "4F",
                "5F",
                "6F",
                "7F",
                "8F",
                "9F",
                };

        int si = 0;
        int ti = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i].equals(s)) {
                si = i;
            }
            if (a[i].equals(t)) {
                ti = i;
            }
        }
        System.out.println(Math.abs(si - ti));
    }
}

考察２

後からよく考えたら、数値化するのそんなに大変でもなかった。

1. "B"→"-"、"F"→空文字に置換すると、数値変換可能になる。
2. B1（-1）と1F（1）の間が2になるので、マイナスの場合+1するか、プラスの場合-1する。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        sc.close();

        int si = toInt(s);
        int ti = toInt(t);
        System.out.println(Math.abs(si - ti));
    }

    static int toInt(String s) {
        s = s.replaceAll("B", "-").replaceAll("F", "");
        int ret = Integer.parseInt(s);
        if (ret < 0) {
            ret++;
        }
        return ret;
    }
}

B - 多数決

問題
これはさすがにやるだけと言ってもいいかな。

問題概要

'a', 'b', 'c'からなる文字列が与えられる。
最も多く含まれる文字は3つの内どれかを出力せよ。

• 
• 最多の文字は1種類

考察

1. それぞれの文字をカウントする。これは'a'を引けば0～2になるので、カウントの格納先は変数3つより長さ3の配列の方が楽そう。
2. 3つの数値を比較し、最大数に対応する文字を出力する。こちらは文字種がもっと多ければfor文を使うが、3つ程度であれば汚いけどif文並べた方が早いと思った。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();

        int[] cnt = new int[3];
        for (int i = 0; i < s.length; i++) {
            cnt[s[i] - 'a']++;
        }

        char ans = 'a';
        int max = cnt[0];
        if (max < cnt[1]) {
            ans = 'b';
            max = cnt[1];
        }
        if (max < cnt[2]) {
            ans = 'c';
        }
        System.out.println(ans);
    }
}

C - 山崩し

問題
なんか一気に難しくなった気がする。まず問題文が長くて辛い。
しかし問題を把握すれば書いてある通りにやるだけなので、ある意味第一回のC（3番目）と比べてやり方を考える必要はない？

問題概要

縦、横のマス目の中に、1つ以上の 'X' を含む山型の '#' がある。
以下のように、下から順に、初期状態が '#' の箇所について、左下、真下、右下のいずれかが 'X' ならば 'X' に塗り替えていった後の状態を出力せよ。

....#....　　 　　....X....
...###...　　 　　...XXX...
..#####..　　→　　..XXXXX..
.####X##.　　 　　.XX##X##.
#X#######　　 　　#X#######

• 

考察

1. 入出力例がそのように見えたので、「各 'X' の左上、真上、右上を 'X' に塗り替える」といつの間にか読み替えていた。
2. 下の段から順に、マスが'X'ならば、マス～を'X'にする。
3. ただし、書き換えるマスが配列内かつ '#' であること。

※後から思えば、余計な読み替えをしなければ配列外参照に気を遣う必要はなかった。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] s = new char[n][];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        // N段目～2段目の'X'を探す
        for (int i = n - 1; i > 0; i--) {
            for (int j = 0; j < s[i].length; j++) {
                if (s[i][j] == 'X') {
                    // 元が'X'の箇所の上3箇所（配列外参照対策込み）
                    for (int j2 = Math.max(0, j - 1); j2 < Math.min(s[i].length, j + 2); j2++) {
                        if (s[i - 1][j2] == '#') {
                            s[i - 1][j2] = 'X';
                        }
                    }
                }
            }
        }
        // 結果出力
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < s[i].length; j++) {
                System.out.print(s[i][j]);
            }
            System.out.println();
        }
    }
}

D - パターンマッチ

問題
やっぱり前回のD問題よりかなり大変。

問題概要

英小文字からなる文字列が与えられる。
英小文字または '.'からなる長さ1～3の文字列全てのうち、の連続する部分文字列であるものの個数を求めよ。（'.' は任意の1文字に相当）

• 

考察

1. 全ての文字列を実際に作って条件を満たすか試す。
2. 文字列の数がくらい（もう少し多いけど）、それぞれの判定にくらい。計算量は大丈夫そう。
3. 実装を三重ループにするか再帰にするか。まあたかだか3回なら三重ループでいいかと思った。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();

        int ans = 0;
        char[] t = new char[3];
        for (int i = 0; i < 27; i++) {
            if (i < 26) {
                t[0] = (char) ('a' + i);
            } else {
                t[0] = '.';
            }
            if (isOk(s, t, 1)) {
                ans++;
            }
            for (int i2 = 0; i2 < 27; i2++) {
                if (i2 < 26) {
                    t[1] = (char) ('a' + i2);
                } else {
                    t[1] = '.';
                }
                if (isOk(s, t, 2)) {
                    ans++;
                }
                for (int i3 = 0; i3 < 27; i3++) {
                    if (i3 < 26) {
                        t[2] = (char) ('a' + i3);
                    } else {
                        t[2] = '.';
                    }
                    if (isOk(s, t, 3)) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }

    static boolean isOk(char[] s, char[] t, int k) {
        label:
        for (int i = 0; i <= s.length - k; i++) {
            for (int j = 0; j < k; j++) {
                if (t[j] != '.' && s[i + j] != t[j]) {
                    continue label;
                }
            }
            return true;
        }
        return false;
    }
}

さすがにちょっとひどいので再帰版も。

import java.util.Scanner;

public class Main {
    static int ans = 0;
    static char[] s;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        s = sc.next().toCharArray();
        sc.close();

        dfs(new char[3], 0);
        System.out.println(ans);
    }

    static void dfs(char[] t, int idx) {
        if (idx == 3) {
            return;
        }
        for (int i = 0; i < 27; i++) {
            if (i < 26) {
                t[idx] = (char) ('a' + i);
            } else {
                t[idx] = '.';
            }
            if (isOk(s, t, idx + 1)) {
                ans++;
            }
            dfs(t, idx + 1);
        }
    }

    static boolean isOk(char[] s, char[] t, int k) {
        // 三重ループ版と同内容
    }
}

E - 順列

問題
CやDより簡単では。

問題文（原文のまま）

の順列が与えられます。
各整数に対して、次の条件を満たす以上の整数として考えられる最小の値を求めてください。

• とする。をで置き換えるという操作をちょうど回行った後、となる。

• 
• 
• 
• 入力は全て整数

考察

1. とりあえずそのままやることを考える。
2. で初期化する。
3. の間、にを代入し続け、ループ回数をカウントする。
4. 0回になってしまうので、do-while文に変更して1回以上回るようにした。初期値をとし、カウント1からスタートしてもよかった。
5. スペース区切りは末尾に余計なスペースが付かないようにするのが面倒。余計なスペースがあっても改行区切りでも通るのかもしれないけど、一応ちゃんとやった。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt() - 1;
        }
        sc.close();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int j = 0;
            int x = i;
            do {
                x = a[x];
                j++;
            } while (x != i);
            sb.append(j).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

考察２

解説PDFの最後の2行について。
例えば例１の場合、「1→1→・・・」「2→3→2→3→・・・」「4→5→6→4→5→6→・・・」のようにグループごとに一定周期でループするので、同じグループ内の値は同一周期（同一回数）となる。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt() - 1;
        }
        sc.close();

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (ans[i] == 0) {
                int j = 0;
                int x = i;
                do {
                    x = a[x];
                    j++;
                } while (x != i);

                do {
                    x = a[x];
                    ans[x] = j;
                } while (x != i);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(ans[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

程度では実行時間全然変わらず。

F - タスクの消化

問題
誤読というか勘違いして時間かかってしまった。
茶色の半分以上が解けたらしいけど、非AtCoderユーザで初級以上は9/71人しかいないし、やっぱり難しめ？
というか、自分の場合はQueue系のコレクションは競プロ以外でほとんど使ったことなかったし、同じように馴染みのない人が多かったのかも？

問題概要

個のタスクがある。個目のタスクは日目以降に消化することができ、消化することでポイントを得られる。
1日目から日目まで、毎日1つずつタスクを消化するとき、の全ての整数に対して、日目までに得られるポイントの合計の最大値を求めよ。

• 
• 
• 
• 入力は全て整数
• 日目までに実行可能なタスクは個以上存在する

考察

1. 日付順に消化可能キューに追加していくことになるので、とをセットにした上で、の昇順にソートする。
2. 日目の処理としては、の要素を全部消化可能キューに追加した上、の降順に個取り出した合計を出力する？　→日目のタスクが複数選ばれるのは駄目だった。にならないように無駄に苦労して実装したけどWA。
3. 日目の処理としては、の要素を新たに消化可能キューに追加し、キューからが最大のものを1つ取り出し、これまでの合計に足すだけでよかった。
4. 制約が20万なので入出力を高速化。*1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;

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());
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[0]);
            o.b = Integer.parseInt(sa[1]);
            arr[i] = o;
        }
        br.close();

        // aの昇順でソート
        Arrays.sort(arr, (o1, o2) -> o1.a - o2.a);

        // 降順に取り出す優先度付きキュー
        PriorityQueue<Integer> que = new PriorityQueue<>((o1, o2) -> o2 - o1);

        int ans = 0;
        int idx = 0;
        PrintWriter pw = new PrintWriter(System.out);
        for (int k = 1; k <= n; k++) {
            // k日目のタスクを追加
            while (idx < n && arr[idx].a <= k) {
                que.add(arr[idx].b);
                idx++;
            }
            // 最大のものを1つ取り出し
            ans += que.poll();
            pw.println(ans);
        }
        pw.flush();
    }

    static class Obj {
        int a, b;
    }
}

G - ストリング・クエリ

問題
連続してキューを使用する問題。F問題と違って前から順に処理すればいいが多少の計算が必要。

問題概要

初め空文字列である文字列に対して回の操作を行う。
回目の操作の種類をとし、内容は以下の通り。

• のとき
  • の末尾に英小文字を文字追加する。
• のとき
  • の先頭から文字削除する。
  • この操作で削除された'a' ～ 'z'の各文字数の2乗の和を出力する。

• 
• 
• または
• は英小文字、それ以外は整数
• の操作が1つ以上存在する

考察

1. を個連結した文字列を実際に作るのは、になるので駄目。
2. の場合はとりあえずそのままの情報をキューに追加。
3. の場合、キュー先頭のとの大小関係を気にしながら頑張って計算したい。
4. ならキューの先頭を削除、なら先頭を残したまま処理終了するのを上手いことやる。
5. ついでに文字種ごとにカウントもしておき、2乗の和を計算する。の2乗はintの範囲を超えるので注意。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine());
        Queue<Obj> que = new ArrayDeque<>();
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            if (sa[0].equals("1")) {
                Obj o = new Obj();
                o.c = sa[1].charAt(0) - 'a';
                o.x = Integer.parseInt(sa[2]);
                que.add(o);
            } else {
                int d = Integer.parseInt(sa[1]);
                long[] cnt = new long[26];
                while (d > 0 && !que.isEmpty()) {
                    Obj o = que.peek();
                    int del = Math.min(d, o.x);
                    cnt[o.c] += del;
                    d -= del;
                    o.x -= del;
                    if (o.x <= 0) {
                        que.poll();
                    }
                }
                long ans = 0;
                for (int j = 0; j < cnt.length; j++) {
                    ans += cnt[j] * cnt[j];
                }
                pw.println(ans);
            }
        }
        pw.flush();
        br.close();
    }

    static class Obj {
        int c, x;
    }
}

H - 1-9 Grid

問題
例１を見るまで問題文が何言っているのかよくわからなかった。
「S123456789123456789G」のような順に通る必要があるのか？とか思ったりしてた。
それはさておき、G問題とI問題が中級レベルとしてはやるだけだったので、この問題が中級の門番だったと思う。

問題概要

縦マス、横マスのマス目があり、各マスには 'S'、'G'、'1'～'9' のいずれかが書かれている。
「S-1-2-3-4-5-6-7-8-9-G」（"-"は任意の0マス以上）のように、1～9を順に経由してSからGまで移動するときの最小の移動回数を求めよ。
そのような経路が存在しない場合はを出力せよ。
上下左右の4方向に移動可能。

考察

1. S→1のどこか→2のどこか→・・・→9のどこか→G の順に移動することになる。
2. S→一番近い1→一番近い2→・・・のように貪欲に移動すると、Sには近くても2から遠ざかるような1に行くと駄目そう。つまり、どの1を経由すればいいかすら、ゴールしないとわからない。
3. 各2のマスへの最短距離を求めるには、全ての1→2の組み合わせを調べて最小を取るとよさそう。とりあえず、1つ前の数字より前は見る必要がない。
4. 行列目のマスまでの最短距離　として、数字の小さい順に埋めていく。
5. 遷移は、「1つ前の数字が書かれた各マスの最短距離そのマスからマスまでの距離」の最小値。
6. 計算量はざっくり、数字が変わるのが回 遷移先マスの探索が 遷移元マスの探索が で数千万くらいになりそうな気もするけど、if文の中に入る回数はだいぶ少ないし、とりあえず投げてみよう。　→128msで余裕だった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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]);
    char[][] a = new char[n][m];
    for (int i = 0; i < n; i++) {
      a[i] = br.readLine().toCharArray();
    }
    br.close();

    int[][] dp = new int[n][m];
    for (int i = 0; i < n; i++) {
      Arrays.fill(dp[i], 100000000);
    }

    char[] c = {'S', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'G'};
    for (int k = 0; k < c.length; k++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          // 遷移先マスの数字がc[k]の場合
          if (a[i][j] == c[k]) {
            if (k == 0) {
              dp[i][j] = 0; // Sのマス
            } else {
              for (int i2 = 0; i2 < n; i2++) {
                for (int j2 = 0; j2 < m; j2++) {
                  // 遷移元マスの数字はc[k - 1]
                  if (a[i2][j2] == c[k - 1]) {
                    int alt = dp[i2][j2] + Math.abs(i - i2) + Math.abs(j - j2);
                    dp[i][j] = Math.min(dp[i][j], alt);
                  }
                }
              }
              if (c[k] == 'G') {
                if (dp[i][j] == 100000000) {
                  System.out.println(-1);
                } else {
                  System.out.println(dp[i][j]);
                }
                return;
              }
            }
          }
        }
      }
    }
  }
}

I - トーナメント

問題
ただ愚直にシミュレーションするだけ。本当にそれでいいのか一瞬疑った。
前回と比べて、初級までは難しくなったと思ったけど、中級は随分簡単になったのでは。

問題概要

人人が番号順に一列に並んでおり、番号の若い順に2人ずつペアになって戦うトーナメントを行う。
人の強さはであり、値が大きい方が勝つ。2回戦以降も勝者を番号順に並べて同様。
それぞれの人が何回戦まで残るかを求めよ。

• 
• 
• の要素は相異なる

考察

1. 全員をリストに入れる。
2. 奇数番目と偶数番目を比べ、弱い方を取り除いてその際何回戦かを記録する。
3. リスト上でエレメントを取り除くと、前の方を取り除いたときに要素数分の時間がかかってしまうので、回戦ごとに新しいリストに強い方を追加していく。
4. リストに追加する回数が、回戦ごとに半分になっていく。トータルで回なので間に合う。
5. 優勝者についても忘れずに設定する。（サンプル試してになって気が付いた）

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

        int[] ans = new int[n2];
        List<Integer> list = new ArrayList<>(n2);
        for (int i = 0; i < n2; i++) {
            list.add(i);
        }
        int cnt = 1;
        while (list.size() > 1) {
            List<Integer> work = new ArrayList<>(); // 勝者リスト
            for (int i = 0; i < list.size(); i+=2) {
                if (a[list.get(i)] > a[list.get(i + 1)]) {
                    work.add(list.get(i)); // 勝った方は勝者リストへ
                    ans[list.get(i + 1)] = cnt; // 負けた方は何回戦かを記録
                } else {
                    work.add(list.get(i + 1)); // 勝った方は勝者リストへ
                    ans[list.get(i)] = cnt; // 負けた方は何回戦かを記録
                }
            }
            list = work;
            cnt++;
        }
        ans[list.get(0)] = cnt - 1; // 優勝者
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n2; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }
}

J - 文字列解析

問題
これも知識はほとんどいらない実装メインの問題。
H問題を飛ばしてこれをやった方が中級取れそう。

問題概要

英小文字、'('、')'からなる文字列が与えられる。
「(abc)」→「abccba」のように、括弧部分を、そのままの文字列と反転した文字列の連結に置き換えたときの最終的な文字列を出力せよ。

• 
• は1文字以上の英小文字を含む
• 内の括弧の対応は取れている（括弧がない場合、入れ子になっている場合、中身が空の場合あり）
• 最終的な文字列の長さ

考察

1. 制約があまり大きくないので、普通にやればよさそう。
2. 前から見ていき、括弧以外はそのまま連結する。*2
3. 開き括弧に当たった場合、後々の反転のことを考えたら、括弧内だけの文字列を別に持っておきたい。
4. 編集中の文字列をスタック*3に退避し、新しい編集用文字列を用意。
5. 閉じ括弧の場合、編集中文字列＋反転文字列の処理を行い、スタックに退避していた文字列に連結する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        br.close();

        StringBuilder sb = new StringBuilder();
        Deque<StringBuilder> que = new ArrayDeque<>();
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '(') {
                que.push(sb);
                sb = new StringBuilder();
            } else if (s[i] == ')') {
                // 括弧内の文字列
                StringBuilder sb2 = sb;
                // 複製して反転
                StringBuilder sb3 = new StringBuilder(sb2);
                sb3.reverse();

                sb = que.pop();
                sb.append(sb2).append(sb3);
            } else {
                sb.append(s[i]);
            }
        }
        System.out.println(sb.toString());
    }
}

K - 括弧

問題
そろそろ本格的に難易度が上がってきた。
ここまでの難問はDPに偏っているような？

問題概要

'(' と ')' からなる長さの文字列が与えられる。
以下の操作を回以上好きなだけ行い、を括弧の対応が取れた文字列にするときの合計コストの最小値を求めよ。

• （の文字目）を逆の文字に変更する。コストは。
• を削除する。コストは。

• 
• 
• は整数

考察

1. とりあえず最悪の合計で達成できる。
2. 例１を見ると、1文字目が ')' だと操作必須だが、変更と削除どちらが最適かは全くわからない。貪欲はない。
3. '(' を+1、')' を-1とすると、途中で負になってはならず、最後に0になっている必要がある。
4. 文字目まで見て、'(' が文字多い状態での最小コスト　で遷移が書けるか？
5. 文字目が '(' の場合、そのままならへ、変更するならへ、削除するならへの遷移が書ける。 ')' なら逆。
6. は、前半開いて後半閉じることを考えたら、程度で十分。くらいなので間に合う。
7. 一応、となる部分は不可能なので見る必要ない。
8. DPの初期値は適当により多めに。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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());
        char[] s = br.readLine().toCharArray();

        String[] sa = br.readLine().split(" ");
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(sa[i]);
        }

        sa = br.readLine().split(" ");
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long[][] dp = new long[n + 1][1502]; // n/2 + 配列外参照回避分くらい
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(dp[i], 1000000000000000L);
        }
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            int lim = Math.min(i, 1500);
            if (s[i] == '(') {
                for (int j = 0; j <= lim; j++) {
                    // そのまま
                    dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j]);
                    // 削除
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + d[i]);
                    // 変更
                    if (j > 0) {
                        dp[i + 1][j - 1] = Math.min(dp[i + 1][j - 1], dp[i][j] + c[i]);
                    }
                }
            } else {
                for (int j = 0; j <= lim; j++) {
                    // そのまま
                    if (j > 0) {
                        dp[i + 1][j - 1] = Math.min(dp[i + 1][j - 1], dp[i][j]);
                    }
                    // 削除
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + d[i]);
                    // 変更
                    dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], dp[i][j] + c[i]);
                }
            }
        }
        System.out.println(dp[n][0]);
    }
}

L - 辞書順最小

問題
ABC146-F（Sugoroku）っぽさを感じたりしていた。
今回はこの問題で初めてライブラリ貼った。
前回より1時間以上早い2時間45分ほどで上級達成。

問題概要

長さの整数列から、個の要素を以上の間隔で抜き出し、元の順序のまま新しい数列を作る。
この操作で作れる数列の内、辞書順最小であるものを求めよ。
そのような操作が不可能な場合はを出力せよ。

• 
• 
• 
• 入力は全て整数

考察

1. 文字目に選べる右端のインデックスは、文字目の右端は、・・・と後ろから順にずつ減らしていくと、1文字目に選べる範囲がわかる。
2. この時点で右端が0未満なら。
3. あとは、～右端インデックスリスト の範囲の最小値（複数あれば一番左のもの）、前回選択インデックス～右端リスト の範囲の最小値、・・・と貪欲に選択していく。
4. ただし、最小値の探索にかけられるオーダーがくらい。
5. 区間の最小値と言えば、セグメント木を使う？　F問題のようにPriorityQueueで簡単にできないか？
6. PriorityQueueだと、右の方の追加は簡単だが、左の方の使えなくなったものを削除する方法がぱっとわからなかったので、悩むくらいならセグ木を使うことにした。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.function.BiFunction;

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

        // 右端インデックスリスト
        List<Integer> list = new ArrayList<>();
        int idx = n - 1;
        list.add(idx);
        for (int i = 0; i < k - 1; i++) {
            idx -= d;
            if (idx < 0) {
                break;
            }
            list.add(idx);
        }
        if (list.size() < k) {
            System.out.println(-1);
            return;
        }
        // 後ろから入れているので逆順にする
        Collections.reverse(list);

        Obj na = new Obj();
        na.i = -1;
        na.a = Integer.MAX_VALUE;
        SegTree<Obj> st = new SegTree<>(n, na, (o1, o2) -> {
            // Aが小さい方、同じならindexが小さい方を複製して返す
            Obj o = new Obj();
            Obj src = null;
            if (o1.a < o2.a) {
                src = o1;
            } else if (o1.a > o2.a) {
                src = o2;
            } else {
                if (o1.i < o2.i) {
                    src = o1;
                } else {
                    src = o2;
                }
            }
            o.i = src.i;
            o.a = src.a;
            return o;
        });
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;
            o.a = a[i];
            st.update(i, o);
        }

        StringBuilder sb = new StringBuilder();
        idx = 0;
        for (int i = 0; i < k; i++) {
            // 選択可能区間内の最小値取得
            Obj min = st.query(idx, list.get(i) + 1);
            sb.append(min.a).append(' ');
            idx = min.i + d;
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static class Obj {
        int i, a;
    }

    // 以下ライブラリ

    static class SegTree<T> {
        int n = 2;
        int n2;
        T NA;
        List<T> list;
        BiFunction<T, T, T> func;

        public SegTree(int num, T na, BiFunction<T, T, T> func) {
            while (n < num) n <<= 1;
            n2 = n * 2 - 1;
            NA = na;
            list = new ArrayList<T>(n2);
            for (int i = 0; i < n2; i++) list.add(NA);
            this.func = func;
        }

        void update(int i, T x) {
            i += n - 1;
            list.set(i, x);
            while (i > 0) {
                i = (i - 1) / 2;
                list.set(i, func.apply(list.get(i * 2 + 1), list.get(i * 2 + 2)));
            }
        }

        T query(int l, int r) {
            return query(l, r, 0, 0, n);
        }

        private T query(int l, int r, int k, int beg, int end) {
            if (end <= l || r <= beg) return NA;
            if (l <= beg && end <= r) return list.get(k);
            T v1 = query(l, r, k * 2 + 1, beg, (beg + end) / 2);
            T v2 = query(l, r, k * 2 + 2, (beg + end) / 2, end);
            return func.apply(v1, v2);
        }
    }
}

考察２

後でよく考えたら、PriorityQueueでもできた。1つ選択するごとに使用不可になったものを全部捨てようとするのではなく、次の最小値を得る際に、インデックスが使用可能な左端より小さいものを捨て続けるだけだった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws Exception {

        // 省略

        if (list.size() < k) {
            System.out.println(-1);
            return;
        }

        // ここまでセグ木解と同じ

        list.add(-1); // 番兵
        Collections.reverse(list);

        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> {
            // Aの昇順、同じならindexの昇順
            if (o1.a != o2.a) {
                return o1.a - o2.a;
            }
            return o1.i - o2.i;
        });

        StringBuilder sb = new StringBuilder();
        idx = 0;
        for (int i = 1; i <= k; i++) {
            for (int j = list.get(i - 1) + 1; j <= list.get(i); j++) {
                que.add(arr[j]);
            }
            // 選択可能範囲のものが見つかるまで捨てる
            while (true) {
                Obj o = que.poll();
                if (o.i >= idx) {
                    sb.append(o.a).append(' ');
                    idx = o.i + d;
                    break;
                }
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static class Obj {
        int i, a;
    }
}

M - 食堂

問題
15分くらい考えてみたが解けなかったので飛ばし。
最初に好みの料理を食べるまでと、最後に好みの料理を食べた後を単純にシミュレーションするだけで計算量オーバーのような気がして（実際どうかは不明）諦めた。
解説PDFも未解読。

N - ビルの建設

問題
1時間くらいかかったが、ラスト3問の中では唯一時間内に解けた。結果88点。

問題概要

2次元平面上に、各辺がx, y軸に平行な正方形が個ある。
番目の正方形は、左下の頂点が、1辺の長さが、コストが。
個の点それぞれについて、点を含む（または境界線上に持つ）正方形のコストの和を求めよ。

• 
• 
• 
• 
• 
• 入力は全て整数

考察

1. 少なくともは必ず全体のオーダーに関わる。1クエリ当たりくらいで求まる必要がある。
2. が比較的小さい。座標圧縮して二次元累積和を取れば、クエリはになるが、累積和部分がで無理そう。
3. 二次元累積和をしても、正方形ともクエリとも関係ない無駄な部分だらけになりそう。関係ある部分だけの情報を持てないか？
4. xでソートしてx座標の小さい方から見ていき、正方形の境界部分でy座標の情報更新しながら、x座標が対象範囲に含まれるクエリに答えていくことを考える。
5. x座標を固定したときのy座標に注目すると数直線のようになり、BITを使って各正方形の下端に、上端にを加算した上でまでの和を取得することで、コストの和を取得できる。
6. のデータは持てないので、yについて座標圧縮する。これでBITのサイズが程度に収まる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

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 q = Integer.parseInt(sa[1]);

        // キー：正方形の境界線のx座標（左右両側）、値：対応する正方形のリスト
        TreeMap<Integer, List<Toti>> map = new TreeMap<>();
        // キー：正方形の境界線のy座標（上下両側）、値：座標圧縮後の値
        TreeMap<Integer, Integer> zy = new TreeMap<>();
        zy.put(Integer.MIN_VALUE, null); // 番兵

        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Toti o = new Toti();
            o.x = Integer.parseInt(sa[0]);
            o.y = Integer.parseInt(sa[1]);
            o.d = Integer.parseInt(sa[2]) + 1; // 半開区間とする
            o.c = Integer.parseInt(sa[3]);
            zy.put(o.y, null);
            zy.put(o.y + o.d, null);
            List<Toti> list = map.get(o.x);
            if (list == null) {
                list = new ArrayList<>();
                map.put(o.x, list);
            }
            list.add(o);
            list = map.get(o.x + o.d);
            if (list == null) {
                list = new ArrayList<>();
                map.put(o.x + o.d, list);
            }
            list.add(o);
        }
        map.put(Integer.MAX_VALUE, new ArrayList<>(0)); // 番兵

        Query[] qs = new Query[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            Query qu = new Query();
            qu.i = i;
            qu.a = Integer.parseInt(sa[0]);
            qu.b = Integer.parseInt(sa[1]);
            qs[i] = qu;
        }
        br.close();

        // 座標圧縮
        Integer[] tmp = zy.keySet().toArray(new Integer[0]);
        int cnt = 0;
        for (Integer i : tmp) {
            cnt++;
            zy.put(i, cnt);
        }

        // x座標の昇順でソート
        Arrays.sort(qs, (o1, o2) -> o1.a - o2.a);

        BIT bit = new BIT(100001); // 2N以上確保
        int idx = 0;
        // x座標の境界分ループ
        for (int key : map.keySet()) {
            // 正方形の前回の境界 ≦ A ＜ 今回の境界 のクエリに答える
            while (idx < q && qs[idx].a < key) {
                qs[idx].ans = bit.sum(zy.floorEntry(qs[idx].b).getValue());
                idx++;
            }
            // 境界に対応する正方形のコストをBITに反映
            List<Toti> list = map.get(key);
            for (Toti o : list) {
                if (o.x == key) {
                    // これから敷地内に入る正方形分を加算
                    bit.add(zy.get(o.y), o.c);
                    bit.add(zy.get(o.y + o.d), -o.c);
                } else {
                    // 敷地から抜ける正方形分を減算
                    bit.add(zy.get(o.y), -o.c);
                    bit.add(zy.get(o.y + o.d), o.c);
                }
            }
        }

        // クエリをインデックス順にソートし直して結果出力
        Arrays.sort(qs, (o1, o2) -> o1.i - o2.i);
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            pw.println(qs[i].ans);
        }
        pw.flush();
    }

    static class Toti {
        int x, y, d, c;
    }

    static class Query {
        int i, a, b;
        long ans;
    }

    // 以下ライブラリ

    static class BIT {
        int n;
        long[] arr;

        public BIT(int n) {
            this.n = n;
            arr = new long[n + 1];
        }

        void add(int idx, long val) {
            for (int i = idx; i <= n; i += i & -i) {
                arr[i] += val;
            }
        }

        long sum(int idx) {
            long sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += arr[i];
            }
            return sum;
        }
    }
}

O - 可変全域木

問題
解説PDFのLCA解がわかってはいたが、ダブリングで実装をしたことがなく、一からやっていたら30～40分かけても終わらず、時間切れ。
次回までにはライブラリ整備しておいて、エキスパートを狙いたい。

問題概要

頂点辺の重みつき単純連結無向グラフが与えられる。
辺は頂点とを結び、重みは。
辺～のそれぞれの辺について、その辺を含む最小の重みの全域木の重みを求めよ。

• 
• 
• 

考察

1. とりあえずクラスカル法で最小全域木を求める。
2. 上記に含まれる辺は、それが答え。
3. その他の（とを結ぶ）辺を1つ足してみると、最小全域木上でのパス内で最大の重みをもつ辺を代わりに抜けばよいことがわかる。
4. そのような辺をどうやって求めるか？　LCA絡みの何かをすれば、とLCA間、LCAと間の最大をそれぞれ求めて、両者の最大を取れた気がする。
5. そのものずばり、もしくはちょっと改変するくらいで使えるライブラリがほしかった。

一応後でACは取れたのだが、ソースは無駄に長いと思うので一旦省略。
その内整備できたら追加するかもしれません。

初記事なのに随分長くなってしまいました。

*1:ScannerやSystem.out.println()だと、十万単位の行数を入出力するとそれだけで1秒近くかかってしまったりするので、比較的お手軽に何割かは速くなるBufferedReaderやPrintWriterを使うようにしている。それ以上の高速化までは知らない。

*2:Stringで扱うと、連結の度に新規オブジェクトが生成され、MLEになる恐れがあるので、StringBuilderを使う。

*3:便宜上スタックと呼ぶが、JavaのStackは古く、Dequeが上位互換のようなので、実際はDequeを使っている。