競技プログラミング in Go #3
今回
今回は下記の記事を参考に迷路の最短路と特殊な状態の列挙のAtCoderの問題を解いていく。
qiita.com
幅優先探索
問題：C - 幅優先探索
解答：Submission #20044513 - AtCoder Beginner Contest 007
考えたこととか
[][]runeにしておくと、距離を保存する時に '1'~'9' までしか入れられないから面倒だった。距離用に [][]intの多次元配列を用意して、距離を見たい時はそっちから参照するようにした。
チーズ(Cheese)
問題：E - チーズ (Cheese)
解答：Submission #20049509 - 第１０回日本情報オリンピック 予選（オンライン）
考えたこととか
めちゃくちゃ苦戦した。計4回提出したが、大まかな方針は間違っていなかった。自作のqueueのパフォーマンスが悪かったため、queueについて少し計算を加えるような実装になっているとTLEやMLEが発生してしまっていた。これを通した時はqueueはそこまで原因になっていないと思っていたが、色々試す中で結果的にqueueに対する走査が減ったようでACとなった。これは時間を置いて再度解きたい。
Grid Repainting
問題：D - Grid Repainting
解答：Submission #20050170 - AtCoder Beginner Contest 088
考えたこととか
最大になる時は最短経路を通過する時なので、.の総数から最短経路のマスの数を引けば良い。素直な問題だったのですぐ解けた。
Darker and Darker
問題：A - Darker and Darker
解答：Submission #20050717 - AtCoder Grand Contest 033
考えたこととか
#を通過できないように前処理を入れたらあとはBFSをする。探索時に数字を渡しておいて、maxを取っていけば探索終了時にそれが答えになる。これも素直な問題だったのですぐ解けた。
器物損壊！高橋君
問題：C - 器物損壊！高橋君
解答：Submission #20134936 - AtCoder Regular Contest 005
考えたこととか
コストの扱いを考慮することはできていたけれど、上手く実装できなかった。ARC005には解説がないため、検索をして探したところ01BFSを使うと良いとのこと。なんのことかわからなかったので調べたらすごくわかりやすい記事を発見した。
これによりコストが低い選択肢が優先的に処理されるようになるため、障害物を避けた経路をより選択して探索を行うことができる。また、同じノードにたどり着く複数の経路があったとしても、01BFSではコストが低い選択肢を先に処理しているため、訪問済みとしてそのノードにチェックを入れて後続の探索で打ち切ることができる。
キューにpushFrontを実現するため、SliceTricksを見ながら実装を行った。
SliceTricks · golang/go Wiki · GitHub
しかしこれはTLEになってしまう。
先ほどのチーズ(Cheese)ではキューの実装が悪かったためにTLEになっておりキューに対する処理を減らすことでACできたが、今回はそうはいかなかった。そのため他の人の01BFSを使った解答を見たら下記のパッケージを使っていることがわかった。
go/src/container/list at master · golang/go · GitHub
SliceTricksの実装だとappend時に配列をたくさん作ることになり、特にpushFrontでは要素の長さだけ毎回メモリを確保してしまっていたのだと思う。なのでcontainer/listのようにlinked listになっていると非常に高速になった。
One-stroke Path
問題：C - One-stroke Path
解答：Submission #20176878 - AtCoder Beginner Contest 054
考えたこととか
探索できたものを数えれば良いのでそう実装していたのだがWAになってしまった。サンプルだけ通っていて何が起きているのかわからず解説を読んで通した。
WAの原因はindexの取り違いだった。for-rangeで回していた二次元配列の値をindexと間違えていて、DFSで誤った値が処理されていた。二次元配列のループはfor-rangeにせずにふつうにiをインクリメントしながら走査してvec[i][j]と値を見た方が直感的な気がした。
解説に載っていたDFSの前後でvisitedをtrue/falseとするコードはすごく良かったので取り入れて解答した。これを読む前はDFSで再帰する際にcopyして渡していたので、かなりメモリ効率が良くなったと思う。
カード並べ
問題：D - カード並べ
解答：Submission #20177931 - 第９回日本情報オリンピック 予選（オンライン）
考えたこととか
数が少ないので全部列挙してしまうのが良さそう。また、数字だと桁を考慮しないといけないので数字で扱うよりも文字列で扱って、mapのlenを取る実装が良さそう。懸念として文字列の結合コストがある。ここだけは気になる。
実際に実装してそれでOKだった。ただ、選択した数字のインデックスに対応して[]boolをtrueにして選び取る実装をしてしまい時間を食ってしまった。[]intにして選択したものをappendしてその順序を維持してmapに突っ込む。AC。
One-stroke Pathで学んだdfsの前後で状態をコントロールする実装ができたので嬉しい。
まとめ
DFSもBFSも特に迷わず実装できているけれど、状態をどうコントロールするのかまだスラスラ書けないので制約が増える度に手が遅くなるのを感じる。ただ書いていてすごく楽しい。
