結果

問題 No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木
コンテスト
ユーザー LyricalMaestro
提出日時 2026-04-13 23:39:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 493 ms / 2,000 ms
コード長 2,424 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 200 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 127,204 KB
最終ジャッジ日時 2026-04-13 23:39:34
合計ジャッジ時間 11,744 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/1780

ALPHA_NUM = 26
NODE_NUM = 16

MIN_INT = -float("inf")

def main():
    C = list(map(int, input().split()))
    K = list(map(int, input().split()))
    N = int(input())
    S = []
    for _ in range(N):
        s, a, b, e = input().split()
        S.append((s, int(a), int(b), int(e)))

    # matrix構築
    matrix_list = [[[MIN_INT for _ in range(NODE_NUM)] for _ in range(NODE_NUM)] for _ in range(ALPHA_NUM)]
    for i in range(ALPHA_NUM):
        for j in range(NODE_NUM):
            matrix_list[i][j][j] = 0

    for i in range(N):
        s, a, b, e = S[i]
        s = set([s0 for s0 in s])
        a -= 1
        b -= 1

        for s0 in s:
            s1 = ord(s0) - ord("A")
            matrix_list[s1][a][b] = max(matrix_list[s1][a][b], e)
            matrix_list[s1][b][a] = max(matrix_list[s1][b][a], e)

    def prod_vector(matrix, vector):
        new_vector = [MIN_INT for _ in range(NODE_NUM)]
        for i in range(NODE_NUM):
            for j in range(NODE_NUM):
                new_vector[i] = max(new_vector[i], matrix[i][j] + vector[j])
        return new_vector
    
    def prod_matrix(left, right):
        new_matrix = [[MIN_INT for _ in range(NODE_NUM)] for _ in range(NODE_NUM)]
        for i in range(NODE_NUM):
            for j in range(NODE_NUM):
                for k in range(NODE_NUM):
                    new_matrix[i][j] = max(new_matrix[i][j], left[i][k] + right[k][j])
        return new_matrix


    dp_list = []
    for alpha in range(ALPHA_NUM):
        k = K[alpha]

        vector = [MIN_INT for _ in range(NODE_NUM)]
        vector[C[alpha] - 1] = 0
        base_matrix = matrix_list[alpha]
        while k > 0:
            if k % 2 == 1:
                vector = prod_vector(base_matrix, vector)

            base_matrix = prod_matrix(base_matrix, base_matrix)
            k //= 2

        dp_list.append(vector)

    # 答え
    answer = MIN_INT
    for target_color in range(NODE_NUM):
        is_ok = True
        value = 0
        for alpha in range(ALPHA_NUM):
            if dp_list[alpha][target_color] == MIN_INT:
                is_ok = False
                break
            else:
                value += dp_list[alpha][target_color]
        if is_ok:
            answer = max(answer, value)


    if answer == MIN_INT:
        print("Impossible")
    else:
        print(answer)



if __name__ == '__main__':
    main()
0