結果

問題 No.1397 Analog Graffiti
ユーザー evimaevima
提出日時 2021-02-05 08:51:43
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,168 ms / 10,000 ms
コード長 3,570 bytes
コンパイル時間 1,773 ms
コンパイル使用メモリ 172,148 KB
実行使用メモリ 84,736 KB
最終ジャッジ日時 2024-07-07 06:37:59
合計ジャッジ時間 12,165 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
15,616 KB
testcase_01 AC 8 ms
15,668 KB
testcase_02 AC 1,168 ms
84,692 KB
testcase_03 AC 8 ms
15,616 KB
testcase_04 AC 8 ms
15,616 KB
testcase_05 AC 1,165 ms
84,736 KB
testcase_06 AC 8 ms
15,616 KB
testcase_07 AC 8 ms
15,616 KB
testcase_08 AC 9 ms
15,616 KB
testcase_09 AC 8 ms
15,532 KB
testcase_10 AC 8 ms
15,744 KB
testcase_11 AC 1,143 ms
83,200 KB
testcase_12 AC 370 ms
40,320 KB
testcase_13 AC 1,114 ms
81,664 KB
testcase_14 AC 1,126 ms
82,036 KB
testcase_15 AC 39 ms
18,048 KB
testcase_16 AC 346 ms
38,912 KB
testcase_17 AC 1,040 ms
77,952 KB
testcase_18 AC 1,064 ms
78,976 KB
testcase_19 AC 16 ms
17,232 KB
testcase_20 AC 13 ms
16,128 KB
testcase_21 AC 36 ms
18,176 KB
testcase_22 AC 403 ms
39,856 KB
testcase_23 AC 22 ms
16,656 KB
testcase_24 AC 10 ms
15,860 KB
testcase_25 AC 63 ms
19,200 KB
testcase_26 AC 9 ms
15,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// Enjoy your stay. Code by evima on 2021/02/05

#include <bits/stdc++.h>

#define LOOPVAR_TYPE long

#define all(x) (x).begin(), (x).end()
#define sz(x) ((LOOPVAR_TYPE)(x).size())
#define foreach(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for(LOOPVAR_TYPE i = (LOOPVAR_TYPE)(a); i < (LOOPVAR_TYPE)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)

template<class T> bool tomin(T &a, const T &b) { return (b < a) ? (a = b, true) : false; }
template<class T> bool tomax(T &a, const T &b) { return (a < b) ? (a = b, true) : false; }

#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
const long INF = 1070000000LL;
const long MOD = 998244353LL;

using namespace std;

const int MR = 100, MC = 10, MN = 100;
const int B = MC / 2 + 2;
int R, C, N;
char ch[MR][MC + 1];

vector<int> int2baseB(int n){
    vector<int> ret;
    rep(i, C + 1){
        ret.eb(n % B);
        n /= B;
    }
    return ret;
}

int baseB2int(vector<int> v){
    int ret = 0;
    for(int i = C; i >= 0; --i){
        ret = ret * B + v[i];
    }
    return ret;
}

void normalize(vector<int>& v){
    int to[B + 1] = {}, num = 1;
    for(int& x: v){
        if(x){
            if(!to[x]){
                to[x] = num++;
            }
            x = to[x];
        }
    }
}

unordered_map<int, long> memo[MR + 1][MC + 1][MN + 1][2];
long f(int y, int x, int n, int flag, int state){
    if(n > N) return 0;
    auto it = memo[y][x][n][flag].find(state);
    if(it != memo[y][x][n][flag].end()){
        return it->sec;
    }
    long& ret = memo[y][x][n][flag][state];
    auto v = int2baseB(state);
    vector<int> cnt(B);
    for(int x: v) ++cnt[x];
    if(y == R){
        if(all_of(all(v), [](int x){ return x <= 1; })){
            int m = n + !!v[C];
            rep(i, C){
                m += !!v[i] ^ !!v[i + 1];
            }
            ret = m == N;
        }
    }else if(x == C){
        vector<int> nv(C + 1);
        copy(v.begin(), v.end() - 1, nv.begin() + 1);
        normalize(nv);
        ret = f(y + 1, 0, n + (!!v[C - 1] ^ !!v[C]), flag, baseB2int(nv));
    }else{
        // ab
        // c!
        int a = v[x], b = v[x + 1], c = x ? v[x - 1] : 0;
        int s = !!a + !!b + !!c;
        if(ch[y][x] != '#' && !(!a && b && c || b && cnt[b] == 1 && cnt[0] != C || a && b && cnt[b] == 2 && cnt[0] != C - 1)){    // .
            auto nv = v;
            nv[x] = 0;
            normalize(nv);
            ret += f(y, x + 1, n + s % 2, flag || b && cnt[b] == 1 || a && b && cnt[b] == 2, baseB2int(nv));
        }
        if(ch[y][x] != '.' && !flag && (!(a && !b && !c || !a && b && (b == c)))){   // #
            auto nv = v;
            if(!b && !c){
                nv[x] = B;
            }else if(b && c){
                nv[x] = b;
                rep(i, C + 1){
                    if(nv[i] == c){
                        nv[i] = b;
                    }
                }
            }else if(b){
                nv[x] = b;
            }else{  // c
                nv[x] = c;
            }
            normalize(nv);
            ret += f(y, x + 1, n + (s + 1) % 2, flag, baseB2int(nv));
        }
    }
    return ret %= MOD;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> R >> C >> N;
    cout << f(0, 0, 0, 0, 0) << endl;
}
0