Maximum-Cup 2018
Updated:
Source codes
Solutions
A - フィギュアスケート界の貴公子埼大選手
$\sum_{\{ i \mid d_i \geq 10 + t_i \}} d_i$ を計算する。
B - 駆け抜けろ！埼大山車部！！
これは嘘解法を通しました。後で反省して正しい解法で通します。
ポイント
C - 嘘つきな天使たち
指を指した相手を方向付きの辺だとすると、どこからスタートしても、これはループになっているはずである。最初の人が天使だと仮定すると次の人は悪魔、その次の人は天使と決まっていく。故にループが奇数長なら矛盾が生じているし、偶数長ならば、最初の人が天使か悪魔かにかかわらず、天使の人数自体はその半分である。全てのループが偶数長なら答えは $N/2$ だし、ひとつでも奇数長のループがあれば -1 が答え。
D - Many Go Round
動的計画法をするだけである。
$DP[i] = i$ 番目の休憩所につくために必要な最小の距離
として、燃料ごとに更新していけばよろしい。一旦 $DP2$ に結果を保持して $DP$ にコピーする。
E - Interrupt Array
ポイント
F - 献立表制作
ポイント
G - Sparrow’s trick
ポイント
H - Maxmin Tour
$0$-indexed とする。全ての $1 \leq i < K$ に対し、地点 $a_i$ の石を持っているのであれば答えは $0$ である。得点は $\max \{ s_i \mid 0 \leq i < K-1 \}$ で定義されるので、「得点 $T$ 以下でこのツアーが完了するか？」という問題を解くことにする。これを解ければあとは二分探索で exact な回答が出る。
まず頂点 $i$ から頂点 $j$ への最短距離 $d[i][j]$ をワーシャルフロイド法で求める。ここで次の規則でフローを作る。辺の重みは全て $1$ とする。まず $0 \leq i < K-1$ について始点と頂点 $a_i$ を結ぶ。次に $d[a_i][a_{i+1}] > T$ ならば、 cnt++ しておいてから全ての $0 \leq j < Q$ に対し $d[a_{i+1}][b_j] \leq T$ ならば頂点 $a_{i+1}$ と $b_j$ を結ぶ。ここで $a, b$ はネットワークの頂点としては区別することにする。最後に全ての $0 \leq j < Q$ に対し $b_j$ と終点を結ぶ。このフローで大きさ cnt のフローが流せるならば、それはつまり、 $d[a_i][a_{i+1}] > T$ となった頂点 $a_i$ にいるときに、何か石を割ってどこかの頂点 $b_j$ にワープし、そこから $d[b_j][a_{i+1}] \leq T$ でたどり着けるということである。そしてその石は $2$ 回以上使ってはいない。だから「得点 $T$ 以下でこのツアーが完了するか？」は Yes である。そういうフローが流せないなら、「得点 $T$ 以下でこのツアーが完了するか？」は No である。以上で問題が解けた。
ポイント
最初の言い換えがポイント。だいたいこういう問題のスコアは sum のはずであり、 max や min だと二分探索が可能となることは意識しておきたい。
Others
間違い：$d[u][v] = d[v][u] = v$ にしていた。 $u, v, w$ は見間違えやすいようだ。