🔖

AtCoder ARC118 個人的メモ

2021/05/10に公開約1,900字

所感

a1完
arc118_score

A - Tax Included Price

\frac{100+t}{100}A=A+\frac{At}{100}より、Atが100の倍数を通過するときに現れない金額が存在するとわかる。
よって、N番目の金額は\frac{At}{100N}が1になるときのAから1を引いた数となる。

t, N = map(int, input().split())

A = -(-100 * N // t)  # 切り上げの割り算
ans = (100 + t) * A // 100 - 1
print(ans)

B - Village of M People

考察は合ってたのに実装でバグらせてた。

B_i=\lfloor \frac{A_iM}{N}\rfloorとする。
B_iを非負整数ではなく小数でも良いとすると、\sum^K_{i=1}B_i=Mを満たしつつmax_i|\frac{B_i}{M}-\frac{A_i}{N}|を最小にするにはB_i=\frac{A_iM}{N}とすれば良い。
これをいい感じに小数点以下を切り上げたり切り捨てたりすれば良さそう。
つまり、最初に全てのB_iを切り捨てで計算しておいて、\frac{B_i}{M}-\frac{A_i}{N}が小さい方からM-\sum^K_{i=1}B_i個のB_iを+1すればおk。

\frac{B_i}{M}-\frac{A_i}{N}の計算で計算誤差が出そうなので、Decimal使った。
scoreの管理を辞書で実装したら、tmp_scoreが重複した場合を考慮していなかったせいかバグった。

from decimal import Decimal

K, N, M = map(int, input().split())
A = list(map(int, input().split()))

ans = []
scores_and_i = []
for i in range(K):
    ans.append(A[i] * M // N)
    tmp_score = Decimal(ans[-1]) / Decimal(M) - Decimal(A[i]) / Decimal(N)
    scores_and_i.append((tmp_score, i))

scores_and_i.sort()

diff = M - sum(ans)
for _, i in scores_and_i[:diff]:
    ans[i] += 1

print(*ans)

C - Coprime Set

N=3の時の解を3つの数2,3,5から2つを選んで掛け算した数(6,15,10)とする。
この数列は問題文の条件を全て満たしている。
この数列に条件を満たす数を加えていきたい。
条件を満たす数は3つの数の内の2つ以上の数を約数に持つ数、つまり(6,15,10)のいずれかを約数に持つ数。
そのような数は1以上10^4以下では2665個あるので、解が求まりそう。

arc118c_fig

N = int(input())

a, b, c = 2, 3, 5
base_nums = [a * b, b * c, c * a]

now_num = max(base_nums) + 1
ans = list(base_nums)
while len(ans) < N:
    if any(now_num % x == 0 for x in base_nums):
        ans.append(now_num)
    now_num += 1

print(*ans)

Discussion

ログインするとコメントできます