TV Show Game

• At-most-one 조건을 사용하는 2-SAT문제
• x,y,z 중에서 2개 이상이 True이다 ⇔ 1개 이하가 False이다. ⇔ ~x,~y,~z 중 최대 1개가 True이다. 이렇게 at-most-one 형태로 바꿔줄수 있다. at-most-one을 인코딩할때는 변수가 3개뿐이므로 그냥 pairwise로 처리하면 된다. 사실 이렇게 단계를 거쳐서 생각하지 않고 그냥 어떤 페어를 잡아도 1개 이상은 True이므로 페어마다 or절을 만든다고 심플하게 생각해도 되긴 한다.
• 시간복잡도는 O(n+m)

"""Solution code for "BOJ 16367. TV Show Game".

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

Tags: [2-Sat]
"""

import sys
from teflib import twosat


def main():
    k, n = [int(x) for x in sys.stdin.readline().split()]
    two_sat = twosat.TwoSat(k)
    for _ in range(n):
        l1, c1, l2, c2, l3, c3 = sys.stdin.readline().split()
        x1 = int(l1) - 1 if c1 == 'B' else -int(l1)
        x2 = int(l2) - 1 if c2 == 'B' else -int(l2)
        x3 = int(l3) - 1 if c3 == 'B' else -int(l3)
        two_sat.at_most_one((x1, x2, x3))

    try:
        assignment = two_sat.find_truth_assignment()
    except ValueError:
        print('-1')
    else:
        print(''.join('R' if x else 'B' for x in assignment))


if __name__ == '__main__':
    main()

• Dependency: teflib.twosat.TwoSat