ABC165 - Atcoder/Python精進のための解説メモ

カレンダーアイコン
2021/06/14

ABC165 - A.We Love Golf

AtCoder公式 | ABC165 - A.We Love Golf

解答

k = int(input())
a, b = map(int, input().split())
ans = 'NG'
for i in range(a, b + 1):
    if i % k == 0:
        ans = 'OK'
print(ans)

要点解説メモ

  • シンプルにやる

ABC165 - B.1%

AtCoder公式 | ABC165 - B.1%

解答

n = int(input())
x = 100
ans = 0
while x < n:
    x = int(x * 1.01)
    ans += 1
print(ans)

要点解説メモ

  • ちょっと小数が怖いけど、そのままやるだけ

ABC165 - C.Many Requirements

AtCoder公式 | ABC165 - C.Many Requirements

解答

import itertools
n, m, q = map(int, input().split())
abcds = [list(map(int, input().split())) for _ in range(q)]
aaa = range(1, m + 1)
ans = 0
for a in itertools.combinations_with_replacement(aaa, n):
    list(a).sort()
    tmp = 0
    for abcd in abcds:
        if a[abcd[1] - 1] - a[abcd[0] - 1] == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)

別解

n, m, q = map(int, input().split())
abcds = [list(map(int, input().split())) for _ in range(q)]

def dfs(pos, aaa, m, abcds):
    if pos == len(aaa):
        score = 0
        for abcd in abcds:
            if aaa[abcd[1] - 1] - aaa[abcd[0] - 1] == abcd[2]:
                score += abcd[3]
        return score

    ans = 0
    low = 1 if pos == 0 else aaa[pos - 1]

    for i in range(low, m + 1):
        aaa[pos] = i
        ans = max(ans, dfs(pos + 1, aaa, m, abcds))
    return ans

print(dfs(0, [0] * n, m, abcds))

要点解説メモ

  • 愚直に全探索すると間に合わない
  • itertools使うと簡単に書けるけど、dfs再帰関数をちゃんと書けるようにしておきたいところ

ABC165 - D.

AtCoder公式 | ABC165 - D.

解答

まだ解いていません

要点解説メモ