競技プログラミング in Go #2

前回

今回

今回は下記の記事を参考に部分和とLake CountingのAtCoderの問題を解いていく。 qiita.com

たくさんの数式

問題：C - Many Formulas
解答：Submission #19722074 - AtCoder Regular Contest 061

考えたこととか

+を入れるパターンを全列挙すれば良いと考えた。考慮として先頭の数字の扱いや桁の扱いがあるが、上手く考えきれず結構時間がかかってしまった。けれど、演算子ではなく符号で考えてしまえば先頭の数字を意識せずに処理ができることに気がついた。これに気がつくまで時間がかかってしまった。
解説を読むと、ビット演算で演算子を入れることが可能な箇所を全列挙して計算すると良いと書いてあったので、符号で考えるのは想定パターンじゃないのかも。

全列挙はビット演算で行った。Goで解いたがビット演算はC++と同じなので直感的に記述できた。ただ、ビット演算を書いていてi&1<<j >= 1でビットが立っているか確認する処理でバグらせてしまった。&は<<よりも優先順位が高いので、((i&1)<<j) >= 1となってしまっていた。あと、解答した後に思ったけれど、(i>>j)&1とすれば== 1と書けるのでわかりやすいかも。

解説では桁を考慮して10を掛けて足すような処理をしていた。ここはGoのSliceを上手く使って書けたのは良かった。

Train Ticket

問題：C - Train Ticket
解答：Submission #19722660 - AtCoder Beginner Contest 079

考えたこととか

これはすぐできた。数字の入力だけど文字列で受け取り、'0'を引くことで各数字の配列を得る。1パターンだけ見つければ良いので全部試して7になったら打ち切る。

All Green

問題：C - All Green
解答：Submission #19738173 - AtCoder Beginner Contest 104

考えたこととか

自力では解けなかった。要復習。

解説を読んだ上での感想として、得点パターンの確認を怠っていた。回答数ばかりに意識を取られて、どのような得点の積み方があるのか考えていなかった。さらにそこから、得点パターンを踏まえた上で最適化した積み方を考える必要があった。

高橋君とお肉

問題：A - 高橋君とお肉
解答：Submission #19738359 - AtCoder Regular Contest 029

考えたこととか

すぐできた。焼き時間をソートして空いている方を優先して焼けば良い。

派閥

問題：D - 派閥
解答：Submission #19765185 - AtCoder Beginner Contest 002

考えたこととか

自力で解けなかった。

1番大きいCycleを探せではなく1番大きいMeshを探せという問題。互いに知っている特性から、伸びているEdgeの数がそのNodeの関係数の最大値となる。なので、Edge先を番号を配列として控えておき、それをEdge先の各Nodeとも関係性があるのか確認するような処理にすれば、その最大値が答えになると思い実装をした。しかし、これでは解けなかったので解説を読んだ。

解説によると、これは最大クリーク問題と呼ばれる有名な問題とのこと。NP困難。

ja.wikipedia.org

Meshと呼んでいたけど正しくはクリーク。今回の問題は入力値が小さい数字なので全探索できる。例えば1~3までの議員がいるなら、関係性の組み合わせは{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}の計8パターンになる。入力内容のグラフから、このパターンを全部確かめて最大のクリークになるものを探せば良い。

深さ優先探索

問題：A - 深さ優先探索
解答：Submission #19841473 - AtCoder Typical Contest 001

考えたこととか

問題名が答えみたいなもの。実装で思ったこととして、再帰関数の引数はバリデーションせずに渡してしまった方が楽。境界判定とかはインデックスとして使う前でやればOK。

一度通ったところに目印をつけておかないと無限ループするので、通ったところは'#'として通れなくしておく。

埋め立て

問題：B - 埋め立て
解答：Submission #19843166 - AtCoder Regular Contest 031

考えたこととか

さっきの問題には始点と終点があったので一瞬悩んだ。けれど数字が小さいので全探索できると気づいた。全ての座標から開始して、通過した点を'o'から'x'にする。もし埋め立てることが可能なのであれば、1つの座標から全ての'o'の座標を通過できるはずなので、全座標が'x'になったら埋め立て成功。

実装でひと手間必要だったところは2つあった。
まず多次元配列のコピー。全座標について通過した点の値を変える全探索をするため、探索用にコピーをしておく必要がある。しかし、多次元配列内の配列をコピーしても配列の値のポインタは変わらないので、ちゃんと値までコピーしてあげる必要がある。

func copyMatrix(src [][]rune) [][]rune {
    dst := make([][]rune, len(src))
    for i, v := range src {
        dst[i] = make([]rune, len(v))
        copy(dst[i], v)
    }
    return dst
}

あとは探索の開始点を'x'ではなく'o'にしておくことだ。'x'のままで渡してしまうとバリデーションに引っかかってしまう。そのため前処理として開始点を'o'にする1行入れてあげるだけで実装がかなり楽になる。

バウムテスト

問題：B - バウムテスト
解答：Submission #20036890 - AtCoder Regular Contest 037

考えたこととか

自力で解くことができなかった。また、解説を読んでもすぐに解けなかった。不正解だった思考、解説を読んだ後、最終的な解答とその思考の順で書く。

不正解だった思考
紆余曲折しながら考えたので取り留めもない思考になっている。文章にすると非常にわかりづらいけれど、その通り思考も整理しきれていなかったのだとわかる。
まず、1度通ったノードを再度通れるなら閉路なので、それを判定できるようにすれば良さそうだと考えた。しかし、これまでのように通過したノードを通れないノードにすると、通過済みなのか元から通過できないのか判断できなくなってしまう。そのため、ステータスとして未探索と探索中と閉路の3つを用意してあげれば良さそうだと思った。探索中のステータスのノードにぶつかったら、閉路として塗り直す。そうすれば最終的に残る木が答えになる。
これについてグラフをイメージすると8の字のような形の時に上手くいかなそうだなとか、閉路の位置によってはバグりそうだな、と漠然と思っていた。手は動かしていたもののそれらしい解答が実装できず解説を読むことにした。
解説を読んで
詳細は間違っていたけれど、閉路の判定には通過済みノードを用いて再帰的に処理すれば良いというところは合っていた。また、不正解だった思考の時は閉路だとわかった時に再帰を打ち切ろうと思っていたけれど、木としてカウントをしなければ良いだけなので処理を続けてしまって良い。もし途中で打ち切ってしまったとしても、繋がっているのであれば後続のループで判定は可能なので気にしなくて良い。このあたり意識して実装を行いsubmitした。
解答（誤答）：Submission #20032525 - AtCoder Regular Contest 037
しかしこれは誤答だった。サンプルは全てACだったのでいまいちわからず、ググってみたらまさにというものがあった。
アルゴリズム - AtCoder ARC 37 バウムテスト ACできない理由がわからない｜teratail
探索で根を考慮できていなかった。グラフによっては1つのグラフを2つのグラフとみなすようになっていた。ということで根を考慮して再submit。
解答（これも誤答）：Submission #20033904 - AtCoder Regular Contest 037
実装のどこかミスってるんだと思う。当たり前だけど。
最終的な解答
解説ブログや他のACの解答を見て修正を行った。シンプルになった。
解答：Submission #20036890 - AtCoder Regular Contest 037
感想
これまでの探索では上下左右のノードにしか遷移しなかったが、今回は任意のノードに遷移できるという点が違いだと思う。上下左右の遷移の場合、通過したノードを通行禁止にしてしまえば無限ループせずに探索できるため、その思考に固執してしまったと思う。特に解説を読む前の思考で、ステータスで色分けをすると考えていたが、その色塗り対象はエッジだった。これは上下左右に遷移するグラフの考え方に近い。
任意のノードに遷移できるグラフだと回しているループのインデックスの前後でinvalidな状態を判定できないので、別途訪問状態を保持しておく必要がある。それが今回の実装だとvisited := make(map[int]bool)だ。このmapを使って訪問判定をする発想ができなかった。

まとめ

バウムテストは解説を読んでもなかなか解けなかった。周辺ノードではなく任意のノードに遷移できるグラフの閉路判定は別途訪問状態を保持しておく必要がある、という知識はしっかり憶えておいてすぐに頭から引き出して書けるようにした方が良いと思った。
今回解けなかった問題、時間がかかってしまった問題は来月あたりに再度解きたい。