AtCoder Regular Contest 119 B – Electric Board をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Regular Contest 119 B – Electric Board

電光掲示板と言うわりに、物理的な移動をしているような……。きちんと考察が終われば、実装は軽い問題。

# AtCoder Regular Contest 119 B - Electric Board
# https://atcoder.jp/contests/arc119/tasks/arc119_b
# tag: 考察 数列 入れ替え 一致

# 01111 <-> 11110

# 入力例1で考える。
# 1110110
# 1011110 : 真ん中の 0 を左へ移動
# 1010111 : 右端の 0 を左へ移動
# のように、0 を左右に移動させると捉えると理解しやすい。
# 1 は空いているスペースに相当する。

# となると、元の数列の n 番目の 0 を、最後の数列の n 番目に
# 移動させると考えればいい。

# 1) すでに一致していれば移動させなくていい。
# 2) 移動先までの間に他の 0 がなければ一手で移動させる。
# 3) 移動先までの間に他の 0 があれば、それを先に一致させる。

# という手順を踏むことで、
# (0 の個数) - (元々場所が一致している 0 の個数)
# の手数で完了できる。(常に 0 が足りなくなっている端から
# 一致させるような動きになる)

def main():
    N = int(input())
    S = [int(c) for c in input()]
    T = [int(c) for c in input()]


    # それぞれの 0 の場所を確認
    s_pos = []
    for i in range(N):
        if S[i] == 0:
            s_pos.append(i)
    t_pos = []
    for i in range(N):
        if T[i] == 0:
            t_pos.append(i)
    
    # 0 の個数が一致していなければ不可能
    if len(s_pos) != len(t_pos):
        print(-1)
        return

    result = len(s_pos)

    # 元々移動させる必要がない 0 の個数分を引く
    for i in range(len(s_pos)):
        if s_pos[i] == t_pos[i]:
            result -= 1
    
    print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。