第五回アルゴリズム実技検定 (バーチャル参加)

f:id:suisen_kyopro:20201230003234p:plain

O は解法は正しかったけど定数倍に敗北して 10 分間に合わず. ただ, 直接の敗因は間違いなく SASUKE が面白かったせい (え？)

A - ○✕ゲーム

S.contains("ooo"), S.contains("xxx") をそれぞれ見る (同時に成立することはない).

B - 上書き

ArrayList<Character> で処理中の文字列 t を持っておくと, 文字 c の削除は t.removeIf(e -> e.equals('c')) で判定できる. 追加は t.add(c).

確かめてないけど, removeIf の中の判定を e == 'c' でやると壊れると思う. Integer みたいに ASCII 文字の範囲がキャッシュされてたら大丈夫だけど, その辺は把握してない.

C - 三十六進法

問題文から 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ をコピーして, charAt なりで求めるのが楽そう.

D - リーディングゼロ

まず, 先頭に 0 がない場合を考えると, $x$ と $y$ の数としての順序と文字列としての順序は次のように対応づけられる.

$|x|\gt|y|$ の場合: 数として $x\gt y$
$|x|=|y|$ の場合: 文字列としての順序と数としての順序は一致する
$|x|\lt|y|$ の場合: 数として $x\lt y$

なので, こういう風にソートすれば OK.

Arrays.sort(s, (x, y) -> {
    int l = x.length, m = y.length;
    int i = 0, j = 0;
    while (i < l && x[i] == '0') i++;
    while (j < m && y[j] == '0') j++;
    int rx = l - i; // x から先頭の 0 を除いたときの長さ
    int ry = m - j; // y から先頭の 0 を除いたときの長さ
    if (rx == ry) { // ケース 2
        int cmp = Arrays.compare(x, i, l, y, j, m);
        if (cmp == 0) {
            // この問題では, 0 の数が多い方が小さいとみなす
            return j - i;
        } else {
            // 文字列としての比較
            return cmp;
        }
    } else { // ケース 1, 3
        return rx - ry;
    }
});

E - ハンコ

やばすぎ. 解法としては, 4 パターンの回転と, 座標の重なり方を全探索するだけなんだけど...

汚くなったので省略.

F - 一触即発

一転して安心感のある全探索. $2 ^ N$ 通りに対して「物質に薬品 $x$ を新たに追加すると爆発するような薬品 $x$ の数」を数えるだけ. 全体 $O((N+M) 2 ^ N)$ で書くと安心. $O(NM 2 ^ N)$ だと単純計算で $8 \times 10 ^ 7$ くらいになって危なそう ?

G - ヘビ

要するにハミルトンパスを見つけて復元する問題. dp テーブルを以下で定義すれば OK (日本語がやばい...).

$\begin{aligned} \mathrm{prev}[i][S]=&\mbox{ 既に訪れた頂点集合が $S$ であって,} \\ &\mbox{ 今は頂点 $i$ にいるようなパスにおける,}\\ &\mbox{ $i$ の前に訪れた頂点} \end{aligned}$

H - コンベア

ゴールから逆方向に BFS するだけ.

I - 避難計画

避難所から逆方向に多始点 BFS するだけ. 同じ問題が連続して並ぶのはいいのか... ?

J - 長い長い文字列

再帰. コード見た方が早そう.

static char solve(char[] s, long x) {
    long c = 0;
    for (char t : s) {
        if ('a' <= t && t <= 'z') {
            c++;
            if (c == x) return t;
        } else {
            int rep = t - '0'; // 繰返し回数
            if (c * (rep + 1) >= x) {
                // 基本的には x % c 番目を求めたい
                // しかし, 丁度割り切れる場合に壊れるので (x - 1) % c + 1 とする
                return solve(s, (x - 1) % c + 1);
            }
            c = c * (rep + 1);
        }
    }
    throw new AssertionError();
}

K - 的あて

難しかった. bit DP をすればよくて, テーブルは以下で定義する.

$\begin{aligned} \mathrm{dp}[S]=&\mbox{ 残りの的の集合が $S$ であるような場合の,} \\ &\mbox{ ゲーム終了までの投擲回数の期待値} \end{aligned}$

遷移を考える. 的 $i\in S$ に当たった場合は, $\mathrm{dp}[S \backslash \{ i \} ]$ の値を参照すれば良いが, 的に当たらなかった場合は自身を再帰的に参照することになるので, 式変形が必要.

いま, $S$ に対して最適な目標マス $x^*$ が分かっていると仮定する. このとき, 当たる可能性のある "マス" の集合 $U _ { x ^ * }$ と当たる可能性のある "的" の集合 $T _ { x ^ * } \subset U _ { x ^ * }$ が定まる. ここで, $T _ { x ^ * } \subset S$ もまた成立し, 以下の式が成立する.

$\begin{aligned} \mathrm{dp}[S] &=1+\sum_{i\in T_ { x ^ * }}\frac{1}{|U_ { x ^ * }|}\cdot\mathrm{dp}[S\backslash \{i\}]+\sum_{i\in U_ { x ^ * }\backslash T_ { x ^ * }}\frac{1}{|U_ { x ^ * }|}\cdot\mathrm{dp}[S]\\ &=1+\sum_{i\in T_ { x ^ * }}\frac{1}{|U_ { x ^ * }|}\cdot\mathrm{dp}[S\backslash \{i\}]+\frac{|U_ { x ^ * }\backslash T_ { x ^ * }|}{|U_ { x ^ * }|}\cdot\mathrm{dp}[S] \end{aligned}$

両辺の $\mathrm{dp}[S]$ をまとめて, 以下の式を得る.

$\displaystyle \mathrm{dp}[S]=\frac{1}{|T_ { x ^ * }|}\left(|U _ { x ^ * }|+\sum_{i\in T_ { x ^ * }}\mathrm{dp}[S\backslash \{i\}]\right)$

$x^*$ の値は事前には分からないので実際には以下を計算すればよい.

$\displaystyle \mathrm{dp}[S]=\min \left\{ \frac{1}{|T_ x|}\left(|U _ x| +\sum_{i\in T_ x }\mathrm{dp}[S\backslash \{i\}]\right) \;\middle|\; |T_x|\gt 0\right\}$

L - T消し

難しい. 結論から言えば, 区間 DP を 2 回やると解ける. 以下では, $S[l:r]$ は半開区間 $S_l,\dots,S _ {r - 1}$ を表すものとする.

一回目の区間 DP では, 次のテーブルを埋める.

$\mathrm{ok}[l][r]=\mbox{$S[l:r]$ を完全に消去できるか}$

$l=r$ のときは, $\mathrm{ok}[l][r]=\mathrm{True}$ . $l\lt r$ のときは, 区切り位置 $m$ を全探索して, 以下のいずれか成り立つかを見ればよい.

$\mathrm{ok}[l][m] \land \mathrm{ok}[m][r]$
$\mathrm{ok}[l+1][m] \land \mathrm{ok}[m+1][r-1] \land S_lS_mS_{r-1}=T$

つまり (?),

$\begin{aligned} \mathrm{ok}[l][r] &=\left(\bigvee_{m=l+1}^{r-1}\mathrm{ok}[l][m] \land \mathrm{ok}[m][r]\right) \\ &\lor \left(\bigvee_{m=l+1}^{r-2}\mathrm{ok}[l+1][m] \land \mathrm{ok}[m+1][r-1] \land S_lS_mS_{r-1}=T\right) \end{aligned}$

二回目の区間 DP では, 次のテーブルを埋める.

$\mathrm{dp}[l][r]=\mbox{$S[l:r]$ に対する操作回数の最大値}$

これは以下のように求められ, 答えは $\mathrm{dp}[0][N]$ である.

$\mathrm{dp}[l][r]=\begin{cases} \dfrac{r-l}{3} & \text{(if $\mathrm{ok}[l][r]$)}\\ \displaystyle\max_{l\lt m\lt r}{\mathrm{dp}[l][m]+\mathrm{dp}[m][r]} & \text{(otherwise)} \end{cases}$

計算量は全体で $O(N ^ 3)$ .

M - 棒の出荷

決め打ち二分探索をしたくなって, 実際にやってみると解ける. つまり, 長さの下限 $X$ に対して, 次の条件 $P(X)$ を満たすような分割が存在するかを判定する.

$P(X)$ :「切断後の断片の長さ $l_1,\dots,l_k$ が $X\leq l_i\leq L$ を満たす」

この判定問題は, 次で表される集合 $S_i$ を $i$ の昇順に求め, $N\in S_N$ かどうかを見ることで解ける.

$\displaystyle S_i=\{j\lt i \mid \mbox{$j$ 番目までの棒を $P(X)$ を満たすように分割できる}\}$

$S_i$ は,

$\displaystyle t_i=\min \left\{ k \;\middle|\; \sum_{j=k}^{i} A_j \leq L \right\}$

を前計算しておくと以下のようにして求められる.

$S_i=\begin{cases} S_{i-1}\cup\{i\} & \text{if $\displaystyle\sum_{j=p+1}^{i} A_j \geq X$}\\ S_{i-1} & \text{otherwise} \end{cases}$

ここで, $p=\displaystyle \min\left\{ x\in S _ { i - 1 } \;\middle|\; x \geq t_i\right\}$ とした. これらの計算は累積和や二分探索, 平衡二分探索木 (または Segment Tree) を用いることで高速に行える.

N - 旅行会社

セグ木上で二分探索をする.

O - 通知

クエリ平方分割.

$\sqrt{Q}$ 個毎に全ての通知を伝播することにすると, 伝播は $\sqrt{Q}$ 回起こり, 毎回 $O(M)$ 時間かかるので伝播パートは全体 $O(M\sqrt{Q})$ となる.

クエリに答えるパートでは, $\sqrt{Q}$ 個しか必要な頂点が存在しないので, 不要な頂点を消したグラフを用いることで愚直にやっても毎回 $O(\sqrt{Q})$ 時間で答えることが出来る. クエリは合計 $Q$ 回飛んでくるので, クエリに答えるパートは全体 $O(Q\sqrt{Q})$ 時間となる. グラフの再構築にかかる時間は全体で $O(M\sqrt{Q})$ である.

以上より, 全体 $O((M+Q)\sqrt{Q})$ 時間でこの問題を解くことが出来る. ただ, 定数倍が結構きつくて, 隣接リストを実際にリストで持つと TLE した. 配列に直すと定数倍が改善されて 2000 ms を切った.