121. AtCoder参加記録（AtCoder Beginner Contest 257）

26回参加でレート 1285 です。

今回はパフォーマンス 1221 です。

ABCDを通して、EFGExは未解答です。Cで1ペナ。

各問題の思考過程など。

1分47秒。

愚直にやっても十分間に合うと判断したので、問題文の通りにやりました。

8分21秒。

初め「一番右のコマは動かさない」と誤読していました…。各コマがどの位置にあるか保持しておけば愚直にシミュレートするだけで良いです。誤読やバグらせがあって妙に時間がかかってしまいました。

初回提出15分7秒、そこからACまで3分54秒。

初め数分、答えで二分探索する方針を考えてしまいました…。最近覚えたことが出てきてしまう病。

体重の昇順で並べておく
大人の合計人数を数えておく
「体重 → 正しく判定できた人数」の Dictionary を用意する
順番に見ていって、Dictionary を更新していく（同じ体重の人がいる場合は新しい値で更新）
1. 「ここまでに出てきた子供の人数」と「大人の合計人数からここまでに出てきた大人の人数」を引いたものが正しく判定できた人数
Dictionary の Value の最大値が答え

$X$ は実数を取れるので、間が $1$ しか空いてないパターンなどは考えなくてもOKです。また、このアルゴリズムだと全員大人だった場合の最適判定ができないので、「体重0 → 大人の合計人数」を最初に Dictionary へ追加しておく必要があります（1WA）。

ソートに一番時間がかかって $O(N \log N)$ 。

45分56秒。遅すぎる…。

ジャンプ台 $i$ と $j$ のマンハッタン距離を $d(i, j)$ として、ジャンプ台 $i$ から $j$ への移動に必要なジャンプ力は $\displaystyle \left\lceil \frac{d(i, j)}{P_i} \right\rceil$ 。これをコストと捉えると、完全有向グラフが見える。

ここから、25分くらい考えていた方針。よく考えたらこの方針でも解けたかも…？

コスト降順に並べて、入次数が 0 になる頂点が現れるまで削っていき、最後に削った辺のコストが答えでは？
色々実装をバグらせたものの、結局正しい答えは出て来ない。そもそも、始点は任意に選べるので、入次数が 0 になる頂点が 2 つ現れた時点でアウトか…。これを修正しても正しい答えは出ない（何かバグらせていた？）

ここで、「始点は任意に選べる、そこから任意の頂点へ遷移できる、経由するコスト最大値を最小化したい…」という状況を改めて考える。すると、「これワーシャルフロイド法に状況似てるな…」と気付く。制約的にも $O(N^3)$ が通るのでこれが想定解では？

ワーシャルフロイド法の最小コスト更新を $c(i, j) \leftarrow c(i, k) + c(k, j)$ から $c(i, j) \leftarrow \max(c(i, k), c(k, j))$ に変える
得られたコスト行列から、始点 $i$ について終点 $j (i \ne j)$ へのコストの最大値をそれぞれ出して、それらの最小値が答え（ABC255-B問題みたいな処理）