今回のB問題はちょっと癖のある問題だったのでそちらも含みます。
B問題 Split Ticketing
一直線の電車の路線で一方向のみ、a→cのように直行するよりも、a→b→cのように途中下車を一回挟むことで安く済ませられる区間が存在するかどうか。
N<=100と制約がそこまで大きくなく、考慮すべきルートは一方向のため特に凝った解法は必要なく全探索できるが、渡される料金表はそのままでは下段へ行くにつれて先細りしていくピラミッドに似た三角型の構造なので、格納時にデータ構造を工夫して分かりやすくする必要がある。
解説
制約のNが3から100までと小さく、全探索（O(n3)として最大1000000通り）で十分間に合うので問題文の通りに実装すればよい。しかしB問題としては珍しく、入力されるデータ構造に手を加えないと少し面倒です。
三角に先細りしていく配列ですが、この問題ではルートが一方向のため1駅目からより遠い駅では選択できる駅の数が減る、つまりiに応じてj列が減っていく特徴があります。i行目に渡される配列Cの要素数はN-i個となり、制約の通りiはN-1が最大です。
そこで、(N,N)となる2次元配列を考えたとき、i行目では対角線上（i=jとなる位置）より右側（i<j）にのみデータがあることが分かります。i=Nの時のi=jは、この問題においてはN駅目つまり終点にあたるため考慮する必要がありません。
となれば入力の配列をピラミッド様の三角ではなく(N-1,N)の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<cがそれにあたるので、for文を回す時にa==bやb==cが成立する状況にならないようにします。まあ言ってしまえばfor文中の初期化式をこのようにします。
for文の初期化式（公式解説の実装例と同様のもの）
for (int a = 0;;)
{
for (int b = a + 1;;)
{
// あとCも同様に
}
}他にも料金の計算では制約上算術オーバーフローの可能性があります。Ci,jの制約ではint型に収まるからといって、Ci,j+Ci‘,j‘の計算をint型+int型とすると、long型に格納するとしても計算結果自体は算術オーバーフロー後のものになってしまうため、入力を受け取る時点でlong型にキャストしておくなどのケアが必要です。
以上によって全探索をすることで答えを求められます。
疑似コード
疑似コード（折り畳み）
// 標準入力は一部省略
long型二次元配列costsを宣言[n-1,n];
for (i < n - 1)
{
標準入力から配列csを取得
for (j < n)
{
i<jならばcosts[i,j]にcs[j-i-1]を代入;
}
}
// a<b<cならforの初期化式で重複しないようにすべきだし、条件式も重複しないように考慮する必要がある。
変数ansを宣言し文字列"No"で初期化;
for (a = 0; a < n - 2;)
{
for (b = a + 1; b < n - 1;)
{
for (c = b + 1; c < n;)
{
if(問題文の通り比較) "Yes"を代入;
}
}
}
変数ansを出力;ACコード
二次元配列への代入について、疑似コードとは違う式を採用しています。自分にとって分かりやすい方を選択すればよいです。
C問題 Puddles
白色のマス「.」で構成された連結領域で、外周に触れているマスを含まない連結領域の数を数え上げて答える。隣接の判定は上下左右のみ。
最大1000*1000の1000000マス。
隣接するマスについて
問題文中で隣接しているかどうかを数学仕草で説明されているが、これを簡単に言うと「そのマスの上下左右を隣接していると見なす。」という感じ。
斜めのマスを含む場合は式の真ん中の＋は×とかになるはず。間違ってたらごめん。式にある縦線は絶対値記号、マス(i,j)の上の点はプライム記号（あるいはダッシュと呼ばれる）。実際の数値（座標）を当てはめて考えればすんなり理解できるはず。もし分からなければコメントください。画像付きで解説するんで。
こんなところまで記事を読みに来るくらい熱心なあなたなら、ちゃんと読み解けます。
で、そういった前提が分かれば解法が分かる。解法が分かれば実装が……でき、……。
解説
BFS・DFSが使えるタイプの問題。再帰でも可。「.」マスが隣接する部分を木構造と見なして探索するよくあるやつ。最大1000000マス程度なら全探索で問題なし。
グリッドに対してBFS・DFSを使う実装に慣れていないとまあまあめんどくさいが、概念上そこまで複雑でもないので慣れるのも早いはず。
その「.」マスから先のマス（グラフ理論でいうところの頂点）を探索するのに、条件式が煩雑になっていく。グリッドの外周でないこと、グリッドの外側にアクセスしないこと、未探索のマスであること、その先も「.」のマスであること。しかも解く問題毎にこの辺の処理が少し変わるので、気を使わないとWAになる。
探索時に配列外にアクセスしないようにすることと、連結領域を探索したあとで「外周部分に触れていたかどうか」で処理を変える必要があるため、これらを混同しないように注意が必要です。
BFS・DFSや再帰の実装については以下で。
疑似コード（再帰）
疑似コード（折り畳み）
// 標準入力は省略
bool型二次元配列visited[h,w]を宣言;
int型変数ansを宣言;
for (i < h)
{
for (j < w)
{
// アーリーリターン
if (黒マス || 到達済み) continue;
外周マスを含んだかどうかの変数wgを宣言;
// 再帰関数を宣言
void Rec(ri,rj)
{
if((ri,rj)が外周マスなら) wg = true;
以下のif文は(ri,rj)の上下左右それぞれのマスについて:
if (インデックスは配列の範囲内 || 到達済みでない || 白マス)
{
Rec()を呼ぶ;
到達済みフラグを立てる; // このif文の外でも動くが、基本はこの位置にあった方が良い。
｝
}
if(wg) continue;
ans++;
}
}
ansを出力;ACコード
感想
AB2完。Bに時間を掛け過ぎてCが間に合わなかった。
Cも解法は会ってるはずなのにWA。原因が判明するまでずっともやもやするんだよねこれ。解決しようにも時間だけがいたずらに過ぎていくし、ほっといて天啓を待つにもそれまでずっともやもや。キモイ。
結局は考慮漏れ。範囲外の判定を-1 < iなどとすべきところを0 < iで判定してた。あーほんとにもー。
コメント