#689189 (C) No.1646 Avoid Palindrome

提出ソース

結果

問題	No.1646 Avoid Palindrome
ユーザー	pengin_2000
提出日時	2021-08-13 22:10:44
言語	C (gcc 12.3.0)
結果	AC
実行時間	1,833 ms / 3,000 ms
コード長	1,444 bytes
コンパイル時間	397 ms
コンパイル使用メモリ	33,020 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-26 02:58:38
合計ジャッジ時間	40,714 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	888 ms 5,376 KB
testcase_05	AC	876 ms 5,376 KB
testcase_06	AC	870 ms 5,376 KB
testcase_07	AC	868 ms 5,376 KB
testcase_08	AC	922 ms 5,376 KB
testcase_09	AC	824 ms 5,376 KB
testcase_10	AC	883 ms 5,376 KB
testcase_11	AC	830 ms 5,376 KB
testcase_12	AC	925 ms 5,376 KB
testcase_13	AC	882 ms 5,376 KB
testcase_14	AC	1,705 ms 5,376 KB
testcase_15	AC	1,759 ms 5,376 KB
testcase_16	AC	1,714 ms 5,376 KB
testcase_17	AC	1,766 ms 5,376 KB
testcase_18	AC	1,727 ms 5,376 KB
testcase_19	AC	1,672 ms 5,376 KB
testcase_20	AC	1,663 ms 5,376 KB
testcase_21	AC	1,807 ms 5,376 KB
testcase_22	AC	1,678 ms 5,376 KB
testcase_23	AC	1,707 ms 5,376 KB
testcase_24	AC	1,805 ms 5,376 KB
testcase_25	AC	1,772 ms 5,376 KB
testcase_26	AC	1,780 ms 5,376 KB
testcase_27	AC	1,797 ms 5,376 KB
testcase_28	AC	1,833 ms 5,376 KB
testcase_29	AC	338 ms 5,376 KB
testcase_30	AC	329 ms 5,376 KB
testcase_31	AC	312 ms 5,376 KB
testcase_32	AC	320 ms 5,376 KB
testcase_33	AC	330 ms 5,376 KB
testcase_34	AC	1,779 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	1 ms 5,376 KB
testcase_38	AC	1 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB
testcase_40	AC	1 ms 5,376 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	0 ms 5,376 KB
testcase_43	AC	318 ms 5,376 KB

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

ソースコード

raw source code

#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	char s[50004];
	scanf("%s", s);
	if (n == 1)
	{
		if (s[0] == '?')
			printf("26\n");
		else
			printf("1\n");
		return 0;
	}
	int i, j, k, l;
	long long int p = 998244353;
	long long int dp[2][26][26];
	for (i = 0; i < 26; i++)
		for (j = 0; j < 26; j++)
			dp[0][i][j] = 0;
	if (s[0] == '?' && s[1] == '?')
	{
		for (i = 0; i < 26; i++)
			for (j = 0; j < 26; j++)
				dp[0][i][j] = 1;
	}
	else if (s[1] == '?')
	{
		for (j = 0; j < 26; j++)
			dp[0][s[0] - 'a'][j] = 1;
	}
	else if (s[0] == '?')
	{
		for (i = 0; i < 26; i++)
			dp[0][i][s[1] - 'a'] = 1;
	}
	else
	{
		dp[0][s[0] - 'a'][s[1] - 'a'] = 1;
	}
	for (i = 0; i < 26; i++)
		dp[0][i][i] = 0;
	for (i = 2; i < n; i++)
	{
		for (j = 0; j < 26; j++)
			for (k = 0; k < 26; k++)
				dp[1][j][k] = 0;
		if (s[i] == '?')
		{
			for (j = 0; j < 26; j++)
				for (k = 0; k < 26; k++)
					for (l = 0; l < 26; l++)
						if (l != j && l != k)
							dp[1][k][l] = (dp[1][k][l] + dp[0][j][k]) % p;
		}
		else
		{
			for (j = 0; j < 26; j++)
			{
				for (k = 0; k < 26; k++)
				{
					l = s[i] - 'a';
					if (l != j && l != k)
						dp[1][k][l] = (dp[1][k][l] + dp[0][j][k]) % p;
				}
			}
		}
		for (j = 0; j < 26; j++)
			for (k = 0; k < 26; k++)
				dp[0][j][k] = dp[1][j][k];
	}
	long long int ans = 0;
	for (i = 0; i < 26; i++)
		for (j = 0; j < 26; j++)
			ans = (ans + dp[0][i][j]) % p;
	printf("%lld\n", ans);
	return 0;
}

yukicoder

結果

テストケース

ソースコード