AtCoder Beginner Contest 153 ／ Python

• 初学者です。（ 2019 / 9 ～ 現在５ヵ月目 ）
• AtCoder の問題に Python で取り組んでいます。
• ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントください。

今回は４問目までが非常に簡単だった。
お陰で結局のところ４問目までのタイム勝負だ。
せっかく４問目まで解けたが、順位は上がらず。

そういえば、問題文が「けもフレ」だったことは触れた方が良いのだろうか。

まあ良い、そんなことは良いんだ。

結果

地味ぃ。

問題と解答と勉強

atcoder.jp

提出したコード

H,A = map(int,input().split())
 
if H % A==0:
    print(H//A)
else:    
    print(H//A + 1)

なんかダサい。

と思ったので他の人のを漁ってみた。

import math

H,A = map(int,input().split())

print(math.ceil(H/A))

この方がイケメン。

atcoder.jp

提出したコード

H,N = map(int,input().split())
A = list(map(int,input().split()))
 
if H <= sum(A):
    print("Yes")
else:
    print("No")

atcoder.jp

提出したコード

H,K = map(int,input().split())
H = list(map(int,input().split()))
 
if len(H) <= K:
    print(0)
 
else:
    H_s = sorted(H)
    print(sum(H_s[:len(H)-K]))

atcoder.jp

提出したコード

H = int(input())
 
for i in range(1,100):
    if H < 2**i :
        print(2**i - 1)
        break

プログラマ的にはワカラナ気味だったので、数学で解いてしまった。



こういうことなので、Hが２の何乗より小さいか求まれば良い。

もっとプログラムっぽい解き方があるんじゃないかと思ったのだが、
ほとんど皆こんな解答だったので、これで良いらしい。

一つカッコいいの見つけた。

print(2**int(input()).bit_length()-1)

一行かよ、プログラマっぽい。

atcoder.jp

動的計画法っぽいな、というのはわかったのだが、コードにしきれなかった。

流石に悔しいので終わった後に自力で考えた。

H,N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
    
DP =[0]*(H+1)

for i in range(1,H+1):
    dp = []
    for j in range(len(A)):
        
        if i-A[j]>=0:
            dp.append(DP[i-A[j]] + B[j])
        else:
            dp.append(B[j])
    DP[i] = min(dp)        

print(DP[-1])

多分こういうことだと思われる。

ただし、上のコードはforが２重になっているので時間的にダメだ。

import numpy as np
 
H,N = list(map(int, input().split()))
A = []
B = []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)
DP = np.zeros(H+1)

for i in range(1,H+1):
    DP[i] = np.amin(DP[np.maximum(i - A, 0)] + B)
    
print(int(DP[-1]))

やってることは同じだが、numpyを使えばループが減らせる。

メモ：

numpyでappendをやるとめっちゃ遅くなるらしいので、
ループから出た後に入れるようにするそうだ。



これさ、めっっちゃ考えれば出来ると言えば出来るのだが、

時間内に解けないよ。

10時40分に終わって、今、これ書いてるの深夜２時半だからね。

十数分とかで全部解けてる人はどうなってるの？？

atcoder.jp

という訳で、お疲れちゃんなので、６問目はパスさせて頂きます。



はぁ～、動的計画法がスラスラ書けるレベルになりたいわ。