競技プログラミング 日記 python 20201213

• A - ABC Preparation

与えられた4つの数字の最も小さい物を出力すれば良い

print(min(list(map(int, input().split()))))

• B - Smartphone Addiction

コードは汚いが、カフェに入ったタイミングと終了時にバッテリーが0以下かどうを判定すれば良さそうという思想で実装
バッテリーは最大容量以上にはならないことを最初忘れていたのがミス

n, m, t = map(int, input().split())
max_n = n
now = 0
ans = "Yes"
for i in range(m):
    a, b = map(int, input().split())
    n = n - a + now
    if n <= 0:
        ans = "No"
        break
    n = min(n + (b - a), max_n)
    now = b
if n - t + now <= 0:
    ans = "No"
    
print(ans)    

• C - Duodecim Ferra

長さLのぼうを11箇所で切断するときの分け方が何通りか。受験でよく出そうな問題ではある

整数の長さになるよう分割なので、切断箇所は L - 1箇所。 L - 1 C 11 とかで求まるか

from math import factorial

L = int(input())

print(int(factorial(L - 1) / factorial(L - 12) / factorial(11)))

と思ったが、これではだめ。
解説を読むと

注意しなければいけないのは、この分数自体の値は
2 ** 63
未満ですが、分子は
64 bit 整数型に収まらないことがあるという点です。オーバーフローを回避する方法はいくつかあります。

int64のサイズを超えるからアウトか。。この発想はなかった。
パスカルの三角形を用いて、漸化式敵に解くのが良さそう

メモ化再帰のようなことをしてみた。関数が副作用満点なので気持ち悪い

from math import factorial

L = int(input())
matrix = [[[] for _ in range(201)] for _ in range(201)]

def pascal(i, j):
    if matrix[i][j]:
        return matrix[i][j]
    if j == 0 or i == j:
        return 1
    ans = pascal(i-1, j-1) + pascal(i-1, j)
    matrix[i][j] = ans
    return(pascal(i-1, j-1) + pascal(i-1, j))
    
print(pascal(L-1, 11))

• D - Stamp

スタンプの作り方は、白いマスの連続する数のうち最も小さい物を採用すればよさそう
幅4のスタンプなら、5のますはスタンプを２回使うことで塗りつぶすことができる

n, m = map(int, input().split())
if m == 0:
    print(1)
    exit()

a = sorted(list(map(int, input().split())))
white = []
for i in range(len(a)):
    if i == 0:
        white.append(a[i] - 1)
    elif i == (len(a) - 1):
        white.append(a[i] - a[i-1] -1)
        white.append(n - a[i])
    else:
        white.append(a[i] - a[i-1] -1)
white = list(filter(lambda x: x != 0, white))
if len(white) == 0:
    print(0)
    exit()
k = min(white)

ans = 0
for l in white:
    x = l // k
    amari = l % k
    if amari != 0:
        x += 1
    ans += x

print(ans)

かなり場当たり的だが、、一応通った

今回はここまで！