僕が考えたこととライフハック

政治経済、ITについて書く。

AGC033 参加メモ 初めてのAGC、0完だった。

https://atcoder.jp/contests/agc033

こんにちは。

昨日のAGC、0完でした。

A問題くらい解けるやろ~くらいの気持ちで参加しましたが甘過ぎました。反省も兼ね、A問題で考えたことやなぜ答えに行きつかなかったのかを書きたいと思います。

 

A問題全く歯が立たなかったわけではなく、頭の中、机上のシミュレーションはあっていたみたい。。。

本番中に考えたこと

f:id:rynsk02:20190505092447j:plain

何番目に黒く塗られるかを表現できたらいいなぁ~とか考えてました。イメージとしては”逆マインスイーパー”みたいな感じです。

しかし、どう考えても4重ループ以上になり実際実装してみると余裕で間に合いませんでした。(案の定引っ掛かって一人で笑ってた。)

他に考えたことは、迷路の最短経路問題のように各#からの距離を幅優先探索で求め、最小値で更新していく。ですね。

しかし、幅優先探索を柔軟な形で実装(考えることすら)できなかったので、結局ループの数一緒じゃね。間に合わなくね?。といった感じで他の事を考えていました。

実際、解法は上の画像でやったようなシミュレーションを幅優先探索で求めるというものでした。

あと一歩。。。

解法が思いつかなかった原因

幅優先探索の抽象的な理解ができてなかったのが良くなかったのかなと思います。

幅優先探索は迷路問題で最短歩数を記録し、ゴールまで歩いていくアルゴリズムみたいな認識でしかなかった。ということです。幅優先探索は次に見ていく部分をキューに入れていくという操作があるのですが、そこに関しての理解をもっと深めておくべきだったなと。。。

この問題で言うと、#の左右上下の座標をキューに入れ、メモ配列に”1”を入れ....という操作をキューの中身がなくなるまでやるということですね。(なるほど....)

結果、計算量はO(HW)。

すごい。

 

まとめ

基本的なアルゴリズムも実装できていないのでもっと基礎的な部分の理解と、それらの類題をたくさん解いていきたいと思う。