AtCoder ARC118 個人的メモ

所感

a1完

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すればおｋ。

$\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個あるので、解が求まりそう。

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)