AtCoder Beginner Contest 165の感想

AtCoder

2020.05.03

ABC165に参加した。

AtCoder Beginner Contest 165 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – We Love Golf

総当りする。

k = int(input())
a, b = map(int, input().split())

flag = False
for i in range(a, b + 1):
    if i % k == 0:
        flag = True
        break

print('OK') if flag else print('NG')

B – 1%

小数点切り捨てなので、毎回整数型にしないと誤差が生じてしまうことに注意。

x = int(input())

now = 100
ans = 0
while now < x:
    ans += 1
    now = int(now * 1.01)

print(ans)

C – Many Requirements

本番中にACできなかった。

Aが1≤A1≤A2≤⋯≤AN≤M という単調増加な数列であることを見落としており、全列挙していたことがTLEになってACできなかった原因。

単調増加な数列を再帰的に求め、コンテスト終了後に自力ACすることができた。

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

A = []


def dfs(num):
    if len(num) == n:
        A.append(num)
    else:
        now = num[-1]
        for i in range(now, m + 1):
            dfs(num + [i])


for i in range(1, 10):
    dfs([i])

ans = 0
for now in A:
    point = 0
    for a, b, c, d in abcd:
        if now[b-1] - now[a-1] == c:
            point += d

    ans = max(ans, point)

print(ans)

後で知ったのだが、再帰を用いなくともitertoolsで簡単に求めることもできる。

itertools.combinations_with_replacement(range(1, m+1), n)

D – Floor Function

整数部分と小数部分に分けて式変形をしていく数学問題。

x / b の小数部分をmとすると、答えは a * m となり、a が定数のため m を最大化する問題と解釈できる。

n >= b のとき、x = b – 1 で x / b が最大値を取る。

n < b のとき、x = n で x / b が最大となる。

import math

a, b, n = map(int, input().split())

if n >= b:
    ans = math.floor(a * (b - 1) / b)
else:
    ans = math.floor(a * n / b)

print(ans)

茶色の真ん中レート600が見えてきた。