#1033323 (C) No.3000 Optimal Run Length Encoding

提出ソース

結果

問題	No.3000 Optimal Run Length Encoding
ユーザー	👑 ygussany
提出日時	2024-12-25 23:06:03
言語	C (gcc 13.3.0)
結果	WA
実行時間	-
コード長	4,759 bytes
コンパイル時間	668 ms
コンパイル使用メモリ	35,044 KB
実行使用メモリ	184,480 KB
最終ジャッジ日時	2024-12-25 23:24:47
合計ジャッジ時間	1,117,412 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,496 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	TLE	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	TLE	-
testcase_46	TLE	-
testcase_47	TLE	-
testcase_48	TLE	-
testcase_49	TLE	-
testcase_50	TLE	-
testcase_51	TLE	-
testcase_52	TLE	-
testcase_53	TLE	-
testcase_54	TLE	-
testcase_55	TLE	-
testcase_56	TLE	-
testcase_57	TLE	-
testcase_58	TLE	-
testcase_59	TLE	-
testcase_60	TLE	-
testcase_61	TLE	-
testcase_62	TLE	-
testcase_63	TLE	-
testcase_64	TLE	-
testcase_65	TLE	-
testcase_66	TLE	-
testcase_67	TLE	-
testcase_68	TLE	-
testcase_69	TLE	-
testcase_70	TLE	-
testcase_71	TLE	-
testcase_72	TLE	-
testcase_73	TLE	-
testcase_74	TLE	-
testcase_75	TLE	-
testcase_76	TLE	-
testcase_77	TLE	-
testcase_78	TLE	-
testcase_79	TLE	-
testcase_80	TLE	-
testcase_81	AC	2,850 ms 44,032 KB
testcase_82	TLE	-
testcase_83	TLE	-
testcase_84	TLE	-
testcase_85	TLE	-
testcase_86	TLE	-
testcase_87	TLE	-
testcase_88	TLE	-
testcase_89	TLE	-
testcase_90	TLE	-
testcase_91	TLE	-
testcase_92	TLE	-
testcase_93	TLE	-
testcase_94	TLE	-
testcase_95	TLE	-
testcase_96	TLE	-
testcase_97	TLE	-
testcase_98	TLE	-
testcase_99	TLE	-
testcase_100	TLE	-
testcase_101	TLE	-
testcase_102	TLE	-
testcase_103	TLE	-
testcase_104	TLE	-
testcase_105	TLE	-
testcase_106	TLE	-
testcase_107	TLE	-
testcase_108	TLE	-
testcase_109	TLE	-
testcase_110	TLE	-
testcase_111	TLE	-
testcase_112	TLE	-
testcase_113	TLE	-
testcase_114	TLE	-
testcase_115	TLE	-
testcase_116	TLE	-
testcase_117	TLE	-
testcase_118	TLE	-
testcase_119	TLE	-
testcase_120	TLE	-
testcase_121	TLE	-
testcase_122	TLE	-
testcase_123	TLE	-
testcase_124	TLE	-
testcase_125	TLE	-
testcase_126	TLE	-
testcase_127	TLE	-
testcase_128	TLE	-
testcase_129	TLE	-
testcase_130	TLE	-
testcase_131	TLE	-
testcase_132	TLE	-
testcase_133	TLE	-
testcase_134	TLE	-
testcase_135	TLE	-
testcase_136	TLE	-
testcase_137	TLE	-
testcase_138	TLE	-
testcase_139	TLE	-
testcase_140	TLE	-
testcase_141	TLE	-
testcase_142	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

typedef struct HList {
	struct HList *next;
	int l, r, min, argmin[2];
} hlist;

#define HASH 5000011
const int H_Mod = HASH;
int hn;
hlist *hash[HASH] = {}, hd[10000001];

int hash_func(int l, int r)
{
	return (((long long)l << 30) + r) % H_Mod;
}

void Z_algorithm(char S[], int Z[])
{
	int i, j, k, l;
	for (l = 0; S[l] != 0; l++);
	Z[0] = l;
	for (i = 1, j = 0; i < l; i++) {
		for (; i + j < l && S[i+j] == S[j]; j++);
		Z[i] = j;
		if (j == 0) continue;
		
		for (k = 1; k < j && k + Z[k] < j; k++) Z[i+k] = Z[k];
		i += k - 1;
		j -= k;
	}
}

int recursion(char S[], int l, int r)
{
	if (r <= l) return 0;
	else if (r == l + 1) return 2;
	
	int h = hash_func(l, r);
	hlist *hp;
	for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->l == l && hp->r == r) return hp->min;
	hp = &(hd[hn++]);
	hp->l = l;
	hp->r = r;
	hp->min = r - l + 1;
	hp->argmin[0] = l;
	hp->argmin[1] = r;
	hp->next = hash[h];
	hash[h] = hp;
	
	int m = (l + r) / 2, tmp[2] = {recursion(S, l, m), recursion(S, m, r)};
	if (hp->min > tmp[0] + tmp[1]) {
		hp->min = tmp[0] + tmp[1];
		hp->argmin[0] = m;
		hp->argmin[1] = m;
	}
	
	int i, j, k, kk, kkk, ll, rr, *Z[2];
	char *T[2];
	T[0] = (char*)malloc(sizeof(char) * (m - l + 1));
	T[1] = (char*)malloc(sizeof(char) * (r - m + 1 + r - l + 1));
	Z[0] = (int*)malloc(sizeof(int) * (m - l + 1 + 1));
	Z[1] = (int*)malloc(sizeof(int) * (r - m + 1 + r - l + 1));
	for (i = 0, j = m - 1; j >= l; i++, j--) T[0][i] = S[j];
	T[0][i] = 0;
	Z[0][i] = 0;
	for (i = 0, j = m; j < r; i++, j++) T[1][i] = S[j];
	T[1][i++] = '#';
	for (j = l; j < r; i++, j++) T[1][i] = S[j];
	T[1][i] = 0;
	Z_algorithm(T[0], Z[0]);
	Z_algorithm(T[1], Z[1]);
	for (i = 1, j = m - l; i <= m - l && j >= 0; i++, j--) {
		k = Z[0][i] + Z[1][r-m+j] + i;
		if (k < i * 2) continue;
		for (kk = k / i, kkk = 0; kk > 0; kk /= 10, kkk++);
		kk = k / i * i;
		for (ll = m - i - Z[0][i], rr = ll + kk; rr <= m + Z[1][r-m+j]; ll++, rr++) {
			if (rr < m) continue;
			tmp[0] = recursion(S, l, ll);
			tmp[1] = recursion(S, rr, r);
			if (hp->min > tmp[0] + tmp[1] + i + kkk) {
				hp->min = tmp[0] + tmp[1] + i + kkk;
				hp->argmin[0] = ll;
				hp->argmin[1] = rr;
			}
		}
	}
	free(T[0]);
	free(T[1]);
	free(Z[0]);
	free(Z[1]);
	
	T[0] = (char*)malloc(sizeof(char) * (r - m + 1));
	T[1] = (char*)malloc(sizeof(char) * (m - l + 1 + r - l + 1));
	Z[0] = (int*)malloc(sizeof(int) * (r - m + 1 + 1));
	Z[1] = (int*)malloc(sizeof(int) * (m - l + 1 + r - l + 1));
	for (i = 0, j = m; j < r; i++, j++) T[0][i] = S[j];
	T[0][i] = 0;
	Z[0][i] = 0;
	for (i = 0, j = m - 1; j >= l; i++, j--) T[1][i] = S[j];
	T[1][i++] = '#';
	for (j = r - 1; j >= l; i++, j--) T[1][i] = S[j];
	T[1][i] = 0;
	Z_algorithm(T[0], Z[0]);
	Z_algorithm(T[1], Z[1]);
	for (i = 1, j = r - m; i <= r - m && j >= 0; i++, j--) {
		k = Z[0][i] + Z[1][m-l+j] + i;
		if (k < i * 2) continue;
		for (kk = k / i, kkk = 0; kk > 0; kk /= 10, kkk++);
		kk = k / i * i;
		for (rr = m + i + Z[0][i], ll = rr - kk; ll >= m - Z[1][m-l+j]; ll--, rr--) {
			if (ll > m) continue;
			tmp[0] = recursion(S, l, ll);
			tmp[1] = recursion(S, rr, r);
			if (hp->min > tmp[0] + tmp[1] + i + kkk) {
				hp->min = tmp[0] + tmp[1] + i + kkk;
				hp->argmin[0] = ll;
				hp->argmin[1] = rr;
			}
		}
	}
	free(T[0]);
	free(T[1]);
	free(Z[0]);
	free(Z[1]);
	// printf("%d %d: %d %d %d\n", l, r, hp->min, hp->argmin[0], hp->argmin[1]);
	return hp->min;
}

void recover(char S[], int l, int r, char ans[])
{
	if (r <= l) return;
	else if (r == l + 1) {
		ans[0] = S[l];
		ans[1] = '1';
		return;
	}
	
	int h = hash_func(l, r), i, j, k = 0, kk;
	char tmp[10];
	hlist *hp;
	for (hp = hash[h]; hp != NULL; hp = hp->next) if (hp->l == l && hp->r == r) break;
	if (hp->argmin[0] > l) {
		recover(S, l, hp->argmin[0], ans);
		k = recursion(S, l, hp->argmin[0]);
	}
	if (hp->argmin[0] < hp->argmin[1]) {
		for (i = 1; i < hp->argmin[1] - hp->argmin[0]; i++) {
			if ((hp->argmin[1] - hp->argmin[0]) % i != 0) continue;
			for (j = hp->argmin[0] + i; j < hp->argmin[1]; j++) if (S[j] != S[j-i]) break;
			if (j == hp->argmin[1]) break;
		}
		for (j = 0; j < i; j++) ans[k++] = S[hp->argmin[0] + j];
		for (j = (hp->argmin[1] - hp->argmin[0]) / i, kk = 0; j > 0; j /= 10, kk++) tmp[kk] = '0' + j % 10;
		while (kk--) ans[k++] = tmp[kk];
	}
	if (hp->argmin[1] < r) recover(S, hp->argmin[1], r, &(ans[k]));
}

void solve(char S[], char ans[])
{
	int h, i, l, min;
	for (l = 0, hn = 0; S[l] != 0; l++);
	min = recursion(S, 0, l);
	recover(S, 0, l, ans);
	ans[min] = 0;
	for (i = 0; i < hn; i++) hash[hash_func(hd[i].l, hd[i].r)] = NULL;
}

int main()
{
	int T;
	char S[500001], ans[500003];
	scanf("%d", &T);
	while (T--) {
		scanf("%s", S);
		solve(S, ans);
		printf("%s\n", ans);
	}
	fflush(stdout);
	return 0;
}

yukicoder

結果

テストケース

ソースコード