AtCoder Beginner Contest 176の解説・感想

100-200-300-400(2)-500-0で2ペナ5完1500点。

A - Takoyaki

$T$ 分間に $X$ 個のたこ焼きを作れるので、実際に1分ずつシュミレーションしていけばよい。現在焼いたたこ焼きの個数を変数で管理して、 $T$ 分経つごとに $X$ 個増やしていき、初めて $N$ 個を超えた時の時間を出力する。計算量は $O(\frac{NT}{X})$ 。
と、ここまでしなくても、 $T$ 分ごとにたこ焼きの個数が増える以外の出来事が起こらないので、 $T$ 分ごとに見ればよいことがわかる。つまり、たこ焼き機で一回焼くごとに $X$ 個のたこ焼きが増えるとき、何回焼けば $N$ 個以上になるかをシュミレーションすればよい。計算量は $O(\frac{N}{X})$ 。
さらに、 $T$ 分ごとに増えるたこ焼きの量は一定なので、シュミレーションしなくても割り算で答えを求めることができる。答えを求める式は $\lceil \frac{N}{X} \rceil \times T$ となる。計算量は $O(1)$ 。
このように、ABCのA問題は $O(1)$ の計算量でも解ける（for文を使わなくても解ける）ように作られていることが多い（絶対ではない！）。

B - Multiple of 9

$N$ の値が非常に大きく、最大ケースでは $2\times 10^5$ 桁近くにもなるため、例えばC++のlong long型などで管理することはできない。*1
なので入力を工夫して、文字列型で受け取ることにする。あとは問題文の通りに $N$ の各桁の数字をすべて足し合わせて、9で割った余りが0ならYesを、そうでないならNoを出力する。計算量は $O(\log N)$ 。

C - Step

一番前の人から順番に、「 $A_i\le A_{i+1}$ を満たしているか？」を見ていけばよい。もし $A_i\gt A_{i+1}$ となっている箇所があれば、高さ $A_i-A_{i+1}$ の踏み台を設置してあげることで、 $A_i=A_{i+1}$ を達成できる。この時、 $A_{i+1}$ の身長を $A_i$ と同じになるよう変更することで、計算量 $O(N)$ で解くことができる。

D - Wizard in Maze

2回TLEを出してしまった問題。
最初に試したのは、ワープ0回で行けるところをDFSで探索し、そのあとワープ魔法を1回使って到達できるところをメモし、DFSで探索、ワープ2回で行けるところを…という風にした。しかしこの場合、最悪計算量が $O(H^2W^2)$ となり間に合わない。
そこで、BFSを用いた実装に方針を変えた。始点のマス（ $C_h, C_w$ ）から探索を始めて、現在探索しているマスから
・上下左右4方向に隣り合うマス(ワープ回数そのまま)
・ $5\times 5$ の範囲内にあるマス(ワープ回数+1)
をpriority_queueに挿入して、ワープ回数が少ない順に取り出すようにした。しかしこのとき、priority_queueから要素を取り出した後にそのマスにたどり着くために必要なワープ回数を更新していたので、そのマスが取り出されるまでの間複数回同じマスが挿入されてしまう場合があり、再びTLEした。なので、priority_queueに挿入されることが決まった時点でマスのワープ回数を更新することで、同じマスが複数回priority_queueに挿入されることを防いだ。計算量は $O(HW)$ 。
ちなみに、dequeを用いた01-BFSでの解法もあるらしい。なかなか発想が出てこない…。

E - Bomber

D問題よりこちらの方が簡単だった。D問題はどちらかというと実装よりの典型問題という気がする。
ある行とある列を選んだとき、その行と列に含まれる爆破対象の個数が最大となるようにしたい。ここで、どの行を選んだかという情報とどの列を選んだかという情報はほぼ独立している。唯一、行と列の交点に位置するマスだけは考慮しなければならない。 $i$ 行目にある爆破対象の個数を $R_i$ 、 $j$ 列目にある爆破対象の個数を $C_j$ とする。 $R_i$ の最大値と $C_i$ の最大値をそれぞれ $R_{max}, c_{max}$ として、 $R_i = R_{max}$ となるような行をすべて記憶しておく（例えば配列などにメモしておく）。列についても同様の処理を行う。
あとは、メモした行 $i$ とメモした列 $j$ の組み合わせをすべて試す。マス（ $i, j$ ）に爆破対象があれば爆破できる爆破対象の個数が $R_{max} + C_{max} - 1$ となる（行 $i$ と列 $j$ で重複してカウントしているため1を引く）。マス（ $i, j$ ）に爆破対象がないなら、爆破できる爆破対象の個数が $R_{max} + C_{max}$ となる。このとき、これ以上多く爆破することはできない*2ので、これが答えとなる。すべての行列の組み合わせについてマス（ $i, j$ ）に爆破対象が存在するのなら、答えは $R_{max} + C_{max} - 1$ となる。
計算量について、例えばマス（ $1, 1$ ）、（ $2, 2$ ）、...に爆破対象が存在するような場合、すべての行と列が最大値の候補となるため組み合わせが $HW$ 通りになってしまうが、その組み合わせの中で1つでも爆破対象が存在しないような行と列の組み合わせが見つかれば答えが確定するので、そこで探索を打ち切ってしまえばよい。爆破対象は高々 $M$ 個しかないので、計算量は $O(M)$ となる。（コンテスト中は嘘解法のように思えたが、ブログを書くために整理してるときに正当性を証明できた！！）