目次
1~10
11~20
21~30 ← 今ココ
31~40
41~50
51~60
61~70
71~80
81~90
91~100
21.ABC149 C - Next Prime
Difficulty:135
$\ X\ $に対して$\ 2 \le i \le X-1\ $が$\ X \mod i \neq 0\ $かどうかを調べる。
もしすべての$\ i\ $で$\ X \mod i \neq 0\ $を満たすなら$\ X\ $が答えの整数であり、違うなら$\ X\ $を 1 増やして条件を満たすまで上の条件で調べ続ける。
制約が$\ 2 \le X \le 10^5\ $であり、 例3 の出力から$\ X \le i \le 100003\ $の範囲で素数かどうか調べたらいいことが分かる。
x = int(input())
for i in range(x,100004):
flg = True
for j in range(2,i):
if i % j == 0:
flg = False
break
if flg:
print(i)
break
22.AGC027 A - Candy Distribution Again
Difficulty:122
子供が欲しがっているキャンディの合計を$\ S\ $とする。
$\ S=x\ $なら、子供全員に丁度渡せるため$\ N\ $人全員が満足する。
$\ S
$\ S>x\ $なら、$\ a_1 \dots a_N\ $の各子供が満足する個数を$\ x\ $個がなくなるまで渡し続ける。
喜ぶ子供の人数を最大化するため、$\ a\ $をソートしておき、喜ぶ個数が少ない順に渡していく。
n,x = map(int,input().split())
a = list(map(int,input().split()))
if sum(a) == x:
print(n)
elif sum(a) < x:
print(n - 1)
else:
ans = 0
a.sort()
for i in range(n):
if a[i] > x:
break
else:
x -= a[i]
ans += 1
print(ans)
23.ABC092 B - Chocolate
Difficulty:91
残ったチョコレート$\ X\ $に$\ N\ $人が食べたチョコレートの数を足して復元する。
$\ i\ $ 人目がチョコレートを食べた日は、問題文にあるように $\ 1,A_i+1,2A_i+1\ $なので、まとめると$\ \lceil D/A_i \rceil \ $ ということが分かる。
1 日目に全員が食べることと、$\ D\ $日目も食べることに注意する。
from math import ceil
n = int(input())
d,x = map(int,input().split())
a = list(int(input()) for i in range(n))
for i in range(n):
x += ceil(d / a[i])
print(x)
24.日立製作所 社会システム事業部 プログラミングコンテスト2020 B - Nice Shopping
Difficulty:94
まず、$\ \min(A)\ $円の冷蔵庫と$\ \min(B)\ $円の電子レンジを買った時の金額を求める。
その後、クーポン通りに購入した時に、上より安くなるか調べる。
例2 のように、クーポンは 1 つしか使えず、同じ組み合わせでもクーポンによって値段が違うことに注意する。
a,b,m = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
l = [list(map(int,input().split())) for i in range(m)]
x,y,c = [list(i) for i in zip(*l)]
ans = min(a) + min(b)
for i in range(m):
ans = min(ans,a[x[i]-1] + b[y[i]-1] - c[i])
print(ans)
25.ABC150 C - Count Order
Difficulty:338
順列$\ 1 \dots N\ $の重複なしの並びを全て格納したリストを用意する。
その後、$\ P\ $と$\ Q\ $の位置を調べ、その差を出力する。
import itertools
n = int(input())
a = list(range(1,n+1))
a = list(itertools.permutations(a,n))
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))
print(abs(a.index(p) - a.index(q)))
26.ABC153 D - Caracal vs Monster
Difficulty:120
最初のモンスターの体力を半分にすると、モンスターの数が 2 倍に増える。
増えたモンスターの体力を全て半分にすると、モンスターの数がさらに 2 倍に増える。
このことから体力を半分にするたび、攻撃回数は$\ 2^0,2^1 \dots \ $と増える。
これを$\ H\ $が 0 になるまで繰り返す。
h = int(input())
ans = 0
i = 0
while h > 0:
h = h // 2
ans += 2 ** i
i += 1
print(ans)
27.ABC158 B - Count Balls
Difficulty:106
$\ A+B \le N\ $の場合、青いボールは少なくとも$\ (\lfloor N/(A+B) \rfloor) \times A\ $個は出現する。
さらに$\ N \mod (A+B)\ $ 個のボールの中で、青いボールが何個出現するか数える。
n,a,b = map(int,input().split())
c = a + b
z = n // c
if n % c != 0:
m = n % c
if a <= m:
print(z * a + a)
else:
print(z * a + m)
else:
print(z * a)
28.ABC081 B - Shift only
Difficulty:98
実際に$\ N\ $個の整数を 2 で割り切れるか調べる。
n = int(input())
a = list(map(int,input().split()))
ans = 0
flg = True
while flg:
for i in range(n):
if a[i] % 2 == 0:
a[i] = a[i] // 2
else:
flg = False
break
if flg:
ans += 1
print(ans)
29.ABC114 B - 754
Difficulty:111
文字列$\ S\ $から、長さ 3 の部分文字列を取り出す。
それを数値化し、 753 との差の絶対値を調べる。
s = input()
ans = 999
for i in range(len(s)-2):
n = int(s[i:i+3])
ans = min(ans,abs(753 - n))
print(ans)
30.ABC108 B - Ruined Square
Difficulty:140
実際に書いてみると法則を探しやすく、画像は 例2 を参考にしている。
まず$\ x_1,x_2\ $の差と、$\ y_1,y_2\ $の差を求める。
それぞれ、$\ c-a,d-b\ $になり、これを$\ n,m\ $として考える。
次に$\ x_3,y_3,x_4,y_4\ $を求める。
$\ x_3,y_3\ $は$\ x_2-m\ $、$\ y_2+n\ $で求まる。
$\ x_4,y_4\ $は$\ x_1-m\ $、$\ y_1+n\ $で求まる。
a,b,c,d = map(int,input().split())
x = c - a
y = d - b
print(c - y,d + x,a - y,b + x)