競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - We Love Golf
KがA以上B以下の範囲に含まれているか答える問題です。
$1\leq A \leq B \leq 1000$, $1\leq K \leq 1000$という制約から、単純に$A$から$B$までの範囲で条件を満たす値があるか探索すれば問題ないです。
N = int(input())
A, B = map(int, input().split())
for i in range(A, B+1):
if i % N == 0:
print('OK')
break
else:
print('NG')
B - 1%
預けた100円に1%の年利が付くとき、与えられた金額X円を超えるのは何年後か答える問題です。
小数点以下となる金額は切り捨てられます。指定された金額を超えるまでwhileを回した回数を答えました。
X = int(input())
n = 100
count = 0
while n < X:
count += 1
n = int(n * 1.01)
print(count)
C - Many Requirements
入力$a, b, c, d$に対して$A_b - A_a = c$となる時$d$点を入手します。数列$\boldsymbol{A}$を自由に作成できるとき、得点の合計の最大値がいくつになるか答える問題です。
ややっこしい問題...に見えるんですが、数列の長さ$N$, 最大値$M$は$1\leq N \leq 10, 1\leq M \leq 10$, 与えられる$a, b, c, d$の個数$Q$も$1\leq Q \leq 50$と指定されています。これなら総当たりでごり押せると思いました。
総当たりにはitertools.combinations_with_replacement()を使用しました。数列$A$にはソートされた値なのは決められていますが値の重複はありうることに注意。
import itertools
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]
Max = 0
for C in itertools.combinations_with_replacement(range(1, M + 1), N):
score = sum([d for a, b, c, d in abcd if C[b-1] - C[a-1] == c])
Max = max(Max, score)
print(Max)
追記
これ本当にゴリ押せる数字か？$O(M^N Q)$じゃね？って不安になって計算してみました。
import itertools
print(len(list(itertools.combinations_with_replacement(range(1, 11), 10))))
# 92378
いけるらしい。解説を見たところ、自力でこの全探索は厳しかったですね。Python万歳。ライブラリ万歳。
D - Floor Function
$$ floor (Ax/B)-A\times floor (x/B) $$
が最大値になる$x$を求める問題です。
数学的な証明は置いといて、$floor (x/B)=0$となる$x$の最大値を求めればいいんだろうなあと思いました。その条件を満たすのは$N$以下で最大の$B-1$、つまり$B-1$か$N$の小さいほうです。
というわけで書いたのは以下です。
A, B, N = map(int, input().split())
x = min(B-1, N)
print(A*x // B - A * (x//B))
数学的な説明
数学的な説明はわからなかったので、解説を読みます。
$$ f(x) = floor (Ax/B)-A\times floor (x/B)$$
と置きます。この数式において$x$の値を$B$増やした時、右辺の第一項は必ず$A$だけ増えます。第二項は必ず$A$だけ減ります。これが打ち消しあい、合計は変化しません。つまり以下の式が成立します。
$$f(x) = f(x+B)$$
なので$B\leq x$の範囲を考える必要はありません。$0\leq x < B$, $0\leq x \leq N$の範囲で最大値を求めましょう。
この範囲では本来負となる第二項の値が必ず0なので、単調増加である第一項の値を範囲内で最大にすればよいです。つまり$x$を範囲内で最大にします。
第二項は使ってないので以下の書き方でもいいですね。
A, B, N = map(int, input().split())
print(A * min(B-1, N) // B)
E - Rotation Matching
$N$人の参加者が1vs1のじゃんけんを同時に$M$試合ずつ、$N$回行う時に対戦相手が重複しない組み合わせの取り方を考える問題です。
問題文が極めてややこしいですね。何を聞かれているんでしょうか？
この大会に$N=9$人が参加したとしましょう。試合は9セット行われます。ここから$M = 3$として、3通りのペアを組んでみましょう。
適当に1, 2のペアを選んでみます。
この状態で9回ローテーションを回しても対戦相手の重複は発生しません。
次に、3, 5のペアを取ってみましょう。
これでも重複は発生しません。
次は6, 7のペアを取ってみます。
これで重複が発生します。1, 2の一個ずらしのペアと6, 7の一個ずらしのペアが途中で同じものを取ってしまいます。
これを直すには？1個、2個とずらしてきているので今度は3個ずらしてみましょう。
今度は重複が発生しません。このようなペアを作っていく問題です。
つまり、この問題は以下のように言い換えられます。
「$B_i - A_i = 1, 2, 3, ..., M$となる($A_i, B_i$)のペアを$M$個、値の重複なく出力せよ」
これを解くのには、まともな探索を行っていられません。(TLE出まくりました。)最初から形を決め打ちして配置します。
というわけで以下のように実装しました。
N, M = map(int, input().split())
halfPos = -(-N//2)
qPos = halfPos // 2
q3Pos = qPos + halfPos
for m in range(1, M+1):
if m % 2:
print(qPos-m//2, qPos+m//2+1)
else:
print(q3Pos-m//2, q3Pos+m//2)
今回の記事はここまでとします。ABCDEと本番で解けたのは初めてです。