AtCoder Problems Training Easy(91~100)

#目次

[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](https://qiita.com/tnodino/private/83c4a61a0361b8995983)
91~100 ← 今ココ

#91. [ABC145 C - Average Length](https://atcoder.jp/contests/abc145/tasks/abc145_c)

**Difficulty:297**

実際に$\ N!\ $通りの全ての経路の長さの合計を求めて$\ N!\ $で割る。

```Python
import itertools
import math
n = int(input())
m = math.factorial(n)
l = [list(map(int,input().split())) for i in range(n)]
x,y = [list(i) for i in zip(*l)]
z = list(range(n))
z = list(itertools.permutations(z))
ans = 0
for i in range(m):
    for j in range(n - 1):
        ans += math.sqrt((x[z[i][j]]-x[z[i][j+1]])**2 + (y[z[i][j]]-y[z[i][j+1]])**2)
print(ans / m)
```

#92. [ABC120 C - Unification](https://atcoder.jp/contests/abc120/tasks/abc120_c)

**Difficulty:304**

どんな順に取り除いても 0 と 1 がそれぞれ 1 個以上あれば消すことができる。
消せないのは 0 のみ残る、 1 のみ残る場合なので、 0 と 1 のうち数が少ない方を$\ N\ $とし、$\ N \times 2\ $で取り除ける個数が分かる。

```Python
s = list(input())
p = s.count('0')
q = s.count('1')
print(2 * min(p,q))
```

#93. [DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 B - Iron Bar Cutting](https://atcoder.jp/contests/ddcc2020-qual/tasks/ddcc2020_qual_b)

**Difficulty:303**

1 ミリ増やすか減らすか、どちらにしても 1 円ずつかかるならなるべく回数を減らしたい。
最初に全体の長さを計算し、$\ 0+A_1+A_2 \dots\ $と$\ sum(A)-A_1-A_2 \dots\ $の差を毎回比較すれば、操作すべき回数が分かる。
その中で差が一番小さい部分を操作すれば、費用が最低限になる。

```Python
n = int(input())
a = list(map(int, input().split()))
ans = 10 ** 16
a_1 = 0
a_2 = sum(a)
for i in range(n - 1):
    a_1 += a[i]
    a_2 -= a[i]
    ans = min(ans, abs(a_1 - a_2))
print(ans)
```

#94. [ABC079 C - Train Ticket](https://atcoder.jp/contests/abc079/tasks/abc079_c)

**Difficulty:300**

組み合わせ自体は 8 通りと少なく、全通り試す。
$\ 0 \le i \le 7\ $の間で$\ i\ $を別の変数に代入し、$\ i \mod 2=0\ $なら + 、違うなら - を$\ A\ $と$\ B\ $の間に入れる。
その後$\ \lfloor i/2 \rfloor\ $で減らし、これを$\ B,C,D\ $間にも行うので合計 3 回行うことになる。
この操作は 2 進数を参考にしている。
$\ 7=0b111\ $ となり、 1 番右の数字が 0 なら + 、 1 なら - とし、1 ビット右にシフトさせている。 

```Python
s = list(input())
a = int(s[0])
b = int(s[1])
c = int(s[2])
d = int(s[3])

def p_mark(j):
    if j % 2 == 0:
        return '+'
    else:
        return '-'

for i in range(2 ** 3):
    j = i
    p = a
    x = p_mark(j)
    if x == '+':
        p += b
    else:
        p -= b
    j = j // 2
    y = p_mark(j)
    if y == '+':
        p += c
    else:
        p -= c
    j = j // 2
    z = p_mark(j)
    if z == '+':
        p += d
    else:
        p -= d
    if p == 7:
        print(str(a) + x + str(b) + y + str(c) + z + str(d) + '=7')
        break
```

#95. [ABC093 C - Same Integers](https://atcoder.jp/contests/abc093/tasks/arc094_a)

**Difficulty:301**

全ての数を揃えたいが、操作はどちらも 2 増やすことになるので、$\ 2,3,3\ $のような差が 1 の場合は$\ 4,3,3\ $、$\ 4,4,4\ $と 2 回操作することで揃えられる。
逆に$\ 2,4,4\ $のような差が 2 の場合は 1 回で揃えられる。
操作を繰り返せば最終的に差が 1 か 2 、つまり奇数か偶数になるので、$\ \max(A,B,C)=S\ $とのそれぞれの差$\ 3S-(A+B+C)=N\ $を求める。
$\ N \mod 2=0\ $なら$\ N/2\ $、$\ N \mod 2=1\ $なら最終的に全て 1 ずつ増えるので$\ (N+3)/2$で操作する回数が求められる。

```Python
a,b,c = map(int,input().split())
z = max(a,b,c)
x = 3 * z - (a + b + c)
if x % 2 != 0:
    x += 3
print(x // 2)
```

#96. [CODE FESTIVAL 2017 qual C B - Similar Arrays](https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_b)

**Difficulty:322**

似ているの条件から$\ A_i\ $には$\ A_{i-1},A_i,A_{i+1}\ $ の 3 通り似ている数字がある。
3 通りを$\ N\ $回選ぶので$\ 3 \times N\ $通りあり、この中から偶数になるものを数える。
偶数を 1 回でもかければ答えは偶数になるため、全て奇数の場合のみ数えないことになる。
そして、$\ A_i\ $が偶数なら 2 個、奇数なら 1 個の奇数が現れるため、$\ A_i\ $が奇数か偶数か判断し、個数を全て掛け算したものを$\ 3 \times N\ $から引く。
例4 なら$\ 3^{10}-(2 \times 2 \times 2 \times 1 \times 2 \times 2 \times 1 \times 2 \times 1 \times 2)\ $ となる。

```Python
n = int(input())
a = list(map(int,input().split()))
ans = 3 ** n
o = 1
for i in range(n):
    if a[i] % 2 == 0:
        o *= 2
    else:
        o *= 1
print(ans - o)
```

#97. [ABC121 C - Energy Drink Collector](https://atcoder.jp/contests/abc121/tasks/abc121_c)

**Difficulty:324**

安いドリンクを買った方がお得なので、$\ A,B\ $のリストを$\ A\ $を基準にソートする。 
その後、$\ M\ $本買えるまで順番に買っていく。

```Python
n,m = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
a,b = [list(i) for i in zip(*l)]
j = 0
ans = 0
while m > 0:
    if b[j] <= m:
        ans += a[j] * b[j]
        m -= b[j]
        j += 1
    else:
        ans += a[j] * m
        m = 0
print(ans)
```

#98. [AGC004 A - Divide a Cuboid](https://atcoder.jp/contests/agc004/tasks/agc004_a)

**Difficulty:278**

偶数が存在する場合、そこを半分に分ければ丁度 2 等分できる。
例2 から、赤青で同じ数になるのが分かる。
全て奇数の場合は、長さ$\ N\ $の列を$\ \lfloor N/2 \rfloor\ $と$\ \lceil N/2 \rceil\ $に分ける。
例3 から分けた時の長さの差は 1 なので、$\ A\ $を分けたなら、$\ B \times C\ $個差になることが分かる。
$\ B \times C\ $が小さい方がいいので、 1 番長い列を分けることになる。

```Python
a = list(map(int,input().split()))
a.sort(reverse = True)
if a[0] % 2 == 0 or a[1] % 2 == 0 or a[2] % 2 == 0:
    print(0)
    exit(0)
block = a[0] * a[1] * a[2]
a[0] = a[0] // 2
x = a[0] * a[1] * a[2]
y = block - x
print(abs(x - y))
```

#99. [ABC046 B - AtCoDeerくんとボール色塗り](https://atcoder.jp/contests/abc046/tasks/abc046_b)

**Difficulty:322**

$\ 1\ $個目のボールを$\ R\ $で塗ると$\ 2\ $個目のボールは$\ R\ $以外の色、$\ K-1\ $の中から選び、$\ i\ $個目のボールも$\ K-1\ $の中から選ぶ。
$\ 1\ $個目の色は$\ K\ $から自由に決めれるので、$\ 1\ $が$\ R\ $だった場合の塗り方は$\ (K-1)^{N-1}\ $ということになる。
$\ 1\ $色目は$\ B\ $でも$\ G\ $でも、$\ K\ $色から選ぶので$\ K \times ((K-1)^{N-1})\ $ということになる。

```Python
n,k = map(int,input().split())
print(k * ((k - 1) ** (n - 1)))
```

#100. [CODE FESTIVAL 2016 qual A B - 仲良しうさぎ](https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_b)

**Difficulty:323**

仲良しなうさぎかどうか調べる。
$\ A_i=j\ $かつ$\ A_j=i\ $のときに仲良しなので、仲良しなペアは固定されると考える。

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