AtCoder Problems Training Easy(81~90)

#目次

[1~10](https://qiita.com/tnodino/private/fe81289a78c79c53e41e)
[11~20](https://qiita.com/tnodino/private/a2f1118ad8276de714e2)
[21~30](https://qiita.com/tnodino/private/bdce8619699fc9cb3110)
[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 ← 今ココ
[91~100](https://qiita.com/tnodino/private/88bacef44c037dc9fc89)

#81. [ABC100 C - *3 or /2](https://atcoder.jp/contests/abc100/tasks/abc100_c)

**Difficulty:264**

例1 の$\ 5\ $を何度も 3 倍して$\ 15,45 \dots\ $としても、どれも$\ 2\ $でちょうど割り切れないことが分かる。
同じように$\ 2\ $を何度も 3 倍して$\ 6,18 \dots\ $としても、どれも$\ 2\ $で割り切れる回数は 1 回だけである。
このことから、各数字が何回$\ 2\ $で割り切れるか調べる。

```Python
n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
    while a[i] % 2 == 0:
        a[i] = a[i] // 2
        ans += 1
print(ans)
```

#82. [AGC019 A - Ice Tea Store](https://atcoder.jp/contests/agc019/tasks/agc019_a)

**Difficulty:380**

頼まれるアイスティーは$\ N\ $リットルの整数であるため、あらかじめ$\ Q \times 4\ $ 、$\ H \times 2\ $ として$\ 1\ $リットルに揃えておく。
あとは$\ N\ $リットルを注文するのに$\ L\ $のみ注文するべきか、$\ D\ $込みで注文するべきか判断する。
例2 のように丁度注文しないといけない点に注意する。

```Python
q,h,s,d = map(int,input().split())
n = int(input())
l = min(q*4,h*2,s)
if n % 2 != 0:
    print(min((n//2)*d+l,n*l))
else:
    print(min((n//2)*d,n*l))
```

#83. [ABC087 C - Candies](https://atcoder.jp/contests/abc087/tasks/arc090_a)

**Difficulty:268**

全部で$\ N\ $通りの飴の取り方がある。
上側を$\ A\ $、下側を$\ B\ $とし、$\ A_i\ $で$\ B\ $に降りた場合、$\ A_1 \dots A_i\ $の合計と、$\ B_i \dots B_N\ $の合計が入手できる飴の数になる。

```Python 
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 0
for i in range(n):
    c = sum(a[0:i+1]) + sum(b[i:n])
    ans = max(ans,c)
print(ans)
```

#84. [ABC135 C - City Savers](https://atcoder.jp/contests/abc135/tasks/abc135_c)

**Difficulty:287**

$\ A_1\ $の街にいるモンスターは$\ B_1\ $の勇者しか倒せないことから、前から順に倒せるか判断する。
最初にモンスターの合計$\ S\ $を求めておき、勇者$\ B_i\ $が順番に$\ A_i,A_{i+1}\ $のモンスターを倒していく。
倒しきれずに残ったモンスターの合計を$\ S\ $から引けば倒したモンスターの数になる。

```Python
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = sum(a)
for i in range(n):
    if b[i] > a[i]:
        b[i] -= a[i]
        a[i] = 0
        if b[i] >= a[i+1]:
            a[i+1] = 0
        else:
            a[i+1] -= b[i]
    else:
        a[i] -= b[i]
print(ans - sum(a))
```

#85. [ABC100 B - Ringo's Favorite Numbers](https://atcoder.jp/contests/abc100/tasks/abc100_b)

**Difficulty:275**

$\ 100^D \times N\ $と計算すれば、プレゼントすべき整数が分かる。
しかし、例えば$\ 0,100\ $の場合、上通りに計算すると$\ 100\ $となるが、 100 で 1 回割りきれてしまうので WA になる。
なので$\ N=100\ $の時だけさらに$ 100^d\ $を足さないといけないことに注意する。

```Python
d,n = map(int,input().split())
if n == 100:
    print(100 ** d * n + 100 ** d)
else:
    print(100 ** d * n)
```

#86. [ABC106 C - To Infinity](https://atcoder.jp/contests/abc106/tasks/abc106_c)

**Difficulty:379**

$\ K\ $の数字が分かるまで文字列$\ S\ $を操作すると、$\ 1 \le K \le 10^{18}\ $の制約で TEL になる。
文字列の操作を見ると、最終的に$\ 2\ $の長さは$\ 2^{5 \times 10^{11}}\ $になり、$\ 10^{18}\ $よりも大きい。
一方で$\ 1\ $は何日経っても長さは$\ 1\ $なので、$\ S_K\ $までに$\ 1\ $以外の数字が存在する場合はそれが答えであり、そうでなければ$\ 1\ $が答えになる。

```Python
s = list(input())
k = int(input())
for i in range(min(k,len(s))):
    if s[i] != '1':
        print(s[i])
        exit(0)
print(1)
```

#87. [ABC103 C - Modulo Summation](https://atcoder.jp/contests/abc103/tasks/abc103_c)

**Difficulty:279**

$\ (a_1 \times a_2 \times \dots a_N)/N\ $を$\ m\ $としたいが、$\ m \mod a_i\ $が$\ 0\ $になってしまう。
なので$\ m-1 \mod a_i\ $とし、 例3 なら$\ 155848-1\ $でそれぞれの余りが$\ 6,45,10,19,10=90\ $となり、最大値になることが分かる。
しかし、$\ 2 \le a_i \le 10^5\ $の数字を全てかけるのは避けたい。
先ほどの余りを見ると、全て$\ a_i-1\ $になっているため、答えは$\ (a_1+a_2+ \dots a_N)-N\ $になる。

```Python
n = int(input())
a = list(map(int,input().split()))
print(sum(a) - n)
```

#88. [ABC091 B - Two Colors Card Game](https://atcoder.jp/contests/abc091/tasks/abc091_b)

**Difficulty:282**

まず、このカードに含まれる文字列が何種類あるかを調べる。
$\ S\ $と$\ T\ $を結合し、重複を消せば文字列が何種類あるか分かる、重複を消したリストを$\ L\ $とする。
先ほど調べた$\ L\ $を順番に発言して、それぞれいくらもらえるか調べる。
例3 のように、最低は 0 円になることに注意する。

```Python
n = int(input())
s = list(input() for i in range(n))
m = int(input())
t = list(input() for i in range(m))
a = s + t
a = list(set(a))
ans = 0
for i in range(len(a)):
    plus = s.count(a[i])
    minus = t.count(a[i])
    ans = max(ans,plus - minus)
print(ans)
```

#89. [ARC088 C - Multiple Gift](https://atcoder.jp/contests/arc088/tasks/arc088_a)

**Difficulty:288**

プレゼントする整数は$\ X^1,X^2,X^3 \dots\ $となるので、$\ Y\ $以下を満たす$\ X^i\ $の$\ i\ $が数列の長さになる。

```Python
x,y = map(int,input().split())
i = 1
while x *(2 ** i) <= y:
    i += 1
print(i)
```

#90. [ABC055 B - Training Camp](https://atcoder.jp/contests/abc055/tasks/abc055_b)

**Difficulty:291**

$\ N\ $回目のトレーニングを終えるとパワーは$\ N!\ $になるが、 例3 の入力例$\ 10^5!\ $を求めてから$\ 10^9+7\ $で割ったあまりを求めると、 TLE を起こす。
途中で$\ 10^9+7\ $を超える場合、超えた分を$\ M\ $とすると次の計算は$\ (10^9+7) \times i+M \times i\ $となるため、答えとして含まれない$\ 10^9+7\ $を先に引いておけば、$\ M \times i\ $で TLE にならずに計算できる。

```Python
n = int(input())
ans = 1
for i in range(1,n+1):
    ans = ans * i
    ans %= (10 ** 9 + 7)
print(ans)
```