結果

問題 No.1654 Binary Compression
コンテスト
ユーザー startcpp
提出日時 2021-08-21 00:54:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,712 bytes
コンパイル時間 587 ms
コンパイル使用メモリ 67,764 KB
実行使用メモリ 253,396 KB
最終ジャッジ日時 2024-10-14 09:37:07
合計ジャッジ時間 27,598 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

//区間と1文字マッチ, 文字列tにできるか？は貪欲できるが「next next文字」までの場合分けが入る。
//これをdpに落とすには、ネクネクまで持てばよい。ぷよぷよか↑？
#include <iostream>
#include <string>
//#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

const int mod = 924844033;
string s;
int ssum[3000001];	//ssum[i] = 先頭i桁の和
int next_zero[3000001];	//next_zero[i] = s[i]以降で初めて'0'が現れる場所（s[i]自身ならi, 最後まで0ならn）
int next_one[3000001];	//next_one[i] = s[i]以降で初めて'1'が現れる場所（s[i]自信ならi, 最後まで0ならn）
int n;
int dp[3000001][2][3][3];	//dp[index][now][next][next next]. 終了（受理状態）はdp[n][0][2][2]とする。

bool all_zero(int l, int r) {
	//for (int i = l; i < r; i++) if (s[i] == '1') return false;
	//return true;
	return ssum[r] - ssum[l] == 0;
}

bool exist_one(int l, int r) {
	//for (int i = l; i < r; i++) if (s[i] == '1') return true;
	//return false;
	return ssum[r] - ssum[l] > 0;
}

int find_zero_prev_one(int l) {
	//int i;
	//for (i = l; i < n - 1; i++) if (s[i] == '1' && s[i + 1] == '0') break;
	//return i + 1;
	return next_zero[next_one[l]];
}

int find_one_next(int l) {
	//int i;
	//for (i = l; i < n; i++) if (s[i] == '1') break;
	//return i + 1;
	return next_one[l] + 1;
}

signed main() {
	int i, now, nxt, nnxt, j;
	
	cin >> s;
	n = s.length();
	
	ssum[0] = 0;
	rep(i, n) {
		ssum[i + 1] = ssum[i] + (s[i] == '1');
	}
	
	next_zero[n] = n;
	for (i = n - 1; i >= 0; i--) {
		if (s[i] == '0') {
			next_zero[i] = i;
		}
		else {
			next_zero[i] = next_zero[i + 1];
		}
	}
	
	next_one[n] = n;
	for (i = n - 1; i >= 0; i--) {
		if (s[i] == '1') {
			next_one[i] = i;
		}
		else {
			next_one[i] = next_one[i + 1];
		}
	}
	
	rep(now, 2) {
		rep(nxt, 3) {
			rep(nnxt, 3) {
				if (nxt == 2 && nnxt != 2) continue;
				dp[0][now][nxt][nnxt] = 1;
			}
		}
	}
	
	rep(i, n) {
		rep(now, 2) {
			rep(nxt, 3) {
				rep(nnxt, 3) {
					int val = dp[i][now][nxt][nnxt];
					if (val == 0) continue;
					if (now == 0) {
						if (nxt == 0 || nxt == 1) {
							if (i + 1 < n && s[i] == '0') {
								rep(j, 3) {
									if (nnxt == 2 && j != 2) continue;
									dp[i + 1][nxt][nnxt][j] += val;
									if (dp[i + 1][nxt][nnxt][j] >= mod) {
										dp[i + 1][nxt][nnxt][j] -= mod;
									}
								}
							}
						}
						else {
							if (all_zero(i, n)) {
								dp[n][0][2][2] += val;
								if (dp[n][0][2][2] >= mod) {
									dp[n][0][2][2] -= mod;
								}
							}
						}
					}
					else {
						if (nxt == 0) {
							if (nnxt == 0 || nnxt == 1) {
								int pos = find_zero_prev_one(i);
								if (pos < n) {
									rep(j, 3) {
										dp[pos][nxt][nnxt][j] += val;
										if (dp[pos][nxt][nnxt][j] >= mod) {
											dp[pos][nxt][nnxt][j] -= mod;
										}
									}
								}
							}
							else {
								if (exist_one(i, n - 1)) {
									dp[n - 1][nxt][nnxt][2] += val;
									if (dp[n - 1][nxt][nnxt][2] >= mod) {
										dp[n - 1][nxt][nnxt][2] -= mod;
									}
								}
							}
						}
						else if (nxt == 1) {
							int pos = find_one_next(i);
							if (pos < n) {
								rep(j, 3) {
									if (nnxt == 2 && j != 2) continue;
									dp[pos][nxt][nnxt][j] += val;
									if (dp[pos][nxt][nnxt][j] >= mod) {
										dp[pos][nxt][nnxt][j] -= mod;
									}
								}
							}
						}
						else {
							if (exist_one(i, n)) {
								dp[n][0][2][2] += val;
								if (dp[n][0][2][2] >= mod) {
									dp[n][0][2][2] -= mod;
								}
							}
						}
					}
				}
			}
		}
	}
	
	cout << dp[n][0][2][2] << endl;
	return 0;
}
0