結果

問題 No.3114 0→1
ユーザー sasa8uyauya
提出日時 2025-04-19 14:53:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 622 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 94,980 KB
最終ジャッジ日時 2025-04-19 14:53:42
合計ジャッジ時間 4,538 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
s=list(map(int,list(input())))
if n<=2:
  print(0 if sum(s)>0 else 1)
  exit()
X=n
q=[X]*4
for p2 in [0,1]:
  for p3 in [0,1]:
    if p2==p3==0:
      continue
    if (p3*2+p2)&(s[0]*2+s[1])==(s[0]*2+s[1]):
      q[p3*2+p2]=p3-s[0]+p2-s[1]
for p1 in s[2:]:
  nq=[X]*4
  if p1:
    for p2 in [0,1]:
      for p3 in [0,1]:
        if p2==p3==0:
          continue
        nq[p2*2+p1]=min(nq[p2*2+p1],q[p3*2+p2])
  else:
    nq[p2*2+0]=min(nq[p2*2+0],q[3])
    for p2 in [0,1]:
      for p3 in [0,1]:
        if p2==p3==0:
          continue
        nq[p2*2+1]=min(nq[p2*2+1],q[p3*2+p2]+1)
  q=nq
print(min(q))
0