ken_math https://blog.hatena.ne.jp/ken_math/ 強くなりたい https://well-defined.hatenadiary.com/ 典型90問 競プロ 012 - Red Painting（★4） マスを赤く塗るクエリと赤で塗ったマスが繋がっているかを判定するクエリを処理する問題。 連結判定なのでUnionFindを使う。 その際マスを数字に対応づける必要があるが、それは とすればよい。（これは左上から順にマスをひとつずつ数えていったとき何番目に対応するかを表しており、この対応は単射である。まあW進法と考えれば当たり前だが……） AC 013 - Passing（★5） (ある地点Kを経由して1からNまで辿る最短経路) = (1からKまでの最短経路) + (KからNまでの最短経路) 最短経路を求めるにはダイクストラを使えば良い AC 014 … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwell-defined.hatenadiary.com%2Fentry%2F2022%2F05%2F17%2F143644" title="典型90問 まとめ 011～020 - 強くなりたい" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/k/ken_math/20220517/20220517155010.jpg Hatena Blog https://hatena.blog 2022-05-17 14:36:44 rich https://well-defined.hatenadiary.com/entry/2022/05/17/143644 1.0 100%