Atcoder Beginner Contest 035
2016/3/26 に行われた過去コンテストの問題にチャレンジ
A テレビ
特に問題なく解けた。
B ドローン
特に問題なく解けた。
C オセロ
初回
問題自体はシンプルなので、N個の要素を持つ配列に駒への操作数を保持して、奇数の場合「白」、偶数の場合「黒」という形で解いた。 要素を白黒の状態の維持ではなく操作累計数にしたのは、要素のへの参照をしなくていいようにしたが、配列の要素への参照は軽い処理のためあまり考えなくても良かった？
オーダー数はO(QN). 400億。。 解いている最中はオーダー数の考慮ができていなく、TLEになってしまった。
解説を見て
いもす法というやりかたで計算量を大幅に減らせるということで、いもす法で解き直してみた。
考え方は結構わかりやすくて、
状態の常に再現するのではなく、状態を構築する要素を記録しておき、別のプロセスで再現を行うことで、状態の再現の効率化を図る方法
という印象。
今回の問題でいうと、ひっくり返す作業を範囲内の駒全体に処理するのではなく、作業の範囲の始点、終点が解るようにメモしておき、そのメモから最終的な状態を再現する。
計算量は、
ひっくり返す範囲をメモしていく処理をQ回、メモから各要素の状態を再現する作業を要素数分ということで、N回.
なので、O(Q + N)と初回で解いた方法よりかなり改善され、無事全テストケースパスできた。
D トレジャーハント
だいぶ苦戦。。 コンテストで同じような問題が出されたら時間内に解ける気がしない。
グラフの最短経路のついてのノウハウがあればそうでもない？
初回
問題の理解として、一番効率がいいのは、複数のいくつかの町にとどまるのではなく、効率のいい町一箇所になるべく多くの時間滞在、というのにはすぐに気づけ、町ごとにTに対して、滞在できる時間を割り出すことができれば解けるなとは思った。
しかし、最短経路の概念を知らなかったので、自力で解こうと思い、結果苦戦した。
データをオブジェクト化せずに、配列の添字で扱っていたので（a[0]はコスト, a[1]はその町から出ている道のリストなど。。）訳がわからなくなってきたので一回クリアに。 ロジックとしては実装できたと思ったが、デバッグが厳しかった。
解説をみて
最短経路の問題で、任意の町へ行く道、帰り道の最短経路を割り出し、与えられたTに対しての各町で稼げる額のMAXをとることで解答可能ということ。
最短経路に関しては、いくつかの解法パターンがあるらしい
- ワーシャルフロイド法
グラフ上の全ノード間の最短距離を全て割り出す方法。
計算量はO(Nの三乗).
コードはシンプルだが、なんでこれで全てのノード間での最短距離が出せているかが直感的に理解できなかったので、理解するまで結構取り組んだ。あとで別記事にまとめるかも。
グラフ上の任意のノードから全ノードへの最短距離を割り出す方法。
計算量は実装によって色々あるらしく、愚直にやると、O(Nの二乗)で、優先度付キューを使うと、O((N + E)logN). Eは道の数
今回の問題は、始点が決まっているので、ダイクストラ法が適している。
ダイクストラ法 + 優先度付キューで実装してみたが、下二つのテストケースでTLEとなってしまった。
これは実装が悪いか, rubyの限界かはよくわからない。 そろそろC++移行をがんばったほうが良さそう。
振り返り
問題自体の理解は今までのところある程度できている。
解法パターンを知らないと、一定時間内にTLEを出さずに実装するのは相当厳しそう（D問題のような）
ある程度以上の規模の問題は、配列のままデータを扱うのではなく、オブジェクトなり、構造体で扱うべき。 規模が小さい問題なら、クラスを定義する手間をかけなくていいので、配列のまま解いてもいいが、ある程度の規模になると、この添字の意味はなんだっけ？と考えるのが思考の妨げになって、ロジックに集中しづらくなる。
デバッグの出力の方法もある程度パターン化しておいたほうが良さそう。 ライブラリ化する？
課題
問題によっては、ミニマムケース、エッジケースを自分で考えることによって問題への理解が深まりそう。 現状は与えられた問題例のみで考えているので、WA, RE となった際にお手上げになってしまう感がある。
解法パターンの無知 プログラミングコンテンツチャレンジブックを少し読んだ程度で、それ自体も結構前のことなので、実際に理解していて活用できる解法パターンが少ない。
今回のように問題を解いて、1つ1つ理解していくしかない？ 特定の問題と解法パターンを意識的に切り離して考えることで、応用しやすくしていくことはできそう。
