今回のB問題はちょっと癖のある問題だったのでそちらも含みます。
B問題
一直線の電車の路線で一方向のみ、直に行くよりも途中下車で安く済ませられる区間はあるかどうか。
N<=100と制約がそこまで大きくないので特に凝った解法は必要なく全探索できるが、渡される料金表はそのままでは下段へ行くにつれて先細りしていくピラミッドに似た三角型の構造なので、格納時にデータ構造を工夫して分かりやすくする必要がある。
解説
制約のNが3から100までと小さいので全探索、問題文の通りに実装する。しかしB問題としては珍しく、入力に手を加えないと面倒くさい。
つまり入力の配列をピラミッド様の三角ではなく2次元の表にする。
入力で与えられるピラミッドのような三角形の頂点は、この問題ではCN-1,N、つまり、2次元の表の右下の角。具体的に言うと以下のような図の黒四角■が入力値となる。
N=4
□■■■
□□■■
□□□■ ←この角の■がCN-1,N
このようにするとa,b,cのインデックスを計算で合わせる必要がなくなり、Ca,bとCb,cとCa,cを求めやすくなる。
配列上のC0,0などその他の箇所（上図でいう□）は、この問題ではコーディングが合っていればアクセスすることはないので何でもいいのだが、あえて無意味であることを表すため制約上ありえない値（この問題では0,-1,1000000001など）や無効な値（nullなど）を入れるとミスに気付きやすい。
あとは細かいミスに気を付ける。一つ例を挙げると、路線が一直線な都合で同駅発同駅止はありえないことなど。制約でいうところのA<BかつB<Cがそれにあたるので、for文を回す時にA==BやB==Cが成立する状況にならないように。まあ言ってしまえばfor文中の初期化式をこのようにする。
for文の初期化式（公式解説の実装例と同様のもの）
for (int a = 0;;)
{
for (int b = a + 1;;)
{
// あとCも
}
}C問題
白色のマス「.」で構成された連結領域で、外周に触れているマスを含まない連結領域の数を数え上げて答える。隣接の判定は上下左右のみ。
最大1000*1000の1000000マス。
隣接するマスについて
問題文中で隣接しているかどうかを数学仕草で説明されているが、これを簡単に言うと「そのマスの上下左右を隣接していると見なす。」という感じ。
斜めのマスを含む場合は式の真ん中の＋は×とかになるはず。間違ってたらごめん。式にある縦線は絶対値記号、マス(i,j)の上の点はプライム記号（あるいはダッシュと呼ばれる）。実際の数値（座標）を当てはめて考えればすんなり理解できるはず。もし分からなければコメントください。画像付きで解説するんで。
こんなところまで記事を読みに来るくらい熱心なあなたなら、ちゃんと読み解けます。
で、そういった前提が分かれば解法が分かる。解法が分かれば実装が……でき、……。
解説
BFS・DFSが使えるタイプの問題。再帰でも可。「.」マスが隣接する部分を木構造と見なして探索するよくあるやつ。最大1000000マス程度なら全探索で問題なし。
グリッドに対してBFS・DFSを使う実装に慣れていないとまあまあめんどくさいが、概念上そこまで複雑でもないので慣れるのも早いはず。
その「.」マスから先のマス（グラフ理論でいうところの頂点）を探索するのに、条件式が煩雑になっていく。グリッドの外周でないこと、グリッドの外側にアクセスしないこと、未探索のマスであること、その先も「.」のマスであること。しかも解く問題毎にこの辺の処理が少し変わるので、気を使わないとWAになる。
BFS・DFSや再帰の実装については以下で。
感想
AB2完。Bに時間を掛け過ぎてCが間に合わなかった。
Cも解法は会ってるはずなのにWA。原因が判明するまでずっともやもやするんだよねこれ。解決しようにも時間だけがいたずらに過ぎていくし、ほっといて天啓を待つにもそれまでずっともやもや。キモイ。
結局は考慮漏れ。範囲外の判定を-1 < iなどとすべきところを0 < iで判定してた。あーほんとにもー。
コメント