AtCoder Beginner Contest 165を振り返る

今回もPythonで挑戦しました。

A - We Love Golf

ジャンボ高橋君はゴルフの練習をすることにしました。ジャンボ高橋君の目標は飛距離をKの倍数にすることですが、ジャンボ高橋君の出せる飛距離の範囲は A以上 B以下です。目標の達成が可能であれば OK と、不可能であれば NG と出力してください。

で、入力が以下の様に与えられます。

K
A B

私は以下の様に範囲内の全部の値をKで割って割り切れるものがあるか確認すると言う力任せの方法で解きましたが

k = int(input())
a,b = map(int, input().split())
print("OK" if any([i%k==0 for i in range(a,b+1)]) else "NG")

解説を見ていると、以下の様に「b以下で最大のkの倍数がa以上であるかを求める」のが良さげ

print("OK" if a <= b//k*k else "NG")

これは思いつきたかったな。

B - 1%

高橋くんはAtCoder銀行に 100円を預けています。
AtCoder銀行では、毎年預金額の 1% の利子がつきます(複利、小数点以下切り捨て)。
利子以外の要因で預金額が変化することはないと仮定したとき、高橋くんの預金額が初めて X円以上になるのは何年後でしょうか。

問題文読み間違って「X円を超えるのは」で提出してしまい、「WA」になった問題以下の方法で解きました

c = 100
y = 0
x = int(input())
while True:
   if c>=x:
       print(y)
       break
   c = int(c*1.01)
   y += 1

これの回答方法も以下の方が小数使わなくていいですしスマートですね。

while True:
   if c>=x:
       print(y)
       break
   c += c//100
   y += 1

C - Many Requirements

問題文に添字が多いので以下を参照

C - Many Requirements

問題の理解に30分かかり、解法はわかったけどコードに落とし込めずに時間が終了。残念。

解説みつつ、何人かの解答みつつ作ったコードが以下。

N, M, Q = map(int, input().split())
lists = [list(map(int, input().split())) for i in range(Q)]
ans = 0

def calc_score(A):
   score = 0
   for a, b, c, d in lists:
       if A[b - 1] - A[a - 1] == c:
           score += d
   return score

def dfs(A):
   global ans
   if len(A) == N:
       score = calc_score(A)
       ans = max(score, ans)
       return
   for n in range(A[-1], M + 1):
       dfs(A + [n])

dfs([1])
print(ans)

結構さっぱり書けるもんですね。pythonだと「itertools」を使うとdfsは使わなくて良いです。
ちなみに、書いて見て思いましたが、これは今のところ何も参照せずには出来ないですね。

所感

解説動画についたコメントとか見てても今回は比較的難しかったらしい。慣れればもうちょっと早く問題が理解できただろうと思われる。今晩もあるらしいので挑戦して見たいと思う。