ABC181

昼のイベントで疲れたらすっかり参加し忘れてしまった。

C

考えたこと

Nが100なので二乗のオーダーでも余裕

各ペアを結ぶベクトルを求める、これは余裕

しかし「2つのベクトルで向きが一致するものがあるか」を素朴にやると10^8で怪しい

半分の半分にすれば間に合うのではないかって感じもある

ダメだったら既約分数をsetに入れる

この時逆向きのものも一緒に入れると良い

公式解説

三重ループでも判定が定数ならよい

傾きの一致判定は除数を消せる

D

考えたこと

Sの長さはかなり長いが、8の倍数かどうかは1000で割った余りを見ればわかるので、要は3文字でよい

Sの長さのオーダーで各数字の出現頻度を調べる

125通りの「8の倍数である条件」を機械的に列挙して、与えられた数がそれを満たすかチェックすればよい

公式解説OK

F

考えたこと

領域の表現が難しいな

領域が表現できたら、ある領域から別の領域に移動するのには直径いくら以下である必要があるのかは点の距離で求まる

必要なのはボロノイ分割自身ではなく、ボロノイ分割をする時にどの点とどの点を選ぶかのペア

「デローニー分割」ドロネー分割って呼び方の方が主流？

O(NlogN)

それをやった上で、端の頂点からは上または下に他の辺と交差せずに伸ばせるかチェックして、外側の通路も刻む必要がある

そこまでできたとして、これは最大フローではないからどうやって解くのか考えなければならない

Nは高々100で、領域は最悪でも200ぐらい

半径を決めれば各辺は「通れる通れない」になる。スタートとゴールが連結であるかどうかはDFSで求まる、十分早い

半径は最大で100で、要求される精度は10^-4

二分探索なら20回程度で絞れる

公式解説

領域ではなく壁に注目

上の壁と下の壁が壁で繋がれば通行不能

壁であるかどうかは2点間の距離を見るだけでOK

距離をソートして小さい方から連結になるまで増やしていく