Submission #74440344

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#define MOD_BY 100000
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int M, N;
char mozi[24][24];
int next_status(int status, char current_char) {
  int res = status << 1;
  res &= (1 << N) - 1;
  if (current_char != 'O') res &= ~2;
  res |= current_char == 'J';
  return res;
}
int pcnt;
int putterns[18000];
void get_putterns(void) {
  int i;
  pcnt = 0;
  for (i = 0; i < (1 << N); i++) {
    int ok = 1, cur = i;
    while (cur > 0) {
      if ((cur & 3) == 3) {
        ok = 0;
        break;
      }
      cur >>= 1;
    }
    if (ok) {
      if (pcnt >= (int)(sizeof(putterns) / sizeof(*putterns))) {
        puts("ERROR: too many putterns!");
        exit(72);
      }
      putterns[pcnt++] = i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

#define MOD_BY 100000

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int M, N;
char mozi[24][24];

int next_status(int status, char current_char) {
	int res = status << 1;
	res &= (1 << N) - 1;
	if (current_char != 'O') res &= ~2;
	res |= current_char == 'J';
	return res;
}

int pcnt;
int putterns[18000];

void get_putterns(void) {
	int i;
	pcnt = 0;
	for (i = 0; i < (1 << N); i++) {
		int ok = 1, cur = i;
		while (cur > 0) {
			if ((cur & 3) == 3) {
				ok = 0;
				break;
			}
			cur >>= 1;
		}
		if (ok) {
			if (pcnt >= (int)(sizeof(putterns) / sizeof(*putterns))) {
				puts("ERROR: too many putterns!");
				exit(72);
			}
			putterns[pcnt++] = i;
		}
	}
}

int get_key(int puttern) {
	int l = 0, r = pcnt - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (putterns[m] == puttern) return m;
		else if (putterns[m] < puttern) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: %d not found!\n", puttern);
	exit(42);
}

int memo[20][20][2][18000];

int calc(int y, int x, int ok, int status) {
	int *pmemo = &memo[y][x][ok][get_key(status)];
	int ans = 0;
	int i;
	if (x >= N) return calc(y + 1, 0, ok, status);
	if (y >= M) return ok;
	if (*pmemo) return ~*pmemo;
	for (i = 0; i < 3; i++) {
		char c = "JOI"[i];
		if (mozi[y][x] == '?' || mozi[y][x] == c) {
			int yeah = (status >> (N - 1)) && c == 'I' && x != N - 1;
			ans = add(ans, calc(y, x + 1, ok || yeah, next_status(status, c)));
		}
	}
	return ~(*pmemo = ~ans);
}

int solve(void) {
	return calc(0, 0, 0, 0);
}

int main(void) {
	int i;
	if (scanf("%d%d", &M, &N) != 2) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%23s", mozi[i]) != 1) return 1;
	}
	get_putterns();
	printf("%d\n", solve());
	return 0;
}

/*

[位置][条件OK][上1行分の状態]でメモ化？
→「上1行分の状態」を普通に J/O/I でやると、3**20 = 3,486,784,401 これは死
それぞれの位置がリーチ (JO) になっているかだけを管理 2**20 = 1,048,576 いけそうか？

[Y][X][OK][リーチフラグ][1個前がJ]
直前(1個しかない)が JO になることはないので、ここだけ「J」として使う

[Y][X][OK][リーチフラグ / 1個前がJ]

条件判定：状態の下から N ビット目 (1-origin) が 1 && 今回 I を置く → OK
↑「今右端でない」も必要

JO 判定は、右端を弾かなくてもよい (条件判定で蹴れるため) (ただしサボると定数倍不利に？)

他のところもあるので、2**20 でも死
リーチフラグは2ビット連続で1にならないので、あり得るパターンのみ割り当てる
→ 最大でやっても 17711 だった

20 20
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????
????????????????????

*/

Submission Info

Judge Result