2020/08/25 - いろいろな記録

AtCoderのネタバレを避けるため、書く順番を最後にしてみた。

英語

DMM英会話

競プロ

AtCoder 6AC
ABC176バーチャル参加（1時間のみ）

D - Wizard in Maze

解説AC : 40分

地獄のようにペナを出し続けた。基本的にはBFSで問題ないが、コスト1で移動した先からコスト0の移動で追加された頂点がもう一度挿入されてしまっていて、無限ループにはまってしまっていた。

コスト0の移動をした点を先に扱う、01-BFSというアルゴリズムを学んだ。やること自体は極めてシンプルだが、優先的に0のものをdequeで処理することで最短経路が出るというのは目から鱗だった。

参考になったサイト：

01-BFSのちょっと丁寧な解説 - ARMERIA

E - Bomber

解説AC : 15分

一瞬考えて別の用事をし、そのあと解説をみてしまった。勿体無いからこういう問題の使い方はしないこと。

愚直が通らない問題は視点を変えるというのが基本。絵を描いてみると、行に乗っている点の数の最大値を $C_{max}$ 、列に乗っている点の数の最大値を $R_{max}$ として、答えは $C_{max} * R_{max}$ か $C_{max} * R_{max} - 1$ になることがわかる。どちらになるかは、乗っている点の数が $C_{max}$ となる行、 $R_{max}$ となる列の全ての組み合わせにおいて、その交点がもともと爆弾が存在する地点であれば-1である、と判定できる。

---

ぼちぼち本読んでるから読書ログつけたい。このブログにまとめようかな。

明日ABC175のバチャをやります。