DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 - C - Strawberry Cakes
https://gyazo.com/13223fcbf2d13516222a9950c18b5cac
最初に出したコードでWAになるケースがわからなかった。。
考えたこと
問題をみると必ず分けれるという条件
いちごの位置を最初にメモして、いちごから四方に伸ばしていって、他のいちごにぶつかるか、すでに他の切り分け範囲になっているところまで広げて行けばいいのでは?
以下のように$ 6 \times 6のケーキで、いちごが4つあるとする
まずいちごの位置を特定して、番号をつける
https://gyazo.com/dd5d1b4c740913d3c987e9f2a2ffbace
1つ目のいちごから見ていく、まず上下にいちごにぶつかるまでを伸ばしていく。ここは確定でこのケーキの範囲となる
https://gyazo.com/def41b6f924297e242b5c3f8e8df9b12
次にこの上下の範囲(この場合は上が1行目, 下が4行目とする)で左右に広げていく(長方形という条件のため)
4列目の4行目に、いちごがあるので、4列目は別の切り分け範囲となる
https://gyazo.com/8caa4ef4b0d86f249d8d9f60aaf7c38b
次のいちごを見ていく
https://gyazo.com/9a9da9c25f4063f99563c1fd5447ee6e
3つ目のいちごを見ていく
ここで、左に広げようとしたときに、すでに3列目は1つめのいちごの範囲となっているので、利用できない
https://gyazo.com/0fee8f7df9f38b9526d5390bb550c5da
https://gyazo.com/369449c6dd45d14629b7c65297985225
これで、最後までやる。
これで出したけど WA.iconがいくつか出た、、反例がわからない。。誰か教えて
解説を見て
いちごでなく、行単位で見ていく
まずいちごのある行だけを特定する、2,4,5行目がいちごをもつ
https://gyazo.com/4ef5f0ac21369bf1e4b8915ff549655d
今の行から次の行まで(先頭の場合は自分より前、最終行の場合は最後まで)を自分の範囲とする
https://gyazo.com/b8fa1a0d219188cc84f2531dab274409
それで、あとは2,4,5行目の各列を見て行って、いちごがある行から分けていけばいい
この時、みるのは黒枠で囲んだ行だけでいい(この行の範囲かつ、他の行はいちごがないことが保証されているから)
https://gyazo.com/7e8faf8744ee223510ec466710f0e607
これだと、かなり1次元的に考えれるので簡単
ただ、最初の行と最終行の処理とか、領域外アクセスには要注意(特に最初の行)
ここはコードにコメントで書いてるので見てみて
提出したコード
code: 計算量を落とした版.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
// 入力変数, グローバルに使うのでここで定義
int h,w,k;
vector<vector<char>> s(310, vector<char>(310));
// 出力用の変数
vector<vector<int>> ans(310, vector<int>(310, 0));
// いちごがある行を保持するvector
vector<int> has_s_line;
int solve(int line, int now) {
bool first_berry=false;
rep(j, w) {
if(s[has_s_lineline]j == '#') { if(!first_berry) first_berry=true;
else now++;
}
// 最初と最後だけ特殊な処理になる
if(line == 0) {
// 0行目にいちごがない可能性がある
// いちごが1つしかない場合の対応
if(has_s_line.size() == 1) {
for(int i=0; i<h; i++) {
}
} else {
for(int i=0; i<has_s_lineline+1; i++) { }
}
} else if(line == has_s_line.size()-1) {
// 次のlineが見れないので、hを直接いれる
for(int i=has_s_lineline; i<h; i++) { }
} else {
// 通常はline行にだけ、いちごがあるので、そこを見ればいい
for(int i=has_s_lineline; i<has_s_lineline+1; i++) { }
}
}
// 次の行にいくときにインクリメントする
now++;
return now;
}
int main() {
// 入力
cin >> h >> w >> k;
rep(i, h) rep(j, w) cin >> sij; // いちごがある行を求めていく
rep(i, h) rep(j, w) if(sij == '#') { has_s_line.push_back(i);
break;
}
// 現在のケーキの切り分けたケーキ番号を管理数r
int now = 1;
// 求める
rep(i, has_s_line.size()) {
now = solve(i, now);
}
// 出力, AtCoderでは改行=スペースなので、普通に全部改行でいい、
rep(i, h) rep(j, w) {
}
// 自分で確認用に見やすくした場合
// rep(i, h) {
// rep(j, w) {
// }
// cout << endl;
// }
return 0;
}
それから、AtCoderでは、出力のスペースと改行を区別しないので、こういう2次元配列の出力でも普通に改行でおkだよ
いつかのABCの解説動画でsunukeさんが言ってた、、実際に上のコードで通るよ