AGC033反省会
はい.
久々の0完太陽.
二時間半椅子を温める作業をしていました.
これじゃだめなので反省会を開催したいと思います.
まず,
問題を見た瞬間の「これはダメだ」感が強かった.
グリッド問題が苦手of苦手なので,NoSub撤退も最初から視野に入っていました.
じゃあなぜ,TLE解を提出してしまったのか.
それはグリッド問題がなぜ苦手なのかに関係してると思うんです.
それは「グリッド問題の計算量の見積もり方が分からない」ってことだったんです.
結局僕は「ソートはO(n log n)」みたいな計算量しか見積もれないってことだったんです.
だってdfsとかbfsの計算量ってよく分からなくないですか
そう思って蟻本を読みなおしてみると,どうやら同じ場所を二度探索しないように工夫することでO(HW)を達成しているようです.
で,今回の問題はどうすればO(HW)を達成できたのか.
僕にはdfsでもbfsでも解けるように見えました(実際どっちも書きました)
しかし訪れた場所は見ないような実装をしていたつもりなのになぜかTLEが出るし,それを頑張ろうとすると再帰での更新がバグってWAが出たりしました.
結局dfsやbfsの問題を避けてきたのが結果として表れたってだけなんですよね
じゃあこれを変えるためにはどうすればいいか
結局の所,精進をするしかないんですよね
問題を解いてbfsさんやdfsさんのお気持ちを理解してあげるしかないんです
ということでグリッド問題を解きまくりたいと思います.
とりあえずこの問題は絶対ACさせる.
ほかにもグリッド問題を探して解く.
なかなか気持ちがもたない気がするのでバチャしたいなぁ
おすすめのグリッド問題があれば教えて頂きたいです
これで水色になろうなんて本当に甘かったです.
僕は変わります
グリッド問題を得意問題にしてみせます