精進記録: ABC21 - ABC24 C問題
600点相当以下の問題の場合、考察+典型的なテクニックだけで解ける印象。
間違った方針、実装で苦労しても時間がもったいない & 変なクセが付きそう。
実際、AOJの問題を我流のC言語でやっていた弊害か、グラフや木の問題で変なコードを書いてしまう。
ソートと簡単なdpぐらいしか必要ない300点ぐらいの問題はともかく、
今後は高難易度の問題については
考察 -> 解説確認 -> 実装(上位者コードを参考に)
という流れにしてみることにする?
ABC24 330点
手元では問題なく動くコードがAtCoder環境上ではWAする。
以前も同じような状況に出会った。
前回は、vec[in()] = hoge;のような操作で死んだが、
int temp = in();
vec[temp] = hoge;
にしたら大丈夫になった。
前回と同じく、in()の結果を直接make_pairに渡すのではなく一時変数に入れるようにしたら大丈夫になった。原因がわからん。
ABC23 622点
全てのマスについてループさせるのは不可能。
各行、各列のcandy数を持っておいてソートしておく。
givenな行に対してその行のcandy数をnとすれば、答えはrow数が K-nになるcolumnsの数で、これはlower_boundとupper_boundを使えばすぐに求められる。
ただし、それらの行、列の交点はダブルカウントされてしまう。
candy_row + candy_column == N と N +1の両方が必要。
candy_row + candy_column == N を満たすcolumnを集める。
-> (row,column)にcandyが無いものだけansに加える。
candy_row + candy_column == N+1 を満たすcolumnを集める。
-> (row,column)にcandyがあるものだけansに加える。
-> TLE.
candy位置の管理をmapからunordered_mapにしたり、二分探索の範囲を各ステップで狭めるなどしたがやはりTLE.
二分探索でcolumnsの探索範囲を狭めるのは良いが、最悪のケースでは相変わらずO(RC)なので間に合わない。
交点の処理をもっと高速にするしかない。
単純に、candyがあるサイトの処理をループの外でやればよい。
-> AC。
ABC22 563点
巡回セールスマン問題かと思ったが、「少なくとも一軒」だった。
dfsで探索するコードを書いたがTLE塗れ。枝刈り入ってれば通るんじゃないかと思ったが甘くなかった。weightの値は一般に一様から程遠い(特に競プロの場合)ので、楽観的になるとあっさりやられる。
解説によると、出発地点を除いたグラフ上での最短経路問題に落とし込むことで解ける。ワーシャルフロイドで二点間距離を求めておけば、後は一瞬。
climpet さんのコードが分かりやすい。
300点問題だと制約が甘くて適当な実装や悪い計算量のアルゴリズムでも通ってしまうケースがあるが、600点ぐらいの問題になると、そうもいかない。
ただ、まだこのぐらいでは高度な知識は要求されないように見える。
正しく考察すると典型問題に落とし込める + 実装が300-400点問題より面倒 ぐらいの難易度感。
ABC21 493点
またグラフ問題。
500点ぐらいになると、ゲーム木やグラフが主体になってくる？
最短経路の候補はどれだけあるか。
道路の長さ = weightは全て同じなので、通ってきた街の数が等しいものがどれだけあるか。
同じ街を二回通るのは明らかに最短ではない。
サンプルケースから分かる通り、a, bが橋で結ばれた部分グラフの異なる側にいる場合、
解はそれぞれの橋と橋の間の最短経路の積として求められる。
しかし、橋を検出してどうこうは500点相当にしてはややこしすぎるし、各部分グラフ内の探索は依然として残る。
aから最短nステップでbに到達できるとき、グラフ中のノード cについて、cを通る最短経路の数は
(a -> c最短の組み合わせ) * (c -> b最短の組み合わせ)
になる。最短経路であるため、a->cで通ったノードがc->bで使われることがない。
aから最短ステップで cに到達する組み合わせの数を dp[a][c]としておく。
任意のノード xについて、xの隣接ノードをy_xとすると dp[x][y_x] = 1;
これを予め埋めておいた上で、y_xの隣接ノード z != xについて、
dp[x][z] += dp[x][y_x] ;
dp[z][x] += dp[x][y_x] ;
このDPをBFSで埋めていく。
BFSであれば、bを探索した時点で終了。
-> AC。
途中で気づいたけど a から情報だけで足りるから dp[y_x]だけでok。
正解こそしたものの、bfsの探索状態を調べるのに配列を3つも使ったコードになっている。
・そのノードまでの最短経路の数が確定しているか否か
・そのノードが既にキューに入っているか(入ったことがあるか)
・そのノードのaからの距離
の３つが必要になっている。
あるノードまでの最短経路数が確定していて、かつそのノードが、今調べているノードの一つ手前の場合にだけ、、、、 ということをしたい。
過去にキューに入ったことがあるかどうかを管理する必要は必ずしもない。
popされた段階で、既に経路数が確定していればcontinueすれば良い。
