(cache)Submission #73347847 - 2009年日本情報オリンピック春合宿OJ

Contest Duration: 2009-03-20(Fri) 09:00 - 2009-03-20(Fri) 09:00 (local time) (0 minutes) Back to Home

Submission #73347847

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 N;
char eizinoretu[512];
int colors[512];
int memo[512][512][64];
int calc(int start, int end, int color) {
  int ans = 9999, candidate, i;
  int start2, end2;
  if (start == end) return colors[start] != color;
  if (memo[start][end][color]) return ~memo[start][end][color];
  /* 端から同じ色の部分を調べる */
  for (start2 = start; start2 <= end && colors[start2] == colors[start]; start2++);
  for (end2 = end; end2 >= start && colors[end2] == colors[end]; end2--);
  if (start2 > end) {
    /* 対象範囲全体が同じ色 → 全部塗って終わり */
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int N;
char eizinoretu[512];

int colors[512];

int memo[512][512][64];

int calc(int start, int end, int color) {
	int ans = 9999, candidate, i;
	int start2, end2;
	if (start == end) return colors[start] != color;
	if (memo[start][end][color]) return ~memo[start][end][color];

	/* 端から同じ色の部分を調べる */
	for (start2 = start; start2 <= end && colors[start2] == colors[start]; start2++);
	for (end2 = end; end2 >= start && colors[end2] == colors[end]; end2--);

	if (start2 > end) {
		/* 対象範囲全体が同じ色 → 全部塗って終わり */
		ans = colors[start] != color;
	} else if (colors[start] == colors[end]) {
		/* 両端が同じ色 → 両端を削る */
		ans = calc(start2, end2, colors[start]);
		for (i = start2 + 1; i <= end2; i++) {
			candidate = calc(start2, i - 1, colors[start]) + calc(i, end2, colors[start]);
			if (candidate < ans) ans = candidate;
		}
		ans += colors[start] != color;
	} else {
		/* 両端が違う色 */
		/* 左端を削る */
		ans = calc(start2, end, colors[start]);
		for (i = start2 + 1; i <= end; i++) {
			candidate = calc(start2, i - 1, colors[start]) + calc(i, end, colors[start]);
			if (candidate < ans) ans = candidate;
		}
		ans += colors[start] != color;
#if 0
		/* 右端を削る */
		candidate = calc(start, end2, colors[end]) + (colors[end] != color);
		if (candidate < ans) ans = candidate;
		for (i = start + 1; i <= end2; i++) {
			candidate = calc(start, i - 1, colors[end]) + calc(i, end2, colors[end]) + (colors[end] != color);
			if (candidate < ans) ans = candidate;
		}
#endif
	}

	return ~(memo[start][end][color] = ~ans);
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	if (scanf("%511s", eizinoretu) != 1) return 1;
	for (i = 0; i < N; i++) {
		char c = eizinoretu[i];
		if ('A' <= c && c < 'A' + 26) colors[i] = c - 'A';
		else if ('a' <= c && c < 'a' + 26) colors[i] = c - 'a' + 26;
		else c = 52;
	}
	printf("%d\n", calc(0, N - 1, 53));
	return 0;
}

Submission Info

Submission Time	2026-02-15 17:36:25
Task	chopsticks - 塗り箸 (Chopsticks)
User	mikecat
Language	C23 (GCC 14.2.0)
Score	100
Code Size	2059 Byte
Status	AC
Exec Time	415 ms
Memory	13828 KiB

Judge Result

Set Name

Set01

Set02

Set03

Set04

Set05

Set06

Set07

Set08

Set09

Set10

Set11

Set12

Set13

Set14

Set15

Set16

Set17

Set18

Set19

Set20

Set21

Set22

Set23

Set24

Set25

Score / Max Score

4 / 4

Status

× 2

Set Name	Test Cases
Set01	01, 02
Set02	03, 04
Set03	05, 06
Set04	07, 08
Set05	09, 10
Set06	11, 31
Set07	12, 32
Set08	13, 33
Set09	14, 34
Set10	15, 35
Set11	16, 36
Set12	17, 37
Set13	18, 38
Set14	19, 39
Set15	20, 40
Set16	21, 41
Set17	22, 42
Set18	23, 43
Set19	24, 44
Set20	25, 45
Set21	26, 46
Set22	27, 47
Set23	28, 48
Set24	29, 49
Set25	30, 50

Case Name	Status	Exec Time	Memory
01	AC	1 ms	1688 KiB
02	AC	0 ms	1628 KiB
03	AC	0 ms	1712 KiB
04	AC	0 ms	1924 KiB
05	AC	0 ms	1756 KiB
06	AC	0 ms	1756 KiB
07	AC	0 ms	1840 KiB
08	AC	0 ms	1756 KiB
09	AC	0 ms	1872 KiB
10	AC	1 ms	1764 KiB
11	AC	1 ms	2268 KiB
12	AC	1 ms	2384 KiB
13	AC	1 ms	2192 KiB
14	AC	1 ms	2436 KiB
15	AC	1 ms	2436 KiB
16	AC	17 ms	5052 KiB
17	AC	35 ms	7388 KiB
18	AC	26 ms	7388 KiB
19	AC	18 ms	7388 KiB
20	AC	11 ms	7448 KiB
21	AC	9 ms	7388 KiB
22	AC	10 ms	7260 KiB
23	AC	49 ms	7472 KiB
24	AC	42 ms	7388 KiB
25	AC	11 ms	7268 KiB
26	AC	47 ms	7428 KiB
27	AC	51 ms	7448 KiB
28	AC	48 ms	7472 KiB
29	AC	40 ms	7356 KiB
30	AC	49 ms	7436 KiB
31	AC	4 ms	2704 KiB
32	AC	6 ms	3468 KiB
33	AC	10 ms	3504 KiB
34	AC	14 ms	3856 KiB
35	AC	14 ms	3936 KiB
36	AC	183 ms	10212 KiB
37	AC	193 ms	10128 KiB
38	AC	155 ms	10128 KiB
39	AC	192 ms	10252 KiB
40	AC	197 ms	10204 KiB
41	AC	27 ms	13536 KiB
42	AC	386 ms	13660 KiB
43	AC	366 ms	13584 KiB
44	AC	355 ms	13660 KiB
45	AC	370 ms	13744 KiB
46	AC	365 ms	13828 KiB
47	AC	382 ms	13700 KiB
48	AC	382 ms	13744 KiB
49	AC	357 ms	13664 KiB
50	AC	415 ms	13720 KiB