LINE Verda Programming Contest (AtCoder ABC 263) 参戦記

Dまでの4完。

Eはうまく整理しきれず。

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    A, B, C, D, E = map(int, input().split())
    L = [A, B, C, D, E]
    N = dict()
    for l in L:
        if l in N: N[l] += 1
        else: N[l] = 1
    for key in N:
        if N[key] == 3:
            for skey in N:
                if N[skey] == 2:
                    print("Yes")
                    return 0
    print("No")
    return 0
  
if __name__ == "__main__":
    solve()

気合です。

3つ同じかつ2つ同じものがあればYes, それ以外は全部Noです。

B問題 (Ancestor)

def solve():
    input = sys.stdin.readline 
    N = int(input())
    P = list(map(int, input().split()))
    count = 0
    current = N-1
    while current > 0:
        current = P[current - 1] - 1
        count += 1
    print(count)
    return 0
  
if __name__ == "__main__":
    solve()

シミュレーションです。

いまどれを見ているかと何世代目かを持っておいて、今見ているものが1になった時点の世代を出力します。

C問題 (Monotonically Increasing)

from collections import deque
def solve():
    input = sys.stdin.readline 
    N, M = map(int, input().split())
    # i桁目のlimitはM - N + i + 1
    dq = deque()
    dq.append(("", 0, 0))
    for i in range(N):
        while True:
            L, index, minL = dq.popleft()
            if index > i: 
                dq.appendleft((L, index, minL))
                break
            else:
                # print(minL)
                for j in range(minL + 1, min(M + N + i + 1, M + 1)):
                    if i == 0: dq.append((str(j), index + 1, j))
                    else: dq.append((L + " " + str(j), index + 1, j))
                    # print(dq)
    while dq:
        L, index, minL = dq.popleft()
        if index == N: print(L)
    return 0
  
if __name__ == "__main__":
    solve()

combinations(range(M), N)でもしかしてよい？ということに今気づきました。

dequeに先頭から突っ込んでいって実際に辞書順で数列を生成していました。

途中で後ろの方が確実にMより大きくなってしまう場合は探索を打ち切るようにしています。

combinations使えば上のようなめんどくさいことをせずに↓のように一発で終わりますね...

from itertools import combinations
def solve():
    input = sys.stdin.readline 
    N, M = map(int, input().split())
    for c in combinations(range(1, M+1), N):
        print(*c, sep=" ")
    return 0
  
if __name__ == "__main__":
    solve()

D問題 (Left Right Operation)

def solve():
    input = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9
    N, L, R = map(int, input().split())
    A = list(map(int, input().split()))
    AL = [[INF, INF] for _ in range(N)] # Aiはそのまま、AiまでLに変換
    AL[0][0] = A[0]
    AL[0][1] = L
    for i in range(1, N):
        AL[i][0] = min(min(AL[i-1][0] + A[i], AL[i-1][1] + A[i]), AL[i][0])
        AL[i][1] = AL[i-1][1] + L
    
    minSum = min(sum(A), AL[N-1][0])
    for i in reversed(range(1, N)):
        # i以降をRにする場合
        rcount = N - i
        if i == 1: S = A[0] + R * rcount
        else: S = min(AL[i-1]) + R * rcount
        minSum = min(S, minSum)
    minSum = min(minSum, L * N)
    minSum = min(minSum, R * N)
    print(minSum)
    # print(AL)
    return 0
  
if __name__ == "__main__":
    solve()

どこまで一括で更新するか決めれば、その時の合計値についてはすぐ計算できますが、左右どちらも探索すると間に合わないです。

そこで左側の一括変換に関してはAiまでの和の最小値を事前に計算しておくことで、右側の一括変換だけ探索すれば済むようにします。

左側の事前計算としては、どこまでLで一括変換したかは分からないけどAiを変換しなかったときの和の最小値と、AiまでLで変換したときの値でDPをしています。

アールグレー特売所

ゲームやら競プロやらのメモ書き

LINE Verda Programming Contest (AtCoder ABC 263) 参戦記