ABC129-D
https://atcoder.jp/contests/abc129/tasks/abc129_d
この問題を解きました。ネタバレを含むのでご注意ください。
与えられるH行W列のグリッドのうち、もっとも広い範囲を照らすことができる場所にランプを置いたときのマスの数を出力する問題です。
例えば以下のような入力が与えられたと考えます。
(# は障害物を表しています。詳しくはリンクから問題文を読んでください)
#..#.. .....# ....#. #.#...
この場合は上から2行目、左から2列目のマスにランプを置くと合計8マスを照らすことができて、これが最大となるので8を出力します。
制約は
1 <= H <= 2000 1 <= W <= 2000
となっています。
行を列を別々に考えるとわかりやすくなるので、ここでは1番上の行について考えてみます。
#..#..
このうち、4つの . のうち、どこにランプを置いても照らすことができるマスの数は2です。
2行目は
.....#
となっていて、1列目〜5列目まではどこに置いても照らすことができるマスの数は5です。
列についても同じように考えると、
1列目は
# . . #
なので、2行目か3行目にランプを置くと2箇所照らすことができます。
2列目は
. . . .
なので、どこに置いても4箇所照らせます。
つまり、行について考えるとき以下のような入力に対して
#..#..
以下のようなデータを用意することができれば、H*Wで全探索することができます。
022022
問題を解く方針については以上です。
データを用意する部分がこの問題の肝というか、この問題から学べたことなんですが、
in = ['#', '.', '.' ,'#', '.', '.']
このような配列から . の数をカウントして
in = ['#', '.', '.' ,'#', '.', '.'] out = [] // なにか処理 // outの中身=> [0, 2, 2, 0, 2, 2]
のような配列outを作りたいとき、in[2]の時点でのカウント2をout[2]に入れるのは簡単ですが、out[1]の部分に入れるところが厄介です。
こんなイメージです
for(int i=0; i<W; i++){
if(in[i] == '#') continute;
int cnt = 0;
for(int j=0; j<W; j++){
if(in[j] == '#') break;
cnt++;
}
out[i] = cnt; // なんかおかしい
// このcntって、in[2]の時点では2だけど、それをout[1]に巻き戻って入れようとすると計算量が増えてしまうよ？
// それじゃあTLしちゃうよ？
}
これはしゃくとり法っぽい動きを使うことでO(n)で達成することができます。 (もしかしたらこれも一種のしゃくとり法と呼べるのかもしれません)
int cnt = 0;
for(int i=0; i<W; i++){
if(in[i] == '#') continue;
// 計算済みの場合は変数の値をout[i]に入れて次に進む
if(calcDone[i]){
out[i] = cnt;
continue;
}
// iの位置から始める
for(int j=i; j<W; j++){
if(in[j] == '#') break;
cnt++;
calcDone[j] = true; // 計算済みであることを記録しておく
}
out[i] = cnt;
}
こうすれば 2nで（つまりO(n)で）目的の配列を作ることができます。
以上のようにすべての行すべての列で必要なデータを用意すれば、あとは全探索するだけです。
提出したコード
