AtCoder AGC033 参戦記 - cplusplusonly's memo

AtCoder の AGC033

に参戦しました。ABC の仕様変更 (6 問で 1999 まで rated) により水色を維持することにあまり意味はなくなりましたが、レートは落としたくないので、A 問題はマストとして、B, C のうちどちらかを解ければよい (どちらも解ければハッピー) という考え方で臨みました。
結果は 101 分で A, B の 2 問 (ただし 2 WA 2 TLE) となり、順位は 737 位、パフォーマンス 1548 でした。WA/TLE が多すぎてパフォーマンスを落としましたが、可もなく不可もなしという感じです。

f:id:y_r:20190505001730p:plain

感想

A 問題

最初は $\max(\forall 点, min(\forall 黒マス, 点と黒マスの距離))$ みたいな実装して TLE くらった... $1000*1000*1000*1000$ の計算量は TLE くらうよね...
素直に黒色を中心として幅優先探索をしたのだが、ここでも WA (すべてが黒色のケース) と TLE (探索済みマスの探索防止を忘れてた) により -15 分...

B 問題

H 軸と W 軸は独立して扱える
後ろからたどっていって上下左右に落とせるマスの範囲をもとめて、その範囲内に始点があれば No, なければ Yes となる
- ただし途中で (右に落とせるマス <= 0) (上下左も同様) となったらその時点で No
- ただし途中で (左に落とせるマス <= 右に落とせるマス) (上下も同様) になったらその時点で No
  - 上記は嘘解法 (というか考察ミス) 正確には (左に落とせるマス - 1 <= 右に落とせるマス)。

ところまで考察して実装..なのだが、実装ミス*1により WA をくらう。