CODE FESTIVAL 2017 qual C C – Inserting ‘x’ をPython3で解く

Share

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

出典:
CODE FESTIVAL 2017 qual C C – Inserting ‘x’

求めなければならないのは操作回数だけなので、実際に文字列操作を行う必要はない点に注意。

# CODE FESTIVAL 2017 qual C C - Inserting 'x'
# https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_c
# tag: 文字列 文字挿入 回文 すぬけ君

# 'x' 以外の文字を挿入できないので、元の文字列の 'x' 以外の
# 部分はあらかじめ回文になっている必要がある。

# なっていれば、各 'x' 以外の文字の間にいくつ 'x' が
# 入っているかをカウントし、それを左右合わせてやることで、
# 回文に変更できる。

# f.e.
# s = 'xabxa'
# 'x' 以外の文字、'a' 'b' を仕切りと考えるイメージ。
# 'b' を中央として、文字間の x の個数は
# 左から [1, 0] 個 'x'*1 + 'a' + 'x'*0 + 'b'
# 右から [0, 1] 個 'x'*0 + 'a' + 'x'*1 + 'b'
# これをどうにか合わせてやる……みたいな。

# 実装の際は、半分の地点で分けるのは面倒くさいので、
# 最後までリストを作り、逆にしたものと差分の絶対値を取り、
# 合計したものを2 で割ってやる。

# 上記の例で行くと、
# x の個数のリストを最後まで作成すると、
# ('x'*1 + 'a' + 'x'*0 + 'b' + 'x'*1 + 'a' + 'x'*0)
# より、[1, 0, 1, 0] となるので、
# [1, 0, 1, 0]
# [0, 1, 0, 1] - 上記のリストの逆順
#  1  1  1  1 - 差分(絶対値)
# この合計が 4 になる。
# が、ダブって計算しているので、半分に割る。

# 丁度真ん中に 'x' が来る場合は、そこの差分が 0 になるので
# 気にしなくてもいい。

def main():
    s = input()

    # 回分に変換可能かどうかを確認
    without_x = s.replace('x', '')
    if without_x != without_x[::-1]:
        print(-1)
        return

    # x の個数リストを作成
    x_seq = []
    x_cnt = 0
    for c in s:
        if c == 'x':
            x_cnt += 1
        else:
            x_seq.append(x_cnt)
            x_cnt = 0
    x_seq.append(x_cnt)

    # ひっくり返したものと差分を取り、合計する
    result = sum(abs(c1 - c2) for c1, c2 in zip(x_seq, x_seq[::-1]))

    # 実際の答えは、半分
    result //= 2
    print(result)

main()
Share

コメントを残す

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