結果

問題 No.3114 0→1
ユーザー ねしん
提出日時 2025-04-18 22:53:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 826 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 110,604 KB
最終ジャッジ日時 2025-04-18 22:53:51
合計ジャッジ時間 4,804 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())
S=input()
if N==1:
	print(1-int(S))
	exit()
if N==2:
	if S=="00":
		print(1)
	else:
		print(0)
	exit()
dp=[]
for i in range(N+1):
	dp.append([10**18]*8)
ok=set([3,5,6,7])
s=S[:3]
if s=="000":
	dp[3][3]=2
	dp[3][5]=2
	dp[3][6]=2
	dp[3][7]=3
elif s=="001":
	dp[3][3]=1
	dp[3][5]=1
	dp[3][7]=2
elif s=="010":
	dp[3][3]=1
	dp[3][6]=1
	dp[3][7]=1
elif s=="011":
	dp[3][3]=0
	dp[3][7]=1
elif s=="100":
	dp[3][5]=1
	dp[3][6]=1
	dp[3][7]=2
elif s=="101":
	dp[3][5]=0
	dp[3][7]=1
elif s=="110":
	dp[3][6]=0
	dp[3][7]=1
else:
	dp[3][7]=0
for i in range(3,N):
	if S[i]=="1":
		for j in ok:
			dp[i+1][(2*j+1)%8]=min(dp[i+1][(2*j+1)%8],dp[i][j])
	else:
		for j in ok:
			dp[i+1][(2*j)%8]=min(dp[i+1][(2*j)%8],dp[i][j])
			dp[i+1][(2*j+1)%8]=min(dp[i+1][(2*j+1)%8],dp[i][j]+1)
print(min(dp[N][3],dp[N][5],dp[N][6],dp[N][7]))
0