AtCoderを始めて思うのは、解法は合っているのに実装を間違えて不正解になることが多いので、これをどうしたらいいかということです。
実際にコンテストに参加すると、不正解だとしてもどんなテストケースに対して不正解なのかわからないので、どこが間違っているのか見当をつけるのがまず難しい。
ほとんどのテストケースは正解して一部だけ不正解の場合は、解法は正しく後は詰めの問題だと思うのですが、そこから正解に持っていくのが結構大変だったりします。
こればかりは経験を積むしかないのでしょうか。
今回は昨日のARC 120の問題です。
悩みましたが、以下の図のアルファベットで分けられたマスについて、それぞれのアルファベットのマスの組に対して高々1マスしか通らないことに気付きました。
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | a | b | c | d |
| 2 | b | c | d | e |
| 3 | c | d | e | f |
| 4 | d | e | f | g |
上の図だと、$(1, 1)$ から $(4, 4)$ に移動するには、例えば $c$ のマスは3個のうちのどれか1個しか通れません。他のアルファベットも同様です。
そしてそれぞれの組に対して、全て赤か全て青でないといけません。
とすると解答の初期値を1として、あるアルファベットのマスの組に対して以下の条件で答えが導き出せます。
- 赤マスと青マスの両方が存在するならば条件を満たさないので0。
- 色が塗られてないマスと赤マスのみの場合は塗られてないマスは全て赤に塗る。したがって赤1通り。
- 同様に色が塗られてないマスと青マスのみの場合は塗られてないマスは全て青に塗る。したがって青1通り。
- 赤マスも青マスもなく全てが色が塗られてないマスの場合は全て赤に塗るか全て青に塗るかの2通りなので、解答を2倍する。
これを全てのアルファベットのマスの組に対して行います。
この解法で実装したのですが、数問だけ不正解になってしまいました。
マスを調べるときのループがおかしいのだろうと予想しましたが、どうしてもわからなかったので後で解説を読みました。
解法の大まかな筋は自分と同じで、ただ自分がアルファベットで分けたマスの組に対して、
解説では行数を $i$ 、列数を $j$ とした場合にそれぞれのマスの $i + j$ が等しいという共通点を見つけて解いてました。
その解説を参考に自分のソースコードを修正したら一発で正解しました。。
しかも最初に書いたものよりもかなりシンプルになって、実装のセンスの無さに凹んでいます。。。
その正解したソースコードが以下です。
言語はC++(GCC 9.2.1)でAtCoderのコードテストで確認しています。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int H, W;
cin >> H >> W;
vector<string> S(H);
vector<int> RCount(H+W-1, 0), BCount(H+W-1, 0), ECount(H+W-1, 0);
ll ans = 1, m = 998244353;
for (int i = 0; i < H; i++) {
cin >> S[i];
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (S[i][j] == 'R') RCount[i+j]++;
else if (S[i][j] == 'B') BCount[i+j]++;
else if (S[i][j] == '.') ECount[i+j]++;
}
}
for (int i = 0; i < H+W-1; i++) {
if (RCount[i] && BCount[i]) {
ans = 0;
break;
} else if (!RCount[i] && !BCount[i] && ECount[i]) {
ans *= 2;
}
ans = ans % m;
}
cout << ans << endl;
}