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

• アーカイブ
• 提出

リアルタイム受験した。4時間40分かけて全完。前回に比べるとかなり苦戦した。

F

別解っぽいの:

$B_i$の降順に埋められるできるだけ早い日を埋めていく貪欲が成立する。（交換しても損しないことに注目すればよい。） このとき、$\operatorname{next}[i] :=$ $i$日目以降(inclusive)でまだ埋めていない最も早い日、として空きを管理する。$\operatorname{next}$を辿る際にpath compressionするとたぶん${O}(N\log N)$。

K

(を見るとネストの深さが+1され、)を見ると深さが-1されると考えると、文字を削除（=無視）するのは深さを変えないで次に進むことと解釈できる。したがって、次のようなDPが可能である:

$\operatorname{dp}[x][y] :=$ $1, ..., x$文字目まで見て、深さが$y$の場合の最小コスト

答えは$\operatorname{dp}[N][0]$に等しい。${O}(N^2)$。

L

$K$個の要素を選ぶ際、先頭から$x$番目(0-based)の数の元のインデックス$i$(0-based)は$i < N-D(K-x-1)$を満たす必要があり、その中で最小（タイブレークはもっとも左）の数を選べばよい。優先度付きキューでできる。

M

今回いちばん大変だった問題で、最後にACした。

数列$(C_i)$をいくつかつなげたものを走査して、各食事$x$についての情報を累積していく。具体的には、$\operatorname{table}[x]$に(日付, この日付までに食べた料理$x$の数, この日付までに食べた$x$以外の料理の数)の日付に関する昇順配列を作って、料理$x$が出るたびに情報を追加していった。こうすると、ある日付から一巡したときに食べる好みの料理の数と好みでない料理の数は二分探索でわかるので、何周するか計算すればよい。ただし、端の処理をするのがかなりつらかった……

N

平面走査する。$x$座標を圧縮しておいて$y$座標に関して走査した。

O

問題の条件を無視して最小全域木$T$を得たとする。$T$に$T$外の任意の辺$e := (u, v)$を追加すると閉路ができるが、この閉路上でもっとも重みの大きな（$e$以外の）辺を除けば求める最小全域木$T_e$が得られる。（正当性は最適性条件により明らか……と言いたいところだが、そんなに簡単な証明を思いつかなかった。下に書いた。）この「辺の重みの最大値」は$T$上のパス$u - v$に関する$\max$クエリを処理すれば得られる。

やることはわかったのだが、そもそも木上のパスクエリを処理した経験があまりない。単純なオイラーツアーではmin/maxの処理ができないように見えるし、HL分解やLC木は持っていないし、Mo's algorithmでは${O}(1)$の遷移が思いつかないし、しばらく困っていた。HL分解を調べて書こうと決めたところで、そもそも更新がないのでLCAのbinary liftingがそのままmin/maxクエリにも使えることに気づいた。やっぱり経験がないとこういうことがぱっとわからないな。

証明: $e$のコストを$w$とし、このコストを$0$に変えたグラフを$G_0$とする。また、$G_0$のMST $T_0$が与えられたとして、そのコストの総和を$W_0$とする。（path optimality conditionより）$T_0$は$e$を必ず含むので、$T_0$は$G$上でコスト$W_0 + w$の全域木になっている。$G$の$e$を含む全域木 $T'$でこれより総コストの低いものが存在すると仮定して、総コストを$W'(< W_0 + w)$とする。$T'$は$G_0$の全域木でもあり、コストの総和は$W'-w$だが、$W'-w < W_0 + w -w = W_0$なので、$T_0$がMSTであるという仮定に反する。したがって、求める全域木は$G_0$のMSTであることがわかった。

あとは、上の作り方でできた全域木$T_e$が$G_0$上でMSTであることを示せばよい。$T_e$外の任意の辺$e'$を追加すると閉路ができるが、この閉路に含まれる$e$以外の辺は（$T$の$G$におけるpath optimality conditionより）$e'$以下の重みを持つし、$e$自身は重み$0$なので、やはり$e'$以下の重みを持つ。したがって、$T_e$は$G_0$上でpath optimality conditionを満たす。$\square$

後半は有名事実だと思うけど若干雑…… 書き直すかも