테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 피아의 아틀리에 ~신비한 대회의 연금술사~ ======

===== 풀이 =====
  * 기본적으로는 모든 경우의 수를 다 시도해보는 것 밖에 다른 방법은 없다. 구현이 좀 귀찮지만, 차근차근 하면 어렵지는 않다.
  * 어려운 점은, 파이썬 기준으로 시간이 꽤나 빡빡하다는 것. 순서있게 재료 3개를 고르는 경우의 수는 P(n,3)이고, 각 재료마다 4가지의 로테이션과 4가지의 시작 위치를 가지므로, 총 P(n,3)*(4*4)^3 번의 시뮬레이션을 해야 한다. n=10일때에 이 값은 2,949,120 이다. 매 시뮬레이션마다, 25칸에 대해서 업데이트를 3회 해주고, 25칸에 대해서 점수를 계산해야 하므로, 이 연산량을 대략 O(100) 이라고 하면, 총 연산횟수가 대략 3억정도가 되는데, 파이썬 기준으로는 이 연산을 추가시간 없는 3초에 완료하는게 상당히 빡빡해진다.
  * 파이썬으로 통과시키기 위해서는 여러가지 구현 최적화가 필요하다. 하지만 가장 핵심 아이디어는 시뮬레이션 횟수를 줄이는 것이다. 간단히 생각해서, 세개의 재료를 전부 (1,1)을 기준으로 넣는 것과 (2,2)을 기준으로 넣는 것은 같은 결과를 낸다. 로테이션까지 고려해서 생각해보면, 첫번째 재료를 (1,1) 이외에 넣는 경우는 모두, 첫번째 재료를 (1,1)에 넣고 회전시켜서 동일한 결과를 낼 수 있는 방법이 있다는 것을 알 수 있다. 이렇게 생각하면 첫번째 재료의 위치는 (1,1)로 고정시켜도 충분하고, 간단하게 시뮬레이션 횟수를 1/4 로 줄일 수가 있다.
  * 그 외에는 구현 방식의 차이이다. 가마 행렬과 재료 행렬을 모두 1차원 배열로 저장한다든가, 최종 점수를 구할때 루프 대신 math.sumprod()를 쓴다든가 하는 몇몇 최적화를 추가하면 pypy뿐 아니라 python3으로도 3초 안에 통과시키는 것이 가능하다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 15898. 피아의 아틀리에 ~신비한 대회의 연금술사~".

- Problem link: https://www.acmicpc.net/problem/15898
- Solution link: http://www.teferi.net/ps/problems/boj/15898

Tags: [implementation]
"""

import itertools
import math

SCORE_BY_COLOR = {'R': 7, 'B': 5, 'G': 3, 'Y': 2, 'W': 0}
OFFSETS = [0, 1, 5, 6]


def create_rotated_arrays(mat):
    seqs = []
    for _ in range(4):
        mat = list(zip(*reversed(mat)))
        seq = []
        for row in mat:
            seq.extend(row)
            seq.append(0)
        seq.pop()
        seqs.append(seq)
    return seqs


def apply(e_cur, c_cur, ingre, offset):
    e_next, c_next = e_cur[:], c_cur[:]
    ingre_e, ingre_c = ingre
    for i, x in enumerate(ingre_e, start=offset):
        e = e_next[i] + x
        e_next[i] = 0 if e < 0 else (9 if e > 9 else e)
    for i, x in enumerate(ingre_c, start=offset):
        if x > 0:
            c_next[i] = x
    return e_next, c_next


def main():
    n = int(input())
    ingre_arrs = []
    for _ in range(n):
        effect_mat = [[int(x) for x in input().split()] for _ in range(4)]
        color_mat = [input().split() for _ in range(4)]

        color_mat = [[SCORE_BY_COLOR[c] for c in row] for row in color_mat]
        e_arrs = create_rotated_arrays(effect_mat)
        c_arrs = create_rotated_arrays(color_mat)
        ingre_arrs.append(list(zip(e_arrs, c_arrs)))

    answer = 0
    e0 = c0 = [0] * 25
    for ingre1, ingre2, ingre3 in itertools.permutations(ingre_arrs, 3):
        for i1 in ingre1:
            e1, c1 = apply(e0, c0, i1, 0)
            for i2, o2 in itertools.product(ingre2, OFFSETS):
                e2, c2 = apply(e1, c1, i2, o2)
                for i3, o3 in itertools.product(ingre3, OFFSETS):
                    e3, c3 = apply(e2, c2, i3, o3)
                    if (quality := math.sumprod(e3, c3)) > answer:
                        answer = quality

    print(answer)


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_1}}