D - パスタ (Pasta)
bit全探索は厳しいので，DPを使ってとく．指定されたソースを使う日の処理，最後に10000で割ることに注意して実装する．
n, k = map(int, input().split()) ab = [list(map(int, input().split())) for _ in range(k)] dp = [[0 for _ in range(6)] for _ in range(n)] ab.sort(key=lambda x: x[0]) if ab[0][0] == 1: dp[0][ab[0][1]-1] = 1 cnt = 1 else: for i in range(0,6,2): dp[0][i] = 1 cnt = 0 for i in range(n - 1): if cnt < k: if ab[cnt][0] == i + 2: for j in range(6): if j // 2 != ab[cnt][1] - 1: #新しいソース dp[i+1][2 *(ab[cnt][1] - 1)] += dp[i][j] elif j == 2 * (ab[cnt][1] - 1): #同じソース dp[i+1][j + 1] += dp[i][j] cnt += 1 else: for j in range(6): if j % 2 == 0: for m in range(6): if m % 2 == 0 and j != m: #新しいソース dp[i+1][m] += dp[i][j] elif m % 2 == 1 and j + 1 == m: #同じソース dp[i+1][m] += dp[i][j] else: for m in range(6): if m % 2 == 0 and j - 1 != m: #新しいソース dp[i+1][m] += dp[i][j] else: for j in range(6): #iのソース if j % 2 == 0: for m in range(6): #i+1のソース if m % 2 == 0 and j != m: #新しいソース dp[i+1][m] += dp[i][j] elif m % 2 == 1 and j + 1 == m: #同じソース dp[i+1][j + 1] += dp[i][j] else: for m in range(6): if m % 2 == 0 and j - 1 != m: #新しいソース dp[i+1][m] += dp[i][j] ans = sum(dp[-1]) % 10000 print(ans)
二つのelse文は完全に同じなので，きれいに書く方法を見付けたい
