A. 文字列生成の列挙処理

入力された2文字が同一か否かを判定し、条件を満たす文字列候補を列挙する。同一文字の場合は長さ1と2の2通り、異なる文字の場合は単体および結合形の計4通りを出力すればよい。

def solve_string_gen():
    c1, c2 = input().split()
    if c1 == c2:
        print(2)
        print(c1)
        print(c1 * 2)
    else:
        print(4)
        print(c1)
        print(c2)
        print(c1 + c2)
        print(c2 + c1)

solve_string_gen()

B. 非順列化の最小操作

与えられた数列が1からNまでの順列として成立しているかを検証する。すでに重複や範囲外の値が含まれていれば操作不要（0回）。完全な順列である場合、先頭要素を範囲外の数（N+1）に置換することで条件を解除でき、操作回数は1回となる。

def solve_non_perm():
    size = int(input())
    seq = list(map(int, input().split()))
    
    valid_nums = {v for v in seq if 1 <= v <= size}
    if len(valid_nums) != size:
        print(0)
    else:
        print(1)
        print(f"1 {size + 1}")

solve_non_perm()

C. 数値列の貪欲的分割

文字列を先頭から走査し、各セグメントが最初に偶数に到達した時点で区切る処理を行う。取得した部分文字列群を、長さの昇順および辞書順でソートして出力する。

def solve_digit_split():
    raw = input().strip()
    segments = []
    start = 0
    n = len(raw)
    
    while start < n:
        end = start
        while end < n and int(raw[end]) % 2 != 0:
            end += 1
        if end < n:
            end += 1
        segments.append(raw[start:end])
        start = end
        
    segments.sort(key=lambda x: (len(x), x))
    print('\n'.join(segments))

solve_digit_split()

D. 隣接差総和制御の数列構築

隣接要素の絶対差の合計が厳密に1となる配列を構築する。全要素が0の場合や、既存の非零要素間の差が1を超える場合は不可能として-1を返す。中間の未定義要素は直近の非零値で埋め、両端の値は総和条件を満たすように±1調整を行う。

def solve_steep_array():
    n = int(input())
    arr = list(map(int, input().split()))
    
    if all(v == 0 for v in arr):
        if n == 1:
            print(-1)
        else:
            print(1, *[2] * (n - 1))
        return
        
    nonzero = [v for v in arr if v > 0]
    current_diff = sum(abs(nonzero[i] - nonzero[i+1]) for i in range(len(nonzero)-1))
    
    if current_diff > 1:
        print(-1)
        return
        
    first = next(i for i, v in enumerate(arr) if v != 0)
    last = n - 1 - next(i for i, v in enumerate(reversed(arr)) if v != 0)
    
    prev = arr[first]
    for k in range(first + 1, last):
        if arr[k] == 0:
            arr[k] = prev
        else:
            prev = arr[k]
            
    if current_diff == 1:
        for k in range(first): arr[k] = arr[first]
        for k in range(last + 1, n): arr[k] = arr[last]
        print(*arr)
    else:
        if first > 0:
            for k in range(first): arr[k] = arr[first] + 1
            for k in range(last + 1, n): arr[k] = arr[last]
            print(*arr)
        elif last + 1 < n:
            for k in range(last + 1, n): arr[k] = arr[last] + 1
            print(*arr)
        else:
            print(-1)

solve_steep_array()

E. 木構造の二色塗り分け検証

木グラフ上の頂点を二部グラフの要領で彩色する。初期色が確定している頂点から幅優先探索を開始し、隣接頂点へ交互に色を伝播させる。探索完了後、全ての辺において両端の頂点色が異なっているかを検証し、矛盾があれば-1、成功すれば最終状態の文字列を出力する。

from collections import deque
import sys

def solve_tree_coloring():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    state = list(next(it))
    adj = [[] for _ in range(n)]
    
    for _ in range(n - 1):
        u, v = int(next(it)) - 1, int(next(it)) - 1
        adj[u].append(v)
        adj[v].append(u)
        
    queue = deque()
    for idx, ch in enumerate(state):
        if ch != '?':
            queue.append((idx, ch))
            
    if not queue:
        state[0] = 'd'
        queue.append((0, 'd'))
        
    while queue:
        node, color = queue.popleft()
        opp = 'p' if color == 'd' else 'd'
        for nb in adj[node]:
            if state[nb] == '?':
                state[nb] = opp
                queue.append((nb, opp))
                
    valid = True
    for i in range(n):
        if state[i] == '?':
            valid = False
            break
        target = 'p' if state[i] == 'd' else 'd'
        if any(state[nb] != target for nb in adj[i]):
            valid = False
            break
            
    print(-1 if not valid else ''.join(state))

solve_tree_coloring()

F. XOR総和制御行列の構築

全要素の排他的論理和（XOR）が指定値Xとなる行列を生成する。Xが4の倍数の場合は特定領域に均等配置し、それ以外の場合は基本パターンに余剰値を加算する。X=2の場合は解が存在しないため-1を返す。

def solve_xor_matrix():
    H, W, target = map(int, input().split())
    mat = [[0] * W for _ in range(H)]
    
    if target % 4 == 0:
        val = target // 4
        for r in range(min(2, H)):
            for c in range(min(2, W)):
                mat[r][c] = val
        for row in mat: print(*row)
    elif target == 2:
        print(-1)
    else:
        if H >= 3 and W >= 3:
            mat[2][0] = mat[2][1] = 1
            mat[1][0] = mat[1][2] = 1
            mat[0][1] = mat[0][2] = 1
            rem = (target - 6) // 4
            for r in (0, H-1):
                for c in (0, W-1):
                    mat[r][c] += rem
        for row in mat: print(*row)

solve_xor_matrix()

G. 色制約付き置換環による最小交換

配列を置換環に分解し、各環内の色の構成に基づいて交換回数を算出する。環内に両方の色が含まれる場合は環のサイズ-1回で整列可能だが、単色環の場合は外部環からの借用が必要となり+2コストが発生する。単色のR環とW環がペア化できる場合、相互借用により合計2回の交換を節約できるため、最適化を適用する。

from collections import Counter

def solve_min_swaps():
    n = int(input())
    perm = list(map(int, input().split()))
    colors = input().strip()
    
    if perm == list(range(1, n + 1)):
        print(0)
        return
    if len(set(colors)) == 1:
        print(-1)
        return
        
    ops = 0
    mono_r = 0
    mono_w = 0
    visited = [False] * n
    
    for i in range(n):
        if visited[i] or perm[i] == i + 1:
            continue
            
        length = 0
        has_r = has_w = False
        curr = i
        
        while not visited[curr]:
            visited[curr] = True
            length += 1
            if colors[curr] == 'R': has_r = True
            else: has_w = True
            curr = perm[curr] - 1
            
        base = length - 1
        if has_r and has_w:
            ops += base
        else:
            ops += base + 2
            if has_r: mono_r += 1
            else: mono_w += 1
            
    print(ops - 2 * min(mono_r, mono_w))

solve_min_swaps()