(cache)Submission #69695960 - AtCoder Beginner Contest 424

Contest Duration: 2025-09-20(Sat) 21:00 - 2025-09-20(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #69695960

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int H, W;
char S[8][8];
int gen;
int memo_gen[7][7][1 << 8];
int memo[7][7][1 << 8];
int calc(int y, int x, int status) {
  int ans;
  if (x >= W) return calc(y + 1, 0, status);
  if (y >= H) return 0;
  if (memo_gen[y][x][status] == gen) return memo[y][x][status];
  /* 白にする */
  ans = calc(y, x + 1, (status << 1) & ((1 << (W + 1)) - 1)) + (S[y][x] == '#');
  /* 黒にする */
  if (
    S[y][x] == '#' && (
      x == 0 ||
      (status & 1) != 1 ||
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int H, W;
char S[8][8];

int gen;
int memo_gen[7][7][1 << 8];
int memo[7][7][1 << 8];

int calc(int y, int x, int status) {
	int ans;
	if (x >= W) return calc(y + 1, 0, status);
	if (y >= H) return 0;
	if (memo_gen[y][x][status] == gen) return memo[y][x][status];
	/* 白にする */
	ans = calc(y, x + 1, (status << 1) & ((1 << (W + 1)) - 1)) + (S[y][x] == '#');
	/* 黒にする */
	if (
		S[y][x] == '#' && (
			x == 0 ||
			(status & 1) != 1 ||
			(status >> (W - 1)) != 3
		)
	) {
		int candidate = calc(y, x + 1, ((status << 1) | 1) & ((1 << (W + 1)) - 1));
		if (candidate < ans) ans = candidate;
	}
	memo[y][x][status] = ans;
	memo_gen[y][x][status] = gen;
	return ans;
}

int main(void) {
	int T;
	if (scanf("%d", &T) != 1) return 1;
	for (gen = 1; gen <= T; gen++) {
		int i;
		if (scanf("%d%d", &H, &W) != 2) return 1;
		for (i = 0; i < H; i++) {
			if (scanf("%7s", S[i]) != 1) return 1;
		}
		printf("%d\n", calc(0, 0, 0));
	}
	return 0;
}

/*

.......
.######
##?....
.......

? を決める → ? の位置と # の状態 (幅+1 個) でメモ化探索

*/

Submission Info

Submission Time	2025-09-28 09:05:34
Task	D - 2x2 Erasing 2
User	mikecat
Language	C (gcc 12.2.0)
Score	425
Code Size	1148 Byte
Status	AC
Exec Time	9 ms
Memory	1852 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 1

× 27

Set Name	Test Cases
Sample	example_00.txt
All	example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt

Case Name	Status	Exec Time	Memory
example_00.txt	AC	1 ms	1828 KiB
hand_00.txt	AC	9 ms	1796 KiB
hand_01.txt	AC	0 ms	1728 KiB
hand_02.txt	AC	2 ms	1676 KiB
hand_03.txt	AC	1 ms	1712 KiB
hand_04.txt	AC	9 ms	1720 KiB
hand_05.txt	AC	0 ms	1664 KiB
random_00.txt	AC	1 ms	1692 KiB
random_01.txt	AC	1 ms	1852 KiB
random_02.txt	AC	1 ms	1728 KiB
random_03.txt	AC	1 ms	1800 KiB
random_04.txt	AC	1 ms	1700 KiB
random_05.txt	AC	1 ms	1796 KiB
random_06.txt	AC	3 ms	1680 KiB
random_07.txt	AC	3 ms	1820 KiB
random_08.txt	AC	3 ms	1832 KiB
random_09.txt	AC	4 ms	1736 KiB
random_10.txt	AC	2 ms	1752 KiB
random_11.txt	AC	5 ms	1808 KiB
random_12.txt	AC	5 ms	1796 KiB
random_13.txt	AC	5 ms	1732 KiB
random_14.txt	AC	5 ms	1824 KiB
random_15.txt	AC	2 ms	1696 KiB
random_16.txt	AC	5 ms	1816 KiB
random_17.txt	AC	5 ms	1796 KiB
random_18.txt	AC	5 ms	1820 KiB
random_19.txt	AC	5 ms	1696 KiB