Codeforces Round #606 (Div. 2) D. Let's Play the Words? (1800)

codeforces.com

問題概要

10, 1001, 0010みたいな、0と1だけで構成される単語（同じものは無い）でしりとりをする。
10→01のように左右反転する操作が可能である。
n個の単語をすべてつなげたいが、反転する操作の回数を最小にするようにしたい。
反転の操作をしたあとでも、n個の単語全てが違うものでなければいけない。
何番目の単語を反転させればいいか（一つもしなくていいなら0、いくら反転してもしりとりが不可能なら-1）を出力せよ。

制約

入力あたりのテストケース数 <= 10^4
入力あたりのnの和 <= 2*10^5
入力あたり単語の長さの和 <= 4*10^6

解法

しりとりをしたいので、各単語の最初と最後だけ注目すればいい。
よって、最初と最後が00,11,01,10の4パターンに分け、それぞれの数をa,b,c,dとする。
さらに、反転させる意味があるのは01,10パターンのみなので、これらは単語と順番をそれぞれキーと値にして辞書C,Dに入れておく。

しりとりが不可能な場合を考えると、00,11パターンがいずれも1つ以上あり（a*b > 0）、かつそれらをつなぐ10,01パターンが1つもないこと（c == d == 0）。

そうでない場合はしりとりができる。
01,10パターンのみをつなげることを考えれば、00,11パターンは適当な場所に入れることができるので十分。
01,10,01,10...のように交互に繋げないといけないので、01パターンの個数と10パターンの個数の差が1以下でなければいけない。
（端の分だけどちらかが1多くてもよい）

従って、|c-d|=0なら0回、|c-d|=1なら0回、|c-d|=2なら1回、|c-d|=3なら2回...反転する必要がある。
つまり|c-d|//2 回だけ反転させればよい。
cとdの大小で場合分けし、例えばc > dの場合は01パターンを反転させていく。
n個の単語全てが違うものでなければいけないので、辞書Cに入っている01パターンを見ていき、それの反転が辞書Dに入っていなければ、単語をキーとしてCから値（位置）を取り出してansに追加する。
ansの長さが|c-d|//2になったらおしまい。

# Codeforces Round #606 (Div. 2) D. Let's Play the Words?
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    q = int(input())
    for _ in range(q):
        n = int(input())
        s = [str(input()) for k in range(n)]
        a, b, c, d = 0, 0, 0, 0
        C = dict()
        D = dict()
        for k in range(n):
            e = s[k]
            if e[0] == "0" and e[-1] == "0":
                a += 1
            elif e[0] == "1" and e[-1] == "1":
                b += 1
            elif  e[0] == "0" and e[-1] == "1":
                c += 1
                C[e] = k+1
            else:
                d += 1
                D[e] = k+1
        if c == d == 0 and a*b > 0:
            print(-1)
        else:
            diff = abs(c-d)//2
            print(diff)
            if diff == 0:
                print("")
            else:
                ans = []
                if c > d:
                    for e in C:
                        if e[::-1] not in D:
                            ans.append(C[e])
                        if len(ans) == diff:
                            break
                else:
                    for e in D:
                        if e[::-1] not in C:
                            ans.append(D[e])
                        if len(ans) == diff:
                            break
                print(*ans)

if __name__ == '__main__':
    main()