AtCoder ABC 165
ABCD4完で水色パフォでした。以下振り返り。
A - We Love Golf
概要
- 要は以上、以下の数にの倍数が含まれるか否か。
制約
考察
面倒なので愚直に全探索
コード
K = int(input()) A, B = map(int, input().split()) for i in range(A, B+1): if i%K==0: print('OK') exit() print('NG')
B - 1%
概要
- 初年度に100円を預ける。年率1%の利子がつく時、以上になるのは何年後か。
制約
考察
最初、1年毎に端数切り捨てという条件を忘れて実装してしまってたけど、提出前に確認して気づけた。(本番慣れしてきた証拠と思いたい。)
コード
X = int(input()) cnt = 0 m = 100 while True: m *= 1.01 m = int(m) cnt += 1 if m>=X: break print(cnt)
C - Many Requirements
概要
文字にするとややこしいので省略。
制約
ながいので省略。ただ制約的に全探索でも間に合う感じ。
考察
- 問題文を始め読んだ際、日本語の意味が理解できず5分以上は考え込んでしまった。
- 理解してしまえば、そのまま全探索で行ける問題。
- ただ初回の提出の際に
combinations_with_replacement(range(1, M+1), N)
をcombinations_with_replacement(range( M+1), N)
と書いてしまい、0を含めた数列で探索してしまった。(1WA) - C問題はBまでと比べると実装が少し重くなり始めるけど、こういう系はbit全探索系の問題を何度か解く事で慣れてきた気がする。
コード
from itertools import combinations_with_replacement N, M, Q = map(int, input().split()) q = [] for _ in range(Q): q.append(list(map(int, input().split()))) ans = 0 for v in combinations_with_replacement(range(1, M+1), N): score = 0 for i in range(Q): joken = q[i] if v[joken[1]-1] - v[joken[0]-1] == joken[2]: score += joken[3] ans = max(ans, score) #print(v, ': ', score) print(ans)
D - Floor Function
概要
- 以下の非負整数に対するの最大値
制約
- 入力は全て整数
考察
- が0となる範囲内で、最大のを求める。要は
- ただが指定の範囲を取れない場合もある。よってその時の条件を忘れないことが肝。()
コード
from math import floor A, B, N = map(int, input().split()) if N>=B-1: x = B-1 ans = floor((A*x)/B) - A*floor(x/B) else: x = N ans = floor((A*x)/B) - A*floor(x/B) print(ans)
E - Rotation Matching
今回、できなかった問題。テストケース8割は通ったけど、残りがダメでした。
概要
- 参加者人でジャンケン大会を行う。参加者はそれぞれ ~ の番号が割り振られている。
- 1対1でジャンケンを行う闘技場が個用意されている。
- 闘技場には以下の整数が2個割り当てられている。
- 参加者は自分の数字が書かれた闘技場でジャンケンを行う(第1ラウンド)
- その後、参加者に割り振られた整数が1増加する。番目の人は1になる。
- 参加者は自分の数字が書かれた闘技場でジャンケンを行う(第2ラウンド)
- 以降、ラウンドまで繰り返した時に二回以上同じ参加者と対戦するような参加者が存在しないようにしたい。この時の闘技場の整数はどの様に割り当てるか。
制約
考察
公式の解説動画が神すぎるくらい分かりやすかったです。最後におまけで出てくるリーグ戦のアルゴリズムも面白かった!