Atcoder ABC256 振り返り
B - Batters【AC】
マスをAAで表し,そのマスにコマが置かれていることを1,置かれていないことを0として表します.AA[j]が1ならAA[j]を0にしてAA[j+A[i]]を1にします.AA[j+A[i]]が4以上ならPに+1します.これは,マスを決められた分だけ前に動かす操作をしています.これを繰り返す事で求まります.
N = int(input()) A = [int(i) for i in input().split()] P = 0 AA = [0 for i in range(4)] for i in range(N): AA[0] = 1 for j in range(3, -1, -1): if AA[j] == 1: AA[j] = 0 if j + A[i] > 3: P += 1 else: AA[j+A[i]] = 1 print(P)
C - Filling 3x3 array【AC】
ぱっと見どう解けば良いか分からずこの問題を飛ばしましたが,制約が30以下であることをヒントに考えます.これだけ制約が小さいと,全探索をしても間に合いそうです.
各行に対して, h1, h2, h3のルールを守るような数字の並びを全て列挙します.例えば,h1=3なら[1,1,1]のみですし,h1=4なら[1,1,2],[1,2,1],[2,1,1]です.これの全列挙のやり方は1<=i<=30, 1<=j<=30でループさせ, i+jがh1未満なら,[i, j, h1-i-j]とすれば良いです.
h1, h2, h3について各パターンの候補を全て列挙したら,それらを全て組み合わせ,w1, w2, w3を満たしていれば成立することになります.
num = [int(i) for i in input().split()] h1_list = [] h2_list = [] h3_list = [] for i in range(1, 30): for j in range(1, 30): if i + j < num[0]: h1_list.append([i, j, num[0]-i-j]) for i in range(1, 30): for j in range(1, 30): if i + j < num[1]: h2_list.append([i, j, num[1]-i-j]) for i in range(1, 30): for j in range(1, 30): if i + j < num[2]: h3_list.append([i, j, num[2]-i-j]) ans = 0 for h1 in h1_list: for h2 in h2_list: for h3 in h3_list: if h1[0]+h2[0]+h3[0] == num[3] and h1[1]+h2[1]+h3[1] == num[4] and h1[2]+h2[2]+h3[2] == num[5]: ans += 1 print(ans)
D - Union of Interval【AC】
開集合はソートしても答えは変わらない事に注意します.
どのような状態が成立したら開集合を合成できるか考えます.下の図で,上側の開集合を[L1, R1)下側の開集合を[L2, R2)とします.左のパターンでは2つの開集合を1つに合成できますが,右のパターンでは合成できません.
左右の違いは,L2の位置です.L1
import bisect N = int(input()) L = set() lr_dic = {} for _ in range(N): l, r = map(int, input().split()) L.add(l) lr_dic.setdefault(l, 0) lr_dic[l] = max(lr_dic[l], r) L = sorted(list(L)) L.append(10**6) lr_dic[10**6] = 10**7 ans = set() i = 1 now = L[0] if N == 1: print(now, lr_dic[now]) else: while True: if now < L[i] <= lr_dic[now]: lr_dic[now] = max(lr_dic[now], lr_dic[L[i]]) else: print(now, lr_dic[now]) now = L[i] i += 1 if i == len(L)-1 : print(now, lr_dic[now]) break