programming

AtCoder Grand Contest 049 ใƒฌใƒ“ใƒฅใƒผ

AGC049ใฎๆŒฏใ‚Š่ฟ”ใ‚Š

You can share this article with

็ตๆžœ

Ratedใงใฏใชใ„ใฎใงใƒฌใƒผใƒˆๅค‰ๅ‹•ใฏใ‚ใ‚Šใพใ›ใ‚“ใŒใ€0ๅฎŒใงใ™ใ€‚ ไธ€ๅฟœใ€AใจBใฎใ‚ตใƒณใƒ—ใƒซใพใงใฏ้€šใ—ใŸใฎใง 600 ็‚นใงใ‚‚ๅ•้กŒๆ–‡ใฎ็†่งฃใจๆ„š็›ด่งฃใฎๅฎŸ่ฃ…ใฏๅ‡บๆฅใ‚‹ใ‚ˆใ†ใซใชใฃใฆใ„ใพใ™ใ€‚

ใŸใ ใ€่จˆ็ฎ—้‡ใ‚’่ฝใจใ™ๆ–นๆณ•ใฏๆ€ใ„ไป˜ใ‘ใพใ›ใ‚“ใงใ—ใŸใ€‚
ๅ‚ๅŠ ใ‚‚1ๆ™‚้–“้…ใ‚Œใ€ใ—ใฐใ‚‰ใ่€ƒๅฏŸใƒปๅฎŸ่ฃ…ใ—ใฆใฟใ‚‹ใ‚‚ใ€Œใ‚‚ใ†ใ“ใ‚Œใฏ0ๅฎŒใ ใ€ใจๆ‚Ÿใ‚Šใ€ๆŒ™ๅฅใฎๆžœใฆใซใ‚ณใƒณใƒ†ใ‚นใƒˆไธญใซ้ฃฒ้…’ใ—ๅง‹ใ‚ใ‚‹ใจใ„ใ†ๆœ‰ๆง˜ใงใ—ใŸใ€‚

ใ“ใ‚Œใพใงใ‚„ใฃใŸใ“ใจ

  • AOJใฎITP1ใ‚’C++ใงๅฎŒ่ตฐใ—ใŸ
  • paizaใฎDๅ•้กŒใ‚’Pythonใง162ๅ•ใœใ‚“ใถๅŸ‹ใ‚ใŸ
  • paizaใงSใƒฉใƒณใ‚ฏใ‚’ๅ–ๅพ—ใ—ใŸ
  • ่Ÿปๆœฌใฎๅˆ็ดš็ทจใ‚’ใ‚ใ‚‹็จ‹ๅบฆ็†่งฃใ—ใŸ
  • ่Ÿปๆœฌใฎไธญ็ดš็ทจใซ็›ฎใ‚’้€šใ—ใŸ
  • AtCoder ProblemsใงEasyใจMediumใ‚’ใกใ‚‡ใ“ใกใ‚‡ใ“Pythonใงใ‚„ใฃใŸ
  • ใ€Œใ‚ณใƒผใƒ‡ใ‚ฃใƒณใ‚ฐใ‚’ๆ”ฏใˆใ‚‹ๆŠ€่ก“ใ€ใ‚’่ชญใ‚“ใ 

ใ“ใ‚Œใพใงใฎๆˆ็ธพ

AGCใฏใ‚„ใฃใฑใ‚Šๅคฉๆ‰ๅพก็”จ้”ใ‚ณใƒณใƒ†ใ‚นใƒˆใงใ—ใŸใ€‚็„กๅฟตใ€‚

No.contestABCDEprf
-AGC049(1)(4)----
12ABC1820:597:1621:16(1)32:2784:071235
11ABC1810:485:3823:4458:56(4)-881
10ARC10613:12(1)62:56(2)---914
9ARC10520:20(4)40:16-(1)-600
8HHKB20202:3120:16(1)43:36(3)--543
7ARC1047:0164:30(1)---650
6ABC17918:3225:31---122
5ABC1782:565:56---508
4ABC1772:3214:10(2)(3)--332
3ABC1769:0913:2620:32--550
2ABC17510:4639:4891:49(3)--543
-AGC047(1)(1)----
1ABC17457:2553:51(3)--79

Aๅ•้กŒ

ใ‹ใชใ‚ŠใƒฌใƒผใƒˆใŒ้ซ˜ใ„ๅฑคใงใ‚‚่งฃใ‘ใชใ„ไบบใŒๅคšใๅ‡บใŸๅ•้กŒใฟใŸใ„ใงใ™ใ€‚
ไธ€ๆ–นใงๆœŸๅพ…ๅ€คๅ•้กŒใŒๅพ—ๆ„ใชไบบใŸใกใฏใ€Œใ“ใ‚Œใฏๅ…ธๅž‹ใ€200็‚นใงใ‚‚ใ‚ˆใ„ใฎใงใฏใ€ใจใ„ใ†ใƒ†ใƒณใ‚ทใƒงใƒณใ ใฃใŸใฎใงใ€่‡ชๅˆ†ใ‚‚ใกใ‚ƒใ‚“ใจๅพฉ็ฟ’ใ—ใฆๆœŸๅพ…ๅ€คใฎๅ…ธๅž‹ใ‚’ๆŠ‘ใˆใฆใŠใในใใ‹ใจๆ„Ÿใ˜ใพใ—ใŸใ€‚

ใพใ‚ใ€้’Diffใชใฎใง่งฃใ‘ใชใใฆใ‚‚ใพใ‚ๅฆฅๅฝ“ใจใ„ใˆใฐๅฆฅๅฝ“ใงใ™ใญใ€‚

ๆๅ‡บใ‚ณใƒผใƒ‰

n=int(input())
s=[]
for _ in range(n):
  s.append(input())
memo=[]

def remove(d,i):
  for j,v in enumerate(s[i]):
    if (j not in d) and v=='1':
      d|={j}
      remove(d,j)

def dfs(deleted,cnt):
  if len(deleted)==n:
    memo.append(cnt)
    return
  for i,v in enumerate(s):
    if i not in deleted:
      d=deleted.copy()
      d|={i}
      remove(d,i)
      dfs(d,cnt+1)
dfs(set(),0)
print(sum(memo)/len(memo))

้–“ใซๅˆใ‚ใชใ•ใใ†ใชใ“ใจใฏ็™พใ‚‚ๆ‰ฟ็Ÿฅใงใ€ใƒฏใƒณใƒใƒฃใƒณ400็‚นใ ใ‹ใ‚‰้€šใ‚‹ใ‹ใจๆ€ใ„ๆŠ•ใ’ใŸใ‚‰ใƒœใ‚ณใƒœใ‚ณใซใ•ใ‚Œใพใ—ใŸใ€‚

setใงๅ‰Š้™คๆธˆใฎ้ ‚็‚นใ‚’ๆŒใŸใ›ใคใคใ€dfsใงๅ…จ้€šใ‚Š่ฉฆใ™ใจใ„ใ†ๅฎŒๅ…จใชๆ„š็›ด่งฃใงใ™ใ€‚
็ต‚ไบ†ๆกไปถใฏใ€setใฎ่ฆ็ด ๆ•ฐใŒ้ ‚็‚นใฎๆ•ฐใจ็ญ‰ใ—ใใชใฃใŸใ‚‰ใ€ใจใ—ใพใ—ใŸใ€‚

dfsๅ†…ใงdfsใ—ใฆใ‚‹ใฎใงใ€ใƒ‘ใƒƒใจ่จˆ็ฎ—้‡ใฏใ‚ใ‹ใ‚‰ใชใ„ใพใงใ‚‚ใ€ใพใ‚้–“ใซๅˆใ‚ใชใ•ใใ†ใ‹ใชใ€ใจใ„ใ†ๆ„Ÿใ˜ใงใ—ใŸใ€‚

ใถใฃใกใ‚ƒใ‘ใฆ่จ€ใˆใฐใ€ใ“ใฎๆ„š็›ด่งฃใ™ใ‚‰่€ƒๅฏŸใจๅฎŸ่ฃ…ใซ 30 ๅˆ†ไปฅไธŠใ‚’่ฆใ—ใฆใพใ™ใ€‚ใพใ ใพใ ๅฎŸๅŠ›ใŒ่ถณใ‚Šใพใ›ใ‚“ใ€‚

่งฃ่ชฌใ‚’่ชญใ‚“ใง

ๆœŸๅพ…ๅ€คใฎ็ทšๅฝขๆ€งใŒใ‚ญใƒผใƒฏใƒผใƒ‰ใฎใ‚ˆใ†ใงใ™ใŒใ€ๆœ€ๅˆ่ชญใ‚“ใ ใจใใฏๆ—ฅๆœฌ่ชžใงใŠ๏ฝ‹ใจใ„ใ†ๆ„Ÿใ˜ใงใ—ใŸใ€‚

ๆ—ฅๆœฌ่ชžใซ็›ดใ™ใจใ€ๅ’ŒใฎๆœŸๅพ…ๅ€คใฏๆœŸๅพ…ๅ€คใฎๅ’Œใจใ„ใ†ใ“ใจใ‚‰ใ—ใ„ใงใ™ใ€‚

ๅผใง่กจใ™ใจใ€E[X+Y]=E[X]+E[Y]E[X+Y]=E[X]+E[Y]ใจใ„ใ†ใ“ใจใงใ€ใชใ‚“ใจใชใใ‚คใƒกใƒผใ‚ธใฏไป˜ใใพใ™ใ€‚

ไปŠๅ›žใฏใ€ๅ…จใฆใฎ้ ‚็‚นใ‚’ๆถˆๅŽปใ™ใ‚‹ใพใงใซใ‹ใ‹ใ‚‹ๆ“ไฝœๅ›žๆ•ฐใฎๆœŸๅพ…ๅ€คใ‚’ๆฑ‚ใ‚ใ‚‹ใจใ„ใ†ๅ•้กŒใงใ™ใ‹ใ‚‰ใ€ใ“ใ‚Œใ‚’ๅŒใ˜ใ‚ˆใ†ใซ่€ƒใˆใฆใฟใพใ™ใ€‚

  • ๅ„้ ‚็‚นใฏ้ซ˜ใ€…1ๅ›žใ—ใ‹้ธใฐใ‚Œใชใ„
  • ใ‚ฐใƒฉใƒ•ใŒ็ฉบใซใชใ‚‹ใพใงใซใ‚ใ‚‹้ ‚็‚นใŒ้ธใฐใ‚Œใ‚‹็ขบ็Ž‡๏ผใใฎ้ ‚็‚นใซใ‹ใ‹ใ‚‹ๆ“ไฝœๅ›žๆ•ฐใฎๆœŸๅพ…ๅ€ค

ใคใพใ‚Šใ€ๆœŸๅพ…ๅ€คใฎ็ทšๅฝขๆ€งใ‹ใ‚‰ไปฅไธ‹ใŒ่จ€ใˆใ‚‹ใ“ใจใซใชใ‚‹๏ผˆใฎใ ใจๆ€ใ„ใพใ™๏ผ‰ใ€‚

E[โˆ‘vโˆˆVv]=โˆ‘vโˆˆVE[v]=โˆ‘vโˆˆVP(v)E\left[\sum_{v\in V}{v}\right]=\sum_{v\in V}{E\left[v\right]}=\sum_{v\in V}{P\left(v\right)}

ใงใ€ใ“ใฎใจใใซๅ„P(v)P(v)ใ‚’ใฉใ†ๆฑ‚ใ‚ใ‚‹ใ‹ใจ่จ€ใˆใฐใ€ๅ…ฌๅผ่งฃ่ชฌใซๆ›ธใ„ใฆใ‚ใ‚‹้€šใ‚Šใงใ™ใ€‚

ใ“ใ“ใงใ€ๆฌกใฎ22ใคใฎไบ‹ๅฎŸใŒ่จผๆ˜Žใงใใพใ™ใ€‚้ ‚็‚นvvใซๅˆฐ้”ๅฏ่ƒฝใช้ ‚็‚น้›†ๅˆใ‚’S(v)โŠ†VS(v)\subseteq{V}ใจใ—ใพใ™ใ€‚

  • S(v)S(v)ใซๅซใพใ‚Œใ‚‹้ ‚็‚นใ‚’้ธใ‚“ใ ๆ™‚ใ€ใพใŸใใฎๆ™‚ใฎใฟใซ้ ‚็‚นvvใฏๅ‰Š้™คใ•ใ‚Œใ‚‹ใ€‚
  • S(v)S(v)ใซๅซใพใ‚Œใชใ„้ ‚็‚นใ‚’้ธใ‚“ใ ใจใใซใ€S(v)S(v)ใซๅซใพใ‚Œใ‚‹้ ‚็‚นใŒๅ‰Š้™คใ•ใ‚Œใ‚‹ใ“ใจใฏใชใ„ใ€‚

ใคใพใ‚Šใ€ใ‚ฐใƒฉใƒ•ใŒ็ฉบใซใชใ‚‹ใพใงใซvvใ‚’้ธๆŠžใ™ใ‚‹็ขบ็Ž‡ใฏใ€S(v)S(v)ใฎไธญใงๅˆใ‚ใฆ้ธๆŠžใ•ใ‚ŒใŸ้ ‚็‚นใŒvvใงใ‚ใ‚‹็ขบ็Ž‡ใซ็ญ‰ใ—ใใ€ใ“ใ‚Œใฏ1โˆฃS(v)โˆฃ\frac{1}{|S(v)|}ใงใ™ใ€‚

1ใค็›ฎใฎ่จผๆ˜Žใฏใ€้ ‚็‚นvvใซๅˆฐ้”ใงใใชใ„้ ‚็‚นใ‚’ๅ‰Š้™คใ—ใฆใ‚‚ๅˆฐ้”ใ—ใชใ„ใฎใ ใ‹ใ‚‰ๅ‰Š้™คใ•ใ‚Œใชใ„ใฎใฏๅฝ“ใŸใ‚Šๅ‰ใงใ™ใญใ€‚

2ใค็›ฎใฎ่จผๆ˜Žใฏใ€้ ‚็‚นvvใซๅˆฐ้”ใงใใชใ„้ ‚็‚นใ‚’ๅ‰Š้™คใ—ใŸใจใใซ้ ‚็‚นvv่‡ช่บซใฎใฟใชใ‚‰ใšใ€้ ‚็‚นvvใซๅˆฐ้”ใงใใ‚‹้ ‚็‚นใ‚‚ๅŒใ˜ใๅ‰Š้™คใ•ใ‚Œใชใ„ใจใ„ใ†ใ“ใจใ‚’ๆ›ธใ„ใฆใ‚ใ‚Šใพใ™ใญใ€‚

ๆ–‡็ซ ใ ใ‘่ชญใ‚€ใจใ€ใ‹ใพใ„ใŸใกใฎใ€Œใ‚‚ใ—ไฟบใŒ่ฌใฃใฆๆฅใ‚‰ใ‚ŒใฆใใฆใŸใจใ—ใŸใ‚‰ใ€็ตถๅฏพใซ่ชใ‚ใ‚‰ใ‚ŒใฆใŸใจๆ€ใ†ใ‹๏ผŸใ€ใฟใŸใ„ใชๆ„Ÿใ˜ใง้ ญใŒใถใฃ้ฃ›ใณใใ†ใซใชใ‚Šใพใ™ใŒใ€ๅ†ท้™ใซ่€ƒใˆใฆใฟใพใ™ใ€‚

่ƒŒ็†ๆณ•ใ‚’่€ƒใˆใพใ™ใ€‚้ ‚็‚นvvใซๅˆฐ้”ๅฏ่ƒฝใช้ ‚็‚นใŒS(v)S(v)ใงใ™ใ‹ใ‚‰ใ€ๅˆฐ้”ไธๅฏ่ƒฝใช้ ‚็‚นใฎ้›†ๅˆใ‚’Sโ€พ(v)\overline{S}(v)ใจ่กจ่จ˜ใ—ใพใ™ใ€‚

ใ‚ใ‚‹้ ‚็‚น{wโˆฃโˆˆSโ€พ(v)}\{w|\in\overline{S}(v)\}ใ‚’ๅ‰Š้™คใ—ใŸใจใใซใ€้ ‚็‚น{uโˆฃโˆˆS(v)}\{u|\in S(v)\}ใŒๅ‰Š้™คใ•ใ‚ŒใŸใจไปฎๅฎšใ—ใพใ™ใ€‚

ใ—ใ‹ใ—ใ€vvใ‚’ๅซใ‚€ใ™ในใฆใฎuuใซใคใ„ใฆใ€ใฉใฎwwใ‚’ๅ‰Š้™คใ—ใฆใ‚‚uuใ‚’ๅ‰Š้™คใ™ใ‚‹ใ“ใจใฏใงใใชใ„ใŸใ‚ๅ‰ๆใจ็Ÿ›็›พใ—ใพใ™ใ€‚ใ“ใ‚Œใฏ1ใค็›ฎใฎ่จผๆ˜Žๅ†…ๅฎนใ‚’ๅ„uuใซๅฏพใ—ใฆๅ†ๅธฐ็š„ใซ้ฉ็”จใ—ใŸใฎใจๅ…จใๅŒใ˜ใ“ใจใงใ‚ใ‚Šใ€่‡ชๆ˜Žใงใ™ใ€‚

ใ‚ˆใฃใฆใ€ๆฑ‚ใ‚ใ‚‹ในใใฏ1โˆฃS(v)โˆฃ\frac{1}{|S(v)|}ใง้–“้•ใ„ใชใ„ใ“ใจใŒใ‚ใ‹ใ‚Šใพใ—ใŸใ€‚

ๅฎŸ่ฃ…ใ—ใฆใฟใ‚‹

ใ™ในใฆใฎ้ ‚็‚นใซ้–ขใ—ใฆใ€1โˆฃS(v)โˆฃ\frac{1}{|S(v)|}ใ‚’ๆฑ‚ใ‚ใ‚Œใฐ่‰ฏใ„ใงใ™ใ€‚

# ๅ…ฅๅŠ›
n = int(input())
s = [input() for _ in range(n)]
# ๅ‡บๅŠ›ใฎๅˆๆœŸๅŒ–
ans = 0
# ๅ…จ้ ‚็‚นใซ้–ขใ—ใฆใƒซใƒผใƒ—
for i in range(n):
    # ้ ‚็‚นใ‚’ใ‚ญใƒฅใƒผใซ่ฟฝๅŠ ใ™ใ‚‹
    que = [i]
    # ๅ‰Š้™คๆธˆใ‹ใฎใƒ•ใƒฉใ‚ฐ
    deleted = [False] * n
    # ใ‚ญใƒฅใƒผใŒ็ฉบใซใชใ‚‹ใพใงใƒซใƒผใƒ—
    while que:
        # ใ‚ญใƒฅใƒผใ‹ใ‚‰้ ‚็‚นใ‚’ๅ–ใ‚Šๅ‡บใ—
        v = que.pop()
        # ๅ‰Š้™คๆธˆใชใ‚‰ๆฌกใฎ้ ‚็‚นใธ
        if deleted[v]: continue
        # ๅ‰Š้™คๆธˆใƒ•ใƒฉใ‚ฐใ‚’็ซ‹ใฆใ‚‹
        deleted[v] = True
        # ้ ‚็‚นuใ‹ใ‚‰้ ‚็‚นvใซ่พบใŒใ‚ใ‚‹ใ‹ใƒใ‚งใƒƒใ‚ฏ
        for u in range(n):
            # ๅ‰Š้™คๆธˆใพใŸใฏ่พบใŒใชใ„ๅ ดๅˆใฏๆฌกใธ
            if deleted[u] or s[u][v] == '0': continue
            # ๆœชๅ‰Š้™คใฎ่พบใŒใ‚ใ‚Œใฐ้ ‚็‚นuใ‚’ใ‚ญใƒฅใƒผใซ่ฟฝๅŠ 
            que.append(u)
    # ้ ‚็‚นvใธๅˆฐ้”ๅฏ่ƒฝใชๅ…จ้ ‚็‚นใฎ้€†ๆ•ฐใ‚’ๅŠ ใˆใ‚‹
    ans += 1 / sum(deleted)
# ๅ‡บๅŠ›
print(ans)

ใกใ‚‡ใ†ใฉใ€ๅ‰Š้™คใฎ้€ฃ้Ž–ใ‚’้€†ใ‹ใ‚‰่พฟใฃใฆใ„ใ‚‹ใ‚ˆใ†ใชๅฝขใซใชใ‚Šใพใ™ใ€‚

1ๅบฆ่จชใ‚ŒใŸ้ ‚็‚นใ‚’ๅ‰Š้™คๆธˆใจใ™ใ‚‹ใ“ใจใงใ€1้ ‚็‚นใซ้–ขใ—ใฆๆœ€ๅคงใงใ‚‚100้ ‚็‚น่ฟฝๅŠ ใ—ใŸใ‚‰ใƒซใƒผใƒ—ใŒ็ต‚ไบ†ใ™ใ‚‹ใฎใง่จˆ็ฎ—้‡ใ‚‚ๅ•้กŒใ‚ใ‚Šใพใ›ใ‚“ใ€‚

Bๅ•้กŒ

็ท‘Diffใงใ—ใŸใ€‚่งฃใ‘ใ‚‹ในใๅ•้กŒใงใ—ใŸใŒใ€ใƒ€ใƒกใงใ—ใŸใ€‚

ๆๅ‡บใ‚ณใƒผใƒ‰

n=int(input())
s=[int(l) for l in input()]
t=[int(l) for l in input()]
cnt=0
for i in range(n):
  if s[i]!=t[i]:
    j=i+1
    while j<n and s[j]==0:
      j+=1
    if j==n:
      print(-1)
      exit()
    s[j]=0
    s[i]=(0 if s[i] else 1)
    cnt+=j-i
print(cnt)

ใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใŒๅฐใ•ใ„ๆ–นใ‹ใ‚‰ใ€sใจtใŒ็•ฐใชใฃใฆใ„ใ‚‹ใชใ‚‰ใฐs==1ใจใชใ‚‹ใพใงใ‚คใƒณใ‚ฏใƒชใƒกใƒณใƒˆใ—ใฆใ„ใใพใ™ใ€‚
1ใฎไฝ็ฝฎใฏ้€ฃ็ถš็š„ใชๆ“ไฝœใงใฉใ‚“ใฉใ‚“ๅทฆใซ็งปใ—ใฆใ„ใ‘ใ‚‹ใฎใงใ€ใ“ใ‚Œใ‚’็นฐใ‚Š่ฟ”ใ›ใฐๆœ€ๆ‚ช่จˆ็ฎ—้‡O(N2)O(N^2)ใง่งฃใ‘ใพใ™๏ผˆใคใพใ‚Š้–“ใซๅˆใ„ใพใ›ใ‚“๏ผ‰ใ€‚

่งฃ่ชฌใ‚’่ชญใ‚“ใง

ๆญฃ็›ดใ€ใ“ใกใ‚‰ใ‚‚ๆœ€ๅˆใฏ่งฃ่ชฌใ‚’่ชญใ‚“ใงใ‚‚็†่งฃใงใใพใ›ใ‚“ใงใ—ใŸใ€‚

็ดฏ็ฉxorใ‚’ๅ–ใ‚‹ใจ

ใ€Œใใ‚Œใฏใฉใ†ๅ–ใ‚‹ใ‚“ใ‚„โ€ฆโ€ฆใ€‚ใ€ใจใชใ‚Šใพใ—ใŸใ€‚

่ชฟในใฆใฟใฆๅˆ†ใ‹ใ‚Šใพใ—ใŸใŒใ€ใฉใ†ใ‚‚็ดฏ็ฉๅ’Œ็š„ใชๅ‡ฆ็†ใจใ„ใ†ใฎใฏ็พคใฎๆ€ง่ณชใ‚’ๆบ€ใŸใ—ใฆใ„ใ‚Œใฐๅฏ่ƒฝใชใ‚ˆใ†ใงใ™ใ€‚

็พคใฎๆกไปถ

  • ็ตๅˆๅ‰‡ใŒๆˆใ‚Š็ซ‹ใค
  • ้€†ๅ…ƒใŒๅญ˜ๅœจใ™ใ‚‹
  • ๅ˜ไฝๅ…ƒใŒๅญ˜ๅœจใ™ใ‚‹

ใชใ‚‹ใปใฉxorใฏๆˆใ‚Š็ซ‹ใกใพใ™ใญใ€‚

็ตๅˆๅ‰‡

01ใงไฝœใ‚Œใ‚‹ๅ…จใƒ‘ใ‚ฟใƒผใƒณใงTrueใซใชใ‚‹ใฎใงๆˆใ‚Š็ซ‹ใฃใฆใ„ใใ†ใงใ™ใ€‚

for i in [0,1]:
  for j in [0,1]:
    for k in [0,1]:
      print((i^j)^k==i^(j^k))

ๅ˜ไฝๅ…ƒ

ๅ˜ไฝๅ…ƒใจใฏใ€ไปปๆ„ใฎxxใซๅฏพใ—eโŠ•x=xโŠ•e=xe\oplus x=x\oplus e=xใ‚’ๆบ€ใŸใ™eeใ‚’ๆŒ‡ใ—ใพใ™ใ€‚

0โŠ•(1,0)=(1,0)โŠ•0=(1,0)0\oplus (1,0)=(1,0)\oplus 0=(1,0)ใงใ‚ใ‚Šใ€00ใฏๅ˜ไฝๅ…ƒใงใ™ใ€‚ 1โŠ•(1,0)=(1,0)โŠ•1=(0,1)1\oplus (1,0)=(1,0)\oplus 1=(0,1)ใงใ‚ใ‚Šใ€11ใฏๅ˜ไฝๅ…ƒใงใฏใ‚ใ‚Šใพใ›ใ‚“ใ€‚

้€†ๅ…ƒ

้€†ๅ…ƒใจใฏใ€ไปปๆ„ใฎxxใซๅฏพใ—ใฆxโŠ•y=yโŠ•x=ex\oplus y=y\oplus x=eใ‚’ๆบ€ใŸใ™yyใฎใ“ใจใงใ™ใ€‚

xorใฏๅฏๆ›ใงใ‚ใ‚Šใ€ใ‹ใค0โŠ•0=00\oplus 0=0ใŠใ‚ˆใณ1โŠ•1=01\oplus 1=0ใงใ‚ใ‚‹ใŸใ‚ใ€ๅธธใซ่‡ชๅˆ†่‡ช่บซใŒ้€†ๅ…ƒใจใชใ‚Šใพใ™ใ€‚

XORใฏ็พคใ‚’ใชใ™

ไปฅไธŠใ‚ˆใ‚Šใ€XORใฏ็พคใ‚’ใชใ™ๆผ”็ฎ—ๅญใงใ‚ใ‚‹ใจใ„ใ†ใ“ใจใŒๅˆ†ใ‹ใ‚Šใพใ—ใŸใ€‚

ใกใชใฟใซใ€็ตๅˆๅ‰‡ใจๅ˜ไฝๅ…ƒใฎใฟใŒๅญ˜ๅœจใ—้€†ๅ…ƒใŒๅญ˜ๅœจใ—ใชใ„ใ‚‚ใฎใ‚’ใƒขใƒŽใ‚คใƒ‰ใจใ‚ˆใณใ€็พคใฎๆกไปถใซๅŠ ใˆใฆๅฏๆ›ๅ‰‡xโ‹…y=yโ‹…xx\cdot y=y\cdot xใŒๆˆใ‚Š็ซ‹ใคใ‚‚ใฎใ‚’ๅฏๆ›็พคใจๅ‘ผใณใพใ™๏ผˆใคใพใ‚ŠXORใฏๅฏๆ›็พคใงใ™๏ผ‰ใ€‚

ใ—ใŸใŒใฃใฆใ€็ดฏ็ฉๅ’Œใชใ‚‰ใฌ็ดฏ็ฉXORใฏๅธธใซ้€š็”จใ™ใ‚‹ใƒ†ใ‚ฏใƒ‹ใƒƒใ‚ฏใจใ„ใ†ใ“ใจใซใชใ‚Šใพใ™ใ€‚

็ดฏ็ฉXORใ‚’่€ƒใˆใ‚‹

็ดฏ็ฉๅ’Œใฎ00็•ช็›ฎใฎ่ฆ็ด ใ€ใ™ใชใ‚ใกๅŒบ้–“ๅ’Œ[0,0)[0,0)ใŒๅ’Œใฎๅ˜ไฝๅ…ƒ00ใงใ‚ใฃใŸใ“ใจใ‚’่€ƒใˆใ‚‹ใจใ€็ดฏ็ฉXORใงใ‚‚ๅŒใ˜ใ‚ˆใ†ใซๅ˜ไฝๅ…ƒ00ใŒๆฅใ‚‹ใจ่€ƒใˆใฆ่‰ฏใ„ใงใ—ใ‚‡ใ†ใ€‚
ใใ‚Œใงใฏใ€ใ‚ตใƒณใƒ—ใƒซใ‚ฑใƒผใ‚น3ใฎ็ดฏ็ฉXORใ‚’่ฉฆใ—ใซๅ–ใฃใฆใฟใพใ—ใ‚‡ใ†ใ€‚

n = '5'
s = '10111'
t = '01010'
x = '011010'  # sใฎ็ดฏ็ฉXOR
y = '001100'  # tใฎ็ดฏ็ฉXOR

ใ“ใ“ใงใ€็ดฏ็ฉXORใ‚’ๅ–ใ‚‹ๅ‰ใฎๆ–‡ๅญ—ๅˆ—Sใธใฎๆ“ไฝœใ‚’่€ƒใˆใ‚‹ใจใ€ไปฅไธ‹ใฎ2ใƒ‘ใ‚ฟใƒผใƒณใ—ใ‹ใ‚ใ‚Šใพใ›ใ‚“ใ€‚

  • 11ใ‚’ๅทฆใซใ‚ทใƒ•ใƒˆใ™ใ‚‹๏ผš01โ†’1001\rightarrow 10
  • ้šฃใ‚ŠๅˆใฃใŸ11ใฎใƒšใ‚ขใ‚’ๆถˆใ™๏ผš11โ†’0011\rightarrow 00

ใ“ใ‚Œใ‚’็ดฏ็ฉXORใซ็›ดใ™ใจใฉใ†ใชใ‚‹ใ‹ใ‚’่€ƒใˆใพใ™ใ€‚
็›ดๅ‰ใพใงใฎ็ดฏ็ฉๅ€คใŒ00ใ‹11ใฎใƒ‘ใ‚ฟใƒผใƒณใซๅˆ†ใ‹ใ‚Œใ‚‹ใฎใงใ€ๆ•ฐๅญ—ใฎไธฆใณใจใ—ใฆ่€ƒใˆใ‚‰ใ‚Œใ‚‹ใฎใฏใ€

็›ดๅ‰SXORโ†’\rightarrow็›ดๅ‰SXOR
0001010101โ†’\rightarrow0010101111
1101011010โ†’\rightarrow1110100000
0011111010โ†’\rightarrow0000000000
1111110101โ†’\rightarrow1100001111
0000000000โ†’\rightarrow0000000000
1100001111โ†’\rightarrow1100001111
0010101111โ†’\rightarrow0010101111
1110100000โ†’\rightarrow1110100000

ใจใชใ‚Šใ€ใ“ใ‚ŒใŒๅ…ฌๅผ่งฃ่ชฌใง่ฟฐในใ‚‰ใ‚Œใฆใ„ใ‚‹ๅ†…ๅฎนใใฎใพใพใงใ™ใ€‚

Siโ‰ Si+1S_i\ne S_{i+1}ใชใ‚‹iiใ‚’้ธใณ๏ผŒSiS_iใ‚’Si+1S_{i+1}ใง็ฝฎใๆ›ใˆใ‚‹๏ผŽ

Si=Si+1S_i=S_{i+1}ใฎๅ ดๅˆใฏใ€ใใ‚‚ใใ‚‚ๆ“ไฝœใŒไธๅฏใฎๅ ดๅˆใซ็›ธๅฝ“ใ—ใฆใ„ใพใ™ใ€‚
ใใ—ใฆ็ดฏ็ฉXORใฎๅ€คใฏใ€ๆ“ไฝœใ—ใฆใ‚‚ใใ‚Œไปฅ้™ใฎ้ƒจๅˆ†ใซใฏๅฝฑ้Ÿฟใ‚’ๅŠใผใ—ใฆใ„ใชใ„ใŸใ‚ใ€ใ“ใ‚Œใ ใ‘ใ‚’่€ƒใˆใ‚Œใฐใ‚ˆใ„ใ“ใจใŒๅˆ†ใ‹ใ‚Šใพใ—ใŸใ€‚

ๅฎŸ่ฃ…ใ™ใ‚‹

ใพใšใ€sใจtใซ้–ขใ—ใฆ็ดฏ็ฉXORใƒชใ‚นใƒˆใ‚’ไฝœใ‚Šใพใ™ใ€‚

# ๅ…ฅๅŠ›
n=int(input())
s=[int(l) for l in input()]
t=[int(l) for l in input()]
# ็ดฏ็ฉXOR
xs=[0]
xt=[0]
for i in s: xs.append(xs[-1]^i)
for i in t: xt.append(xt[-1]^i)

ใ“ใ‚Œใฏ็ดฏ็ฉๅ’Œใ‚’ๅฎŸ่ฃ…ใ™ใ‚‹ใจใใฎ+ใ‚’^ใซใ™ใ‚‹ใ ใ‘ใชใฎใง้žๅธธใซใ‚ทใƒณใƒ—ใƒซใงใ™ใ€‚
่จˆ็ฎ—้‡O(N)O(N)ใงใ™ใฎใงไฝ™่ฃ•ใง้–“ใซๅˆใ„ใพใ™ใ€‚

ไธ€ๅฟœใ€numpyใซใฏcumsumใจใ„ใ†็ดฏ็ฉๅ’Œใ‚’ๆฑ‚ใ‚ใ‚‹้–ขๆ•ฐใŒใ‚ใ‚Šใ€ๅ‹•ไฝœใ‚‚้ซ˜้€Ÿใชใ‚ˆใ†ใงใ™ใŒ็ซถใƒ—ใƒญใ ใจimportใ™ใ‚‹ๆ™‚้–“ใŒใ‚ใ‚‹ใฎใงๆ™ฎ้€šใฎforใงใ„ใ„ใ‹ใชใจๆ€ใฃใฆใ„ใพใ™ใ€‚ๅˆฅใซๅฎŸ่ฃ…ใ‚‚้žๅธธใซๅ˜็ด”ใชใฎใง้–“้•ใˆใ‚‹ใƒชใ‚นใ‚ฏใ‚‚ใปใผใ‚ใ‚Šใพใ›ใ‚“ใ€‚ใพใŸใ€ๆ™ฎ้€šใฎ็ดฏ็ฉๅ’Œใฏใ‚ใฃใฆใ‚‚numpyใซ็ดฏ็ฉXORใฏใ‚ใ‚Šใพใ›ใ‚“ใ€‚

ใงใฏใ€ใƒซใƒผใƒ—ใ‚’ๅ›žใ™้ƒจๅˆ†ใ‚‚ๅฎŸ่ฃ…ใ—ใฆใ„ใใพใ™ใ€‚ๅ…ฌๅผ่งฃ่ชฌใงใฏใ€

ไธŠใฎๆ“ไฝœๅพŒSi,Si+1,โ€ฆ,SjS_i,S_{i+1},\dots,S_jใŒใ™ในใฆๅŒใ˜ใซใชใฃใฆใ„ใ‚‹ใจใ„ใ†ๆƒ…ๅ ฑใ‚’ๆŒใคใ“ใจใง๏ผŒO(N)O(N)ๆ™‚้–“ใงๆ“ไฝœๅ›žๆ•ฐใŒ่จˆ็ฎ—ใงใใพใ™๏ผŽ

ใจใ„ใ†ใ“ใจใŒๆ›ธใ„ใฆใ‚ใ‚Šใพใ™ใŒใ€ใ“ใ‚Œใฎ่งฃ่ชญใซ่‹ฆๅŠดใ—ใพใ—ใŸใ€‚

็ต่ซ–ใจใ—ใฆใฏใ€1ใคใšใคไผๆ’ญใ•ใ›ใฆO(N)O(N)ๆ™‚้–“ใ‹ใ‘ใ‚‹ใฎใงใฏใชใใ€ๆœ€็ต‚็š„ใช็Šถๆ…‹ใฏๆ—ข็ŸฅใฎใŸใ‚jjใ‹ใ‚‰iiใพใงไธ€ๆฐ—ใซๆ“ไฝœใ€ใคใพใ‚ŠO(1)O(1)ๆ™‚้–“ใงๅ‡ฆ็†ใ—ใพใ—ใ‚‡ใ†ใญใ€ใจใ„ใ†ใ“ใจใ‚’่จ€ใฃใฆใ„ใ‚‹ใฎใ ใจๆ€ใ„ใพใ™ใ€‚

ใ“ใ‚Œใ‚’ๅ…ƒใซๅ‡ฆ็†้ƒจๅˆ†ใ‚’้–ขๆ•ฐๅŒ–ใ™ใ‚‹ใจไปฅไธ‹ใฎใ‚ˆใ†ใซใชใ‚Šใพใ™ใ€‚

def solve():
  # ็ตๆžœใ‚’ไฟๆŒ
  ans=0
  # S[j]!=S[j+1]ใจใชใ‚Šใ†ใ‚‹ๆœ€ๅฐใฎjใ‚’ไฟๆŒ
  j=0
  for i in range(n+1):
    # iใŒjใ‚’่ฟฝใ„่ถŠใ—ใŸใ‚‰ๆ›ดๆ–ฐ
    j=max(j,i)
    # ๆ“ไฝœไธ่ฆใชใ‚‰ใ‚นใ‚ญใƒƒใƒ—
    if xs[j]==xt[i]:continue
    # SใŒๅค‰ๅŒ–ใ—ใชใ„็ฏ„ๅ›ฒใงใ‚คใƒณใ‚ฏใƒชใƒกใƒณใƒˆ
    while j<n and xs[j]==xs[j+1]:j+=1
    # ๆกไปถใ‚’ๆบ€ใŸใ™jใŒใชใ‘ใ‚Œใฐไธๅฏ่ƒฝ
    if j==n:return -1
    # S[j]==T[i]ใจใ™ใ‚‹ใŸใ‚ใ‚คใƒณใ‚ฏใƒชใƒกใƒณใƒˆ
    j+=1
    # ่ท้›ขใŒๆ“ไฝœๅ›žๆ•ฐใจ็ญ‰ใ—ใ„
    ans+=j-i
  return ans

็ดฏ็ฉXORไฝฟใ‚ใชใใฆใ‚‚่งฃใ‘ใ‚‹ใใชใ„๏ผŸ

ใ‹ใชใ‚Š็†่งฃใซๆ™‚้–“ใ‚’่ฆใ—ใŸใ‚‚ใฎใฎใ€็ดฏ็ฉXORใ‚’ไฝฟใ‚ใชใใฆใ‚‚ๅˆฅใซ่งฃใ‘ใ‚‹ใจใ„ใ†ใ“ใจใซๆฐ—ไป˜ใใพใ—ใŸใ€‚

ๅ…ฅๅŠ›ใ‚’ๅ—ใ‘ๅ–ใ‚‹

ใใฎใพใพใงใ™ใ€‚

n=int(input())
s=[int(l) for l in input()]
t=[int(l) for l in input()]

ไบˆๅ‚™ๅ‡ฆ็†

SSใŒ11ใจใชใ‚‹ใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใ‚’้€†้ †ใซใ—ใฆใ‚นใ‚ฟใƒƒใ‚ฏใซไฟๆŒใ—ใพใ™ใ€‚
้€†้ †ใซใ™ใ‚‹ใฎใฏใ€.pop()ใ‚’ไฝฟใฃใฆO(1)O(1)ใง่‹ฅใ„้ †ใซๅ–ใ‚Šๅ‡บใ™ใŸใ‚ใงใ™ใ€‚

dequeใ‚’ไฝฟใฃใฆ.popleft()ใ—ใฆใ‚‚O(1)O(1)ใงใ™ใŒใ€ๆœซๅฐพใธใฎๆ“ไฝœใŒใชใ„ใŸใ‚dequeใงใ‚ใ‚‹ๅฟ…่ฆๆ€งใฏใ‚ใ‚Šใพใ›ใ‚“ใ€‚

ใ“ใฎไบˆๅ‚™ๅ‡ฆ็†ใฎ็›ฎ็š„ใฏไฝ•ใ‹ใจ่จ€ใˆใฐใ€ๆ“ไฝœใŒๅฏ่ƒฝใชใฎใฏSSใŒ11ใจใชใ‚‹ใ‚คใƒณใƒ‡ใƒƒใ‚ฏใ‚นใฎใฟใฎใŸใ‚ใ€ใ“ใ‚Œใ‚’ๆŠฝๅ‡บใ—ใฆใ„ใพใ™ใ€‚

ใ“ใ‚Œใ‚’ใ—ใชใ„ใจใ€S[i]=1S[i]=1ใจใชใ‚‹iiใ‚’ๅ‡ฆ็†ใฎใŸใณใซใ‚ตใƒผใƒใ™ใ‚‹ใ“ใจใซใชใ‚‹ใฎใงใ€่จˆ็ฎ—้‡ใŒใ‚ชใƒผใƒใƒผใ—ใพใ™ใ€‚

u=[]
for i,v in enumerate(s):
  if v==1:u.append(i)
u=u[::-1]

ๆœฌๅ‡ฆ็†

SSใซๅฏพใ—ใฆๅ‡บๆฅใ‚‹ๆ“ไฝœใฏไปฅไธ‹ใฎ2ใƒ‘ใ‚ฟใƒผใƒณใงใ™ใ€‚

  • 11ใ‚’ๅทฆใซใ‚นใƒฉใ‚คใƒ‰ใ™ใ‚‹
  • ใƒšใ‚ขใจใชใฃใฆใ„ใ‚‹11ใ‚’ๆถˆใ™

ใพใŸใ€S[i]=T[i]S[i]=T[i]ใงใ‚ใ‚Œใฐๆ“ไฝœใฏไธ่ฆใงใ™ใ€‚

ใ“ใ‚Œใ‚’ๅฟต้ ญใซใŠใ„ใฆๅฎŸ่ฃ…ใ—ใฆใ„ใใพใ™ใ€‚

# ๅ‡บๅŠ›ใ‚’ไฟๆŒ
ans=0
# Nๅ€‹ๅ…จไฝ“ใ‚’ใƒซใƒผใƒ—
for i in range(n):
  # ่ฟฝใ„่ถŠใ—ใŸ่ฆ็ด ใ‚’ๅ–ใ‚Š้™คใ
  if s[i]==1: u.pop()
  # ๆ“ไฝœไธ่ฆใชใ‚‰ใ‚นใ‚ญใƒƒใƒ—
  if s[i]==t[i]: continue
  # ๆ“ไฝœๅฏ่ƒฝใชไฝ็ฝฎใŒๆžฏๆธ‡ใ—ใŸใ‚‰็ต‚ไบ†
  if len(u)==0: break
  # ๆ“ไฝœๅฏ่ƒฝใชๆœ€ๅฐใฎjใ‚’ๅ–ๅพ—
  j=u.pop()
  # ไปŠใฎไฝ็ฝฎใพใงไธ€ๆฐ—ใซๆ“ไฝœ
  ans+=j-i
  # ใƒ‘ใ‚ฟใƒผใƒณใซใ‚ˆใ‚‰ใšjใฏๅฟ…ใš0ใซใชใ‚‹
  s[j]=0
  # iใฏไปŠใจ้€†ใฎๅ€คใซใชใ‚‹
  s[i]=(0 if s[i] else 1)
# ๆ“ไฝœๅพŒใซไธไธ€่‡ดใชใ‚‰ไธๅฏ่ƒฝ
if s!=t:ans=-1
# ๅ‡บๅŠ›
print(ans)

ๅ‹•ใใ‚’่€ƒใˆใ‚‹

ใฉใ†ใ„ใ†ใ“ใจใ‚’ใ‚„ใฃใฆใ„ใ‚‹ใ‹ใ‚’่ฃœ่ถณใ—ใพใ™ใ€‚
ไธ‹ๅ›ณใฎ้ท็งปใ‚’่€ƒใˆใ‚‹ใจใ€ใƒ‘ใ‚ฟใƒผใƒณใซใ‚ˆใ‚‰ใšใƒˆใƒผใ‚ฟใƒซใฎๆ“ไฝœๅ›žๆ•ฐใฏๅŒใ˜ใงใ‚ใ‚‹ใ“ใจใŒๅˆ†ใ‹ใ‚Šใพใ™ใ€‚

img

ใพใจใ‚

่ค‡ๆ•ฐใฎไฝ็ฝฎใ‚’็ฎก็†ใ—ใชใŒใ‚‰ๅ‹•ใ‹ใ™ๆ“ไฝœใ‚’ไปŠๅพŒใƒใ‚ฐใ‚‰ใ›ใšๅฎŸ่ฃ…ใงใใ‚‹ใ‚ˆใ†ใซใชใ‚ŠใŸใ‹ใฃใŸใฎใงใ€ๆŠ•็จฟใซใ™ใ‚‹ใ“ใจใง้ ญใฎๆ•ด็†ใ‚’ใ—ใพใ—ใŸใ€‚

ใ‚„ใฏใ‚Šใ€AGCใฏ่งฃ่ชฌใ‹ใ‚‰ใ—ใฆใƒ‰็ด ไบบใฏๅธฐใ‚Œใจใ„ใ†ๆ„Ÿใ˜ใงใ™ใญใ€‚ๅŒใ˜ๅ†…ๅฎนใŒๅ‡บใŸใ‚‰ๆฌกใฏใ‚ตใ‚ฏใƒƒใจ็†่งฃใงใใ‚‹ใ‚ˆใ†ใซๅฐ‘ใ—ใšใค็ฉใฟ้‡ใญใฆใ„ใ“ใ†ใจๆ€ใ„ใพใ™ใ€‚