AtCoder Problems Training Easy(21~30)

#目次

[1~10](https://qiita.com/tnodino/private/fe81289a78c79c53e41e)
[11~20](https://qiita.com/tnodino/private/a2f1118ad8276de714e2)
21~30 ← 今ココ
[31~40](https://qiita.com/tnodino/private/426ea11e1509bbe282d8)
[41~50](https://qiita.com/tnodino/private/3e92afbd7fd8396a8118)
[51~60](https://qiita.com/tnodino/private/62637218c5884b2af10d)
[61~70](https://qiita.com/tnodino/private/0997709fa992e538ed36)
[71~80](https://qiita.com/tnodino/private/1249d60df34c0fda8e6e)
[81~90](https://qiita.com/tnodino/private/83c4a61a0361b8995983)
[91~100](https://qiita.com/tnodino/private/88bacef44c037dc9fc89)

#21.[ABC149 C - Next Prime](https://atcoder.jp/contests/abc149/tasks/abc149_c)

**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\ $の範囲で素数かどうか調べたらいいことが分かる。

```Python
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](https://atcoder.jp/contests/agc027/tasks/agc027_a)

**Difficulty:122**

子供が欲しがっているキャンディの合計を$\ S\ $とする。
$\ S=x\ $なら、子供全員に丁度渡せるため$\ N\ $人全員が満足する。 
$\ S<x\ $なら、子供全員に丁度渡した後、余ったキャンディを誰かに渡さないといけないため、$\ N-1\ $人が満足する。
$\ S>x\ $なら、$\ a_1 \dots a_N\ $の各子供が満足する個数を$\ x\ $個がなくなるまで渡し続ける。
喜ぶ子供の人数を最大化するため、$\ a\ $をソートしておき、喜ぶ個数が少ない順に渡していく。

```Python
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](https://atcoder.jp/contests/abc092/tasks/abc092_b)

**Difficulty:91**

残ったチョコレート$\ X\ $に$\ N\ $人が食べたチョコレートの数を足して復元する。
$\ i\ $ 人目がチョコレートを食べた日は、問題文にあるように $\ 1,A_i+1,2A_i+1\ $なので、まとめると$\ \lceil D/A_i \rceil \ $ ということが分かる。
1 日目に全員が食べることと、$\ D\ $日目も食べることに注意する。

```Python
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](https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_b)

**Difficulty:94**

まず、$\ \min(A)\ $円の冷蔵庫と$\ \min(B)\ $円の電子レンジを買った時の金額を求める。
その後、クーポン通りに購入した時に、上より安くなるか調べる。
例2 のように、クーポンは 1 つしか使えず、同じ組み合わせでもクーポンによって値段が違うことに注意する。

```Python
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](https://atcoder.jp/contests/abc150/tasks/abc150_c)

**Difficulty:338**

順列$\ 1 \dots N\ $の重複なしの並びを全て格納したリストを用意する。
その後、$\ P\ $と$\ Q\ $の位置を調べ、その差を出力する。

```Python
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](https://atcoder.jp/contests/abc153/tasks/abc153_d)

**Difficulty:120**

最初のモンスターの体力を半分にすると、モンスターの数が 2 倍に増える。
増えたモンスターの体力を全て半分にすると、モンスターの数がさらに 2 倍に増える。
このことから体力を半分にするたび、攻撃回数は$\ 2^0,2^1 \dots \ $と増える。
これを$\ H\ $が 0 になるまで繰り返す。

```python
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](https://atcoder.jp/contests/abc158/tasks/abc158_b)

**Difficulty:106**

$\ A+B \le N\ $の場合、青いボールは少なくとも$\ (\lfloor N/(A+B) \rfloor) \times A\ $個は出現する。
さらに$\ N \mod (A+B)\ $ 個のボールの中で、青いボールが何個出現するか数える。

```Python
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](https://atcoder.jp/contests/abc081/tasks/abc081_b)

**Difficulty:98**

実際に$\ N\ $個の整数を 2 で割り切れるか調べる。

```Python
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](https://atcoder.jp/contests/abc114/tasks/abc114_b)

**Difficulty:111**

文字列$\ S\ $から、長さ 3 の部分文字列を取り出す。
それを数値化し、 753 との差の絶対値を調べる。

```Python
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](https://atcoder.jp/contests/abc108/tasks/abc108_b)

**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\ $で求まる。
![スクリーンショット (31).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/642825/847700ba-1abb-cdab-a4d2-d33ba661b086.png)

```Python
a,b,c,d = map(int,input().split())
x = c - a
y = d - b
print(c - y,d + x,a - y,b + x)
```