今日の精進(20200105)

AirPort Bus

Tをソートしてバスに客をどんどん詰め込んでいく。定員になるか同じバスに乗っている人の時差の最大値がKを超えたらバスを+1台する。

# coding: utf-8  
N, C, K = map(int, input().split())  
T = []  
for i in range(N):  
    t = int(input())  
    T.append(t)  
T.sort()  
# print(T)  
ans = 0  
s = T[0]  
cnt = 1  
for i in range(1,N):  
    if cnt >= C:  
        ans += 1  
        cnt = 1  
        s = T[i]  
    else:  
        if T[i] - s <= K:  
            cnt += 1  
        else:  
            ans += 1  
            cnt = 1  
            s = T[i]  
if cnt != 0:  
    ans += 1  
print(ans)  

掲示板

昇順に並べた配列と書き込みが発生した順の配列を用意して、未出のものだけ出力する。

# coding: utf-8  
import heapq  
N, M = map(int, input().split())  
# L = [[i, 0] for i in range(1, N+1)]  
T = [True] * N  
l1 = [i+1 for i in range(N)]  
l2 = []  
for i in range(M):  
    a = int(input())  
    l2.append(a)  
L = l2[::-1] + l1  
for i in range(len(L)):  
    if T[L[i]-1]:  
        print(L[i])  
        T[L[i]-1] = False  

Candies

ある座標に来る方法は左から来るか上からくるかなので、大きい方を選択して行くのを(N,2)まで繰り返す。DPってこんな感じだったよなと思いながら実装した。

# coding: utf-8  
N = int(input())  
A = []  
for _ in range(2):  
    A.append(list(map(int, input().split())))  
dp = [[0 for _ in range(N)] for _ in range(2)]  
# dp = np.array(dp)  
dp[0][0] = A[0][0]  
dp[1][0] = A[0][0] + A[1][0]  
for i in range(1, N):  
    dp[0][i] = dp[0][i-1] + A[0][i]  
    dp[1][i] = max(dp[0][i], dp[1][i-1]) + A[1][i]  
print(dp[1][N-1])  

Flip,Flip, and Flip......

そのマスをひっくり返す回数を考える。偶数の場合表になり、奇数の場合裏になる。奇数回ひっくり返るのは長方形に並んだマスの内側なので、すべてのマスから外側を引いた値が答え。

# coding: utf-8  
N, M = map(int, input().split())  
print(abs(N * M - (N + M) * 2 + 4))  

Switches

前にやった問題だったが少し手間取った。制約が小さいのでbit全探索を用いる。

# coding: utf-8  
N, M = map(int, input().split())  
S = []  
for i in range(M):  
    tmp = list(map(int, input().split()))  
    S.append(tmp[1:])  
P = list(map(int, input().split()))  
ans = 0  
# print(S)  
for bit in range(2**N):  
    l = []  
    for j in range(N):  
        if bit >> j & 1 == 1:  
            l.append(1)  
        else:  
            l.append(0)  
    flag = True  
    for j in range(M):  
        t = S[j]  
        cnt = 0  
        for k in range(len(S[j])):  
            if l[t[k]-1] == 1:  
                cnt += 1  
            # else:  
            #     flag = False  
        if cnt % 2 != P[j]:  
            flag = False  
    if flag:  
        # print(bin(bit))  
        ans += 1  
print(ans)