典型90問まとめ 011～020 - 強くなりたい

012 - Red Painting（★4）

マスを赤く塗るクエリと赤で塗ったマスが繋がっているかを判定するクエリを処理する問題。

連結判定なのでUnionFindを使う。

その際マス $(r,c)$ を数字に対応づける必要があるが、それは

$\displaystyle (r,c) \longmapsto rW + c$

とすればよい。（これは左上から順にマスをひとつずつ数えていったとき何番目に対応するかを表しており、この対応は単射である。まあW進法と考えれば当たり前だが……）

(ある地点Kを経由して1からNまで辿る最短経路) = (1からKまでの最短経路) + (KからNまでの最短経路)
最短経路を求めるにはダイクストラを使えば良い

ソートして同じ順位にあるものたちの差を足し上げれば良いことがすぐにわかります。

制約が全探索してくれって言ってるので素直に全探索しましょう。

以下のコードではなるべくループの回数を少なくするために $A>B>C$ となるようにしています。

Aの $i$ 枚、Bを $j$ 枚使うとしたときに $N-Ai-Bj$ が非負でCの倍数なら $k = \frac{N-Ai-Bj}{C}$ とおくと $i+j+k$ が最小値の候補です。これを繰り返します。 AC

三角比でゴリゴリ計算すればOK

私はarctanを求める方法で解きました。いろいろな求め方があると思います。

誤差に注意しようという問題。

$b\log_2 c> \log_2 a$ は $c^{b} > a$ と同値なので後者で判定していく。