AtCoder ABC 165

ABCD4完で水色パフォでした。以下振り返り。

A - We Love Golf

問題のリンク

概要

  • 要は A以上、 B以下の数に Kの倍数が含まれるか否か。

制約

  •  1 ≤ A ≤ B ≤ 1000
  •  1 ≤ K ≤ 1000

考察

面倒なので愚直に全探索

コード

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%の利子がつく時、 X以上になるのは何年後か。

制約

  •  101 ≤ X ≤ 10 ^{18}

考察

最初、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

問題のリンク

概要

  •  N以下の非負整数 xに対する floor(Ax/B) -A × floor(x/B) の最大値

制約

  •  1 ≤ A ≤ 10 ^{6}
  •  1 ≤ B ≤ 10 ^{12}
  •  1 ≤ N ≤ 10 ^{12}
  • 入力は全て整数

考察

  •  floor(x/B) が0となる範囲内で、最大の xを求める。要は x=B-1
  • ただ xが指定の範囲を取れない場合もある。よってその時の条件を忘れないことが肝。( x=N)

コード

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割は通ったけど、残りがダメでした。

概要

  • 参加者 N人でジャンケン大会を行う。参加者はそれぞれ 1 ~  Nの番号が割り振られている。
  • 1対1でジャンケンを行う闘技場が M個用意されている。
  • 闘技場には N以下の整数が2個割り当てられている。
  • 参加者は自分の数字が書かれた闘技場でジャンケンを行う(第1ラウンド)
  • その後、参加者に割り振られた整数が1増加する。 N番目の人は1になる。
  • 参加者は自分の数字が書かれた闘技場でジャンケンを行う(第2ラウンド)
  • 以降、 Nラウンドまで繰り返した時に二回以上同じ参加者と対戦するような参加者が存在しないようにしたい。この時の闘技場の整数はどの様に割り当てるか。

制約

  •  1 ≤M
  •  M × 2 + 1 ≤ N ≤ 100000

考察

 公式の解説動画が神すぎるくらい分かりやすかったです。最後におまけで出てくるリーグ戦のアルゴリズムも面白かった!

www.youtube.com