hirohirohirohirosのブログ

地方国立大学に通う情報系学部4年

Atcoder ABC256 振り返り

A - 2^N【AC】

 pythonで累乗は**とします.

print(2**int(input()))
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