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

先に結果を書くと、残り5分くらいで14問目が解けた、ぎりぎりの94点エキスパートでした。

途中経過

• エントリー確定タイム・・・17分15秒
• 初級確定タイム・・・42分44秒
• 中級確定タイム・・・1時間41分48秒
• 上級確定タイム・・・2時間54分02秒
• エキスパート確定タイム・・・4時間54分31秒

A - ケース・センシティブ

問題
第二回はめんどくさかったけど、今回は普通に実装も楽な1問目だった。

問題概要

長さの英大文字・英小文字のみからなく文字列が与えられる。
が大文字・小文字も含めて一致するなら 'same' を、
大文字と小文字の違いだけなら 'case-insensitive' を、
以上に該当しないなら 'different' を出力せよ。

思考過程

1. 完全一致はequalsで判定する。
2. falseなら、全て大文字か小文字に寄せてからequalsで判定する。

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

        if (s.equals(t)) {
            System.out.println("same");
        } else if (s.toLowerCase().equals(t.toLowerCase())) {
            System.out.println("case-insensitive");
        } else {
            System.out.println("different");
        }
    }
}

B - ダイナミック・スコアリング

問題
yukicoderの得点のようなイメージがなかなか頭を離れなかったせいか、問題を理解するのに多分10分近くかかってしまい、非常に嫌な気持ちになった。
しかもエントリー向けなのに、解き方によってはとかでTLEしそうな制約でいいのだろうか？

問題概要

参加者が、問題数が個のプログラミングコンテストがある。
参加者のスコアは、解いた問題の得点の合計。
各問題のスコアは、(クエリ時点でこの問題を解いている人数)。
以下のいずれかの形式で与えられる個のクエリを順番に処理せよ。

• '1 n'：参加者の現在のスコアを出力せよ。
• '2 n m'：参加者が問題を解いた。

• 
• 
• どの参加者も同じ問題を複数回解くことはない

思考過程

1. 各問題について、何人が解いたかの情報を持っておく。
2. 各参加者について、現在のスコアを持っておき、クエリ１なら出力するだけ、クエリ２なら解いた人に現時点でのスコアを加算する？　→そういう題意ではない。これだと問題が解かれる度に、既に解いている人のスコアを下げる必要が生じる。
3. クエリ２では、参加者が問題を解いたフラグを立て、問題のスコアを下げる。
4. クエリ１では、参加者について解いている問題のスコアを合計する。
5. フラグ情報が空間計算量、クエリ処理が時間計算量で間に合う。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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]);
        int Q = Integer.parseInt(sa[2]);

        // 各問題のスコア
        int[] score = new int[M];
        Arrays.fill(score, N);
        // 参加者nが問題mをACした情報
        boolean[][] ac = new boolean[N][M];

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < Q; i++) {
            sa = br.readLine().split(" ");
            int n = Integer.parseInt(sa[1]) - 1;
            if ("1".equals(sa[0])) {
                int ans = 0;
                for (int m = 0; m < M; m++) {
                    if (ac[n][m]) {
                        ans += score[m];
                    }
                }
                pw.println(ans);
            } else {
                int m = Integer.parseInt(sa[2]) - 1;
                ac[n][m] = true;
                score[m]--;
            }
        }
        br.close();
        pw.flush();
    }
}

C - 等比数列

問題
一見数学的な見た目をしているが、だいたいやるだけ。

問題概要

初項、公比の等比数列の第項がより大きければ 'large' を、そうでなければ計算結果を出力せよ。

• 入力は全て整数
• 

思考過程

1. ならば、を超えるまで倍していっても回以内の計算で終わる。
2. を掛けて以下から回でいきなりlongの範囲を超えることはない。
3. の場合は回掛け算してしまうとTLEなので、そのままを出力する。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextInt();
        long r = sc.nextInt();
        long n = sc.nextInt();
        sc.close();

        if (r == 1) {
            System.out.println(a);
            return;
        }

        for (int i = 2; i <= n; i++) {
            a *= r;
            if (a > 1000000000) {
                System.out.println("large");
                return;
            }
        }
        System.out.println(a);
    }
}

なお、本番時の提出コードでは、思考過程3.の場合分けが抜けた状態でも875msで通ってしまっていた。（上記掲載のコードなら111ms）
エントリーレベルならまあ通ってもいいかという気もしないではないけど。

D - 電光掲示板

問題
ちゃんと実装メインの初級らしい問題かな。添字がややこしくなりそう。

問題概要

桁の数字列を表示する電光掲示板がある。
'#' が表している数字列を出力せよ。

• 
• 入力の～行目は、'#'、'.' のみからなる長さの文字列
• ～行目の文字目は '.'
• 各数字の表し方は以下の入力例の通り。

入力例

10
.###..#..###.###.#.#.###.###.###.###.###.
.#.#.##....#...#.#.#.#...#.....#.#.#.#.#.
.#.#..#..###.###.###.###.###...#.###.###.
.#.#..#..#.....#...#...#.#.#...#.#.#...#.
.###.###.###.###...#.###.###...#.###.###.

出力例

0123456789

思考過程

1. の塊ごとに、どの数字と一致しているか調べていく。
2. 例えば、中央一番上が '.' ならのように、簡単にどの数字かわかるようなマスがないかと思うが、ぱっと見共通部分が多く、ミスがあっても嫌なので、ちゃんとマス全部調べることにする。
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[5][];
        for (int i = 0; i < 5; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        char[][] x = new char[5][];
        x[0] = ".###..#..###.###.#.#.###.###.###.###.###.".toCharArray();
        x[1] = ".#.#.##....#...#.#.#.#...#.....#.#.#.#.#.".toCharArray();
        x[2] = ".#.#..#..###.###.###.###.###...#.###.###.".toCharArray();
        x[3] = ".#.#..#..#.....#...#...#.#.#...#.#.#...#.".toCharArray();
        x[4] = ".###.###.###.###...#.###.###...#.###.###.".toCharArray();

        label1:
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                boolean flg = true;
                label2:
                // 入力のi文字目と比較用のj文字目が5×3マス全て一致するか判定
                for (int a = 0; a < 5; a++) {
                    for (int b = 0; b < 3; b++) {
                        if (s[a][4 * i + 1 + b] != x[a][4 * j + 1 + b]) {
                            flg = false;
                            break label2;
                        }
                    }
                }
                if (flg) {
                    System.out.print(j);
                    continue label1;
                }
            }
        }
        System.out.println();
    }
}

本当は、breakやcontinueにラベルを使うくらいなら、メソッドに切り出した方が読みやすいし書きやすいかもしれない。

E - スプリンクラー

問題
競プロやってる人間からすると、ここら辺からむしろ解きやすくなってくる。
「無向グラフ」とかそういう単語が結構平気で出てくるなぁとか思ってた。

問題概要

頂点辺の単純無向グラフがある。
初め頂点は色で塗られている。
各頂点にはスプリンクラーがあり、頂点のスプリンクラーを起動すると、隣接する全ての頂点の色が起動時点の頂点の色に塗り替えられる。
以下のいずれかの形式で与えられる個のクエリを順番に処理せよ。

• '1 x'：頂点の現在の色を出力する。その後、頂点にあるスプリンクラーを起動する。
• '2 x y'：頂点の現在の色を出力する。その後、頂点の色をで上書きする。

• 入力は全て整数
• 
• 

思考過程

1. 制約が小さいので、クエリ１で毎回頂点の隣接リストを全件処理してもで間に合う。

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));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        int q = Integer.parseInt(sa[2]);

        // 隣接リスト
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int u = Integer.parseInt(sa[0]) - 1;
            int v = Integer.parseInt(sa[1]) - 1;
            list.get(u).add(v);
            list.get(v).add(u);
        }

        // 各頂点の色
        sa = br.readLine().split(" ");
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(sa[i]);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int x = Integer.parseInt(sa[1]) - 1;
            pw.println(c[x]);
            if ("1".equals(sa[0])) {
                for (int r : list.get(x)) {
                    c[r] = c[x];
                }
            } else {
                int y = Integer.parseInt(sa[2]);
                c[x] = y;
            }
        }
        pw.flush();
        br.close();
    }
}

F - 回文行列

問題
個人的には難しいところは何もなく。B問題やD問題の方がよっぽど厄介で、そこさえ抜ければ初級は前回よりだいぶ簡単だったのではないかと思う。

問題概要

個の英小文字列から文字ずつ選んで長さの回文文字列を構築せよ。
できない場合はを出力せよ。

• 
• 各文字列の長さ

思考過程

1. 番目と番目、番目と番目、・・・を順に突き合わせ、同じ文字が存在するかを調べる。

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

        char[] ans = new char[n];
        Arrays.fill(ans, '*');
        for (int i = 0; i <= n / 2; i++) {
            // i番目の文字列に、a～zが存在しているか
            boolean[] c = new boolean[26];
            for (int j = 0; j < n; j++) {
                c[a[i][j] - 'a'] = true;
            }
            // n - 1 - i番目の文字列を調べる
            for (int j = 0; j < n; j++) {
                // 文字列[n - 1 - i]のj文字目が文字列[i]に存在する文字の場合
                if (c[a[n - 1 - i][j] - 'a']) {
                    ans[i] = a[n - 1 - i][j];
                    ans[n - 1 - i] = a[n - 1 - i][j];
                    break;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (ans[i] == '*') {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(ans);
    }
}

G - グリッド金移動

問題
まだあんまり難易度アップした感じではないかも。
ついにPASTでも問題文にすぬけ君が出てきた。

問題概要

無限に広がる二次元グリッドのマスからまで、軸方向を前方とした将棋の金と同様の方向に移動できる駒を動かしていくとき、最小何回の移動で到達できるかを求めよ。
ただし、障害物のあるマスが個あり、そのマスには移動できない。
到達不可能な場合はを出力せよ。

• 入力は全て整数
• 
• 
• およびに障害物はない

思考過程

1. 方向に移動できる普通のBFS。マス数を遷移数の倍しても間に合う。
2. 座標はマイナスがあるため、グリッドを表す二次元配列のインデックスは全体的にくらいする。
3. グリッドは無限に広がるため、障害物が壁になっていても、必ず外側を迂回できるはず。迂回する分配列も少し大きめにしておく。

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

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 gx = Integer.parseInt(sa[1]) + 205;
        int gy = Integer.parseInt(sa[2]) + 205;
        boolean[][] ng = new boolean[410][410];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            int x = Integer.parseInt(sa[0]) + 205;
            int y = Integer.parseInt(sa[1]) + 205;
            ng[x][y] = true;
        }
        br.close();

        int[] dx = {1, 0, -1, 1, -1, 0};
        int[] dy = {1, 1, 1, 0, 0, -1};
        int[][] d = new int[410][410];
        for (int i = 0; i < d.length; i++) {
            Arrays.fill(d[i], Integer.MAX_VALUE);
        }
        d[205][205] = 0;

        Queue<Integer> que = new ArrayDeque<>();
        que.add(205 * 1000 + 205);
        while (!que.isEmpty()) {
            int cur = que.poll();
            int cx = cur / 1000;
            int cy = cur % 1000;
            for (int i = 0; i < 6; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                int alt = d[cx][cy] + 1;
                // 配列内 かつ 障害物なし かつ 最短距離更新（＝未訪問）
                if (0 <= nx && nx < d.length && 0 <= ny && ny < d.length
                        && !ng[nx][ny] && alt < d[nx][ny]) {
                    que.add(nx * 1000 + ny);
                    d[nx][ny] = alt;
                }
            }
        }
        // -1はない想定だが一応
        if (d[gx][gy] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(d[gx][gy]);
        }
    }
}

H - ハードル走

問題
一気に難しくなってきた。やっぱり多少複雑なDPができないと中級はもらえないらしい。

問題概要

数直線上をからまで、以下の内いずれかの行動を選んで実行する、ということを繰り返して移動する。

• 行動1：距離地上移動。
• 行動2：距離地上移動＋距離空中移動＋距離地上移動。合計距離進む。
• 行動3：距離地上移動＋距離空中移動＋距離地上移動。合計距離進む。

地上移動中は距離あたり秒、空中移動中は距離あたり秒の速さで進む。
数直線上には個のハードルがあり、番目のハードルは座標にある。
ハードルがある座標で空中移動していなかった場合、追加で秒かかる。
移動にかかる秒数（空中移動中に座標を通過する場合は通過時点での秒数）の最小値を求めよ。

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

思考過程

1. 各座標で行動1～3を行った場合それぞれを遷移として、配るDPをする。
2. 空中でゴールする場合もあるため、～の各座標で、地上にいる場合と空中にいる場合を持てるよう、DP配列を2本用意する。
3. 配るDPだと行動3でを3マスほど行き過ぎるので、配列サイズを余裕持って5くらい大きめにしておく。
4. 地上→地上の遷移は、行動1～3を選んだ3パターン。行動終了地点にハードルがあったらを加算。
5. 地上→空中の遷移は、行動3の途中まで（現在地の各地点）として計算する。　※本当はゴール前3マス以内しかやる必要はない。
6. 空中→地上の遷移は、地上→地上の遷移の末尾部分でしかなく、既に網羅されているので不要。

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

public class Main {
    static int t3;
    static boolean[] h;

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

        sa = br.readLine().split(" ");
        h = new boolean[l + 5];
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(sa[i]);
            h[x] = true;
        }

        sa = br.readLine().split(" ");
        int t1 = Integer.parseInt(sa[0]);
        int t2 = Integer.parseInt(sa[1]);
        t3 = Integer.parseInt(sa[2]);
        br.close();

        int[] dp0 = new int[l + 5]; // 地上用
        int[] dp1 = new int[l + 5]; // 空中用
        Arrays.fill(dp0, Integer.MAX_VALUE);
        Arrays.fill(dp1, Integer.MAX_VALUE);
        dp0[0] = 0;
        dp1[0] = 0;
        for (int i = 0; i < l; i++) {
            // 地上→地上
            dp0[i + 1] = Math.min(dp0[i + 1], dp0[i] + t1 + pena(i + 1));
            dp0[i + 2] = Math.min(dp0[i + 2], dp0[i] + t1 + t2 + pena(i + 2));
            dp0[i + 4] = Math.min(dp0[i + 4], dp0[i] + t1 + t2 * 3 + pena(i + 4));

            // 地上→空中
            dp1[i + 1] = Math.min(dp1[i + 1], dp0[i] + t1 / 2 + t2 / 2);
            dp1[i + 2] = Math.min(dp1[i + 2], dp0[i] + t1 / 2 + t2 / 2 * 3);
            dp1[i + 3] = Math.min(dp1[i + 3], dp0[i] + t1 / 2 + t2 / 2 * 5);
        }
        System.out.println(Math.min(dp0[l], dp1[l]));
    }

    static int pena(int x) {
        return h[x] ? t3: 0;
    }
}

I - 行列操作

問題
クエリの問題多い。この問題が一番解法合ってるのかどうか自信が持てなかった。

問題概要

左上から右方向にのように値が埋まっているの行列がある。
以下のいずれかの形式で与えられる個のクエリを順番に処理せよ。

• '1 A B'：行列の行目と行目を入れ替える
• '2 A B'：行列の列目と列目を入れ替える
• '3'：行列を転置する（とを入れ替える）
• '4 A B'：行列の行列の要素を出力する

• 

思考過程

1. 愚直にやったのでは、クエリ３が1回だけでもで全然駄目そう。
2. クエリ１と２だけなら、元の行番号や列番号がどこに移動したのかを管理すればできそう。
3. クエリ３は、行番号配列と列番号配列を入れ替えるのでいけるのでは。
4. あとはクエリ４で上手いこと辻褄を合わせて出力できればヨシ（サンプルも見つつここを雑に色々試す）。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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 q = Integer.parseInt(br.readLine());

        int[] x = new int[n]; // 行番号配列
        int[] y = new int[n]; // 列番号配列
        for (int i = 0; i < n; i++) {
            x[i] = i;
            y[i] = i;
        }
        boolean flg = true; // 転置していないフラグ

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            if ("1".equals(sa[0])) {
                int a = Integer.parseInt(sa[1]) - 1;
                int b = Integer.parseInt(sa[2]) - 1;
                int tmp = x[a];
                x[a] = x[b];
                x[b] = tmp;

            } else if ("2".equals(sa[0])) {
                int a = Integer.parseInt(sa[1]) - 1;
                int b = Integer.parseInt(sa[2]) - 1;
                int tmp = y[a];
                y[a] = y[b];
                y[b] = tmp;

            } else if ("3".equals(sa[0])) {
                int[] tmp = x;
                x = y;
                y = tmp;
                flg = !flg;

            } else {
                int a = Integer.parseInt(sa[1]) - 1;
                int b = Integer.parseInt(sa[2]) - 1;
                if (flg) {
                    pw.println((long) x[a] * n + y[b]);
                } else {
                    pw.println((long) y[b] * n + x[a]);
                }
            }
        }
        pw.flush();
        br.close();
    }
}

J - 回転寿司

問題
やることが最長増加部分列（LIS）みたいな問題だと思った。
添え字がこんがらがるI問題よりはかなり簡単なのでは。

※地味に時間かかるので、ここから問題概要書くのやめます。

思考過程

1. 各子供がそれまでに食べた寿司の最大の美味しさを持っておく。
2. 各寿司について、前の子供から順に最大の美味しさを超えているか判定したのでは、かかるので駄目。
3. 美味しさの最大値は単調減少するので、二分探索すればとなって間に合う。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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[] a = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int[] max = new int[n];
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < m; i++) {
            int idx = binarySearch(max, a[i]);
            if (idx == n) {
                pw.println(-1);
            } else {
                pw.println(idx + 1);
                max[idx] = a[i];
            }
        }
        pw.flush();
    }

    static int binarySearch(int[] array, int val) {
        int ok = array.length;
        int ng = -1;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            // mid番目の子供が食べた美味しさの最大値 ＜ 現在の寿司の美味しさ
            if (array[mid] < val) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }
}

K - コンテナの移動

問題
本格的に上級向け問題になってきた気がする。実装も結構手間取った。

思考過程

1. もはや検討する価値もない気がするが一応、そのまんまシミュレーションしたのでは毎回の移動個数がなので、全体でで駄目。
2. LinkedListとかに近いイメージで、各コンテナの隣接関係に注目すると、問題文中の例では以下のように変化している。
   • の上が→なし
   • の上がなし→
   • の下が→
3. このように情報を更新していくなら、毎回の処理がで済む。
4. 最後に机から始めて上に何番が載っているかの情報をたどっていくことで、机に置かれているコンテナがわかる。
5. 実装上は、机の上に何もない場合の考慮や、更新前の値の適切な退避などに気を付ける。（ここでだいぶミスって時間かかった。）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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

        int[] f = new int[q];
        int[] t = new int[q];
        int[] x = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            f[i] = Integer.parseInt(sa[0]);
            t[i] = Integer.parseInt(sa[1]);
            x[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        int[] head = new int[n + 1]; // 各机(1-indexed)の一番下のコンテナ番号
        int[] tail = new int[n + 1]; // 各机(1-indexed)の一番上のコンテナ番号
        Obj[] arr = new Obj[n + 1];
        for (int i = 1; i < head.length; i++) {
            head[i] = i;
            tail[i] = i;
            Obj o = new Obj();
            arr[i] = o;
        }

        for (int i = 0; i < q; i++) {
            Obj cur = arr[x[i]]; // 移動するコンテナ(x)の一番下
            int fpre = cur.pre;
            cur.pre = tail[t[i]]; // xの下は移動先一番上だったもの
            if (cur.pre > 0) {
                arr[cur.pre].next = x[i]; // 移動先一番上の上はx
            }

            if (head[t[i]] == 0) {
                // 移動先がコンテナなしだった場合
                head[t[i]] = x[i];
                cur.head = true;
            } else {
                cur.head = false;
            }
            tail[t[i]] = tail[f[i]]; // 移動先一番上は移動元一番上

            if (fpre == 0) {
                // 移動元がコンテナなしになった場合
                head[f[i]] = 0;
            } else {
                arr[fpre].next = 0; // xの下にあったものの上はなし
            }
            tail[f[i]] = fpre; // 移動元一番上はxの下にあったもの
        }

        // 各机から上にあるコンテナをたどる
        for (int i = 1; i <= n; i++) {
            int now = head[i];
            while (now > 0) {
                arr[now].ans = i;
                now = arr[now].next;
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 1; i <= n; i++) {
            pw.println(arr[i].ans);
        }
        pw.flush();
    }

    // コンテナ
    static class Obj {
        int pre; // 1つ下のコンテナ番号(1-indexed、下がない場合0)
        int next; // 1つ上のコンテナ番号(1-indexed、上がない場合0)
        int ans;
        boolean head = true; // 一番下フラグ
    }
}

L - スーパーマーケット

問題
やりたいことはなんとなくすぐわかるけど、きちんと実装できるかが問題だったと思う。

思考過程

1. 本の列については、番目以降は前から順に取られていくので、本のキューを使って表す。
2. 手前の行については、消費期限の大きいものがわかるようにしたいので、消費期限でソートされたTreeSetをつ（以下set0とset1）使って表したい。
3. の場合は以下の操作が必要。
   1. set0から最大の要素を取り出す。
   2. set1からと列が同じ要素を取り出してset0に移す。
   3. 該当列のキューから先頭要素を取り出してset1に入れる。
4. set1から列indexで探すのはこのままではかかってしまうので、列indexからset1の要素を取得できるマップ（配列）も用意する。上記の操作でキューから取り出した要素を配列にも入れる。
5. の場合は以下の操作が必要。
   1. set0の最大要素とset1の最大要素の内大きい方を採用する。
   2. を採用するなら後はさっきと同じ。以下を採用する場合。
   3. set1から最大の要素を取り出す。
   4. 該当列のキューから先頭要素を取り出してset1と配列に入れる。
6. あとは各キューやセットが空になった場合などに注意する。（本番時は一生懸命場合分けしていたが、番兵を入れた方が楽で、下記掲載のコードも番兵版。一応コード長がコメント除いて2240→2015Byte）

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.TreeSet;

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

        Obj b = new Obj();

        List<Queue<Obj>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Queue<Obj> que = new ArrayDeque<>();
            sa = br.readLine().split(" ");
            for (int j = 1; j < sa.length; j++) {
                Obj o = new Obj();
                o.i = i;
                o.t = Integer.parseInt(sa[j]);
                que.add(o);
            }
            que.add(b); // 番兵2つ追加
            que.add(b);
            list.add(que);
        }

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

        Obj[] c1 = new Obj[n]; // 思考過程4の配列
        TreeSet<Obj> set0 = new TreeSet<>();
        TreeSet<Obj> set1 = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            set0.add(list.get(i).poll());
            c1[i] = list.get(i).poll();
            set1.add(c1[i]);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < m; i++) {
            Obj e0 = set0.last(); // set0の最大要素
            boolean flg = false; // set1から取ったフラグ
            if (a[i] == 2) {
                Obj e1 = set1.last(); // set1の最大要素
                if (e1.t > e0.t) { // 5-1
                    pw.println(e1.t);
                    set1.pollLast(); // 5-3
                    Obj next = list.get(e1.i).poll(); // 5-4
                    set1.add(next); // 5-4
                    c1[e1.i] = next; // 5-4
                    flg = true;
                }
            }
            if (!flg) {
                pw.println(e0.t);
                set0.pollLast(); // 3-1
                set0.add(c1[e0.i]); // 3-2
                set1.remove(c1[e0.i]); // 3-2
                Obj next = list.get(e0.i).poll(); // 3-3
                set1.add(next); // 3-3
                c1[e0.i] = next; // 4
            }
        }
        pw.flush();
    }

    static class Obj implements Comparable<Obj> {
        int t, i, a;

        @Override
        public int compareTo(Obj o) {
            return t - o.t;
        }
    }
}

M - 行商計画問題

問題
ここに来て残り2時間ほど。94点狙いなら1問1時間かけられるし、十分な時間はあると思った。
これも方針はすぐに出てきたのだが、実装に手こずっていた気がする。

思考過程

1. 愚直にやるなら訪れる街の順列を全探索で、これは当然間に合わない。
2. なので、とかはいけそう。訪れた街の集合を全パターン持つことはできる。
3. 「：訪れた街の集合が、最後に訪れた街がの場合の最小通行料」（はビットの数値で表す）を考える。
4. 遷移は、街からへの移動を全組合せ行うとして、との和集合元の値, →の最短距離。
5. ここまでがで大丈夫そう。
6. 「→の最短距離」が必要になるので、あらかじめと各を始点としたダイクストラをやっておく。回くらいまあ大丈夫でしょう。

実装は（）と（）がごちゃごちゃになったりなどで苦戦した。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

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

        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int u = Integer.parseInt(sa[0]) - 1;
            int v = Integer.parseInt(sa[1]) - 1;
            list.get(u).add(v);
            list.get(v).add(u);
        }

        int s = Integer.parseInt(br.readLine()) - 1;
        int k = Integer.parseInt(br.readLine());
        sa = br.readLine().split(" ");
        int[] t = new int[k + 1];
        t[0] = s;
        for (int i = 0; i < k; i++) {
            t[i + 1] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        // d[i][j]：頂点i→jの最短距離 をK+1回ダイクストラで求める
        int[][] d = new int[k + 1][n];
        for (int i = 0; i < d.length; i++) {
            Arrays.fill(d[i], Integer.MAX_VALUE);
            d[i][t[i]] = 0;

            Queue<Integer> que = new ArrayDeque<>();
            que.add(t[i]);
            while (!que.isEmpty()) {
                int cur = que.poll();
                int alt = d[i][cur] + 1;
                for (int next : list.get(cur)) {
                    if (alt < d[i][next]) {
                        que.add(next);
                        d[i][next] = alt;
                    }
                }
            }
        }

        int end = 1 << k;
        int[][] dp = new int[end][k + 1];
        for (int i = 0; i < end; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 0; i < end; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                for (int j2 = 0; j2 < k; j2++) {
                    int cur = dp[i][j];
                    if (cur < Integer.MAX_VALUE) {
                        int nd = d[j][t[j2 + 1]]; // j→j2の最短距離
                        int alt = cur + nd;
                        int i2 = 1 << j2;
                        dp[i | i2][j2 + 1] = Math.min(dp[i | i2][j2 + 1], alt);
                    }
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < k + 1; i++) {
            ans = Math.min(ans, dp[end - 1][i]);
        }
        System.out.println(ans);
    }

    static class Node implements Comparable<Node> {
        int v, d; // この頂点のindex、始点からの距離

        public Node(int v, int d) {
            this.v = v;
            this.d = d;
        }

        public int compareTo(Node o) {
            return d - o.d;
        }
    }
}

N - 入れ替えと並び替え

問題
1時間20分ほどかけてなんとかAC。
標準のソート関数が非常に優秀で、転倒数が小さいほど計算量も少なく済むような仕様だったら愚直で通ってしまったり・・・はさすがにないか。たとえ並び替えが1回もなくても、全要素を確認するだけでかかりそうだし。

思考過程

1. 問題通りに実装したのでは、クエリ２にかかって駄目そう。
2. ソート範囲に含まれたという情報だけ上手く引き継いだりして、ソートを実際に行うのは最後の回だけとかにする方法とかはないか？　→そんなのとても無理そう
3. になっている箇所を覚えたりして何か起こらないか？　→よくわからない
4. なんてことをやりつつ、例２から色々動かす場所を変えたりしてみている内にふと、ソートで実際に要素が並び替わる箇所はかなり少ないのではないかと思う。
5. 上記3.の情報を使うことで、元々ソートされている要素をほとんど参照することなくソートを実現できそう。
6. 上記3.の情報は、クエリ１ごとに高々個しか増えないので、ソートのコストを全体でにかかが付くくらいに抑えられそう。
7. 実際のソート処理は以下の繰り返しで行えそう。
   1. となっている、より大きい最小のをセットから取り出す。
   2. ～の範囲はソート済みなので、この範囲で二分探索して、の挿入先を探す。
   3. ～を後ろにつずらして、にを設定する。

どうせ間全部ずらすのだから、二分探索なんてしなくても、普通に動かしていけばよかったかもしれない。

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

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

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = i + 1;
        }
        // 1つ前より小さい値になっているindexを格納するセット
        TreeSet<Integer> set = new TreeSet<>();

        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            int x = Integer.parseInt(sa[1]) - 1;
            int y = Integer.parseInt(sa[2]); // クエリ２はy"未満"で扱う

            if (t == 1) {
                // x⇔x+1
                int tmp = ans[x];
                ans[x] = ans[x + 1];
                ans[x + 1] = tmp;
                // x-1とxの大小関係チェック
                if (x > 0) {
                    if (ans[x - 1] > ans[x]) {
                        set.add(x);
                    } else {
                        set.remove(x);
                    }
                }
                // xとx+1の大小関係チェック
                if (ans[x] > ans[x + 1]) {
                    set.add(x + 1);
                } else {
                    set.remove(x + 1);
                }
                // x+1とx+2の大小関係チェック
                if (x < n - 2) {
                    if (ans[x + 1] > ans[x + 2]) {
                        set.add(x + 2);
                    } else {
                        set.remove(x + 2);
                    }
                }

            } else {
                int idx = x;
                while (idx < y) {
                    Integer k = set.higher(idx); // 7-1
                    if (k == null || k >= y) {
                        break;
                    }
                    int val = ans[k];
                    int to = binarySearch(ans, val, x - 1, k); // 7-2
                    System.arraycopy(ans, to, ans, to + 1, k - to); // 7-3
                    ans[to] = val; // 7-3

                    // 移動先の大小チェック
                    if (to > 0) {
                        if (ans[to - 1] > ans[to]) {
                            set.add(to);
                        } else {
                            set.remove(to);
                        }
                    }
                    // 移動元自身は必ずk-1より大きい
                    set.remove(k);
                    // k-1→kにずれてきた要素とk+1の大小チェック
                    if (k < n - 1) {
                        if (ans[k] > ans[k + 1]) {
                            set.add(k + 1);
                        } else {
                            set.remove(k + 1);
                        }
                    }
                    idx = k;
                }
            }
        }
        br.close();

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

    static int binarySearch(int[] array, int val, int ok, int ng) {
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (array[mid] < val) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ng;
    }
}

N問題がすぐには解けなかったので、一応O問題も15～20分ほどは考えたものの、全くわからず。
何を考えたかもぱっとは思い出せないので、特に書けることはありません。

何はともあれ、82→88→94点と回を追うごとに順調に上がり、正直まだ先だと思ってたエキスパートという1つの目標を早々に達成。
今後はとりあえずレート1800台維持したいな・・。