AtCoder Problems Training Easy(11~20)

#目次

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

#11. [ABC068 B - Break Number](https://atcoder.jp/contests/abc068/tasks/abc068_b)

**Difficulty:77**

$\ 2\ $で割れる回数を最大にしようとする場合、$\ 2 \times 2 \times \dots \ $ となるので、答えは全て$\ 2^i\ $になる。
あとは$\ N\ $以下の条件を満たす$\ 2^i\ $を探す。

```Python
n = int(input())
ans = 1
while True:
    ans *= 2
    if ans > n:
        ans = ans // 2
        break
print(ans)
```

#12. [ABC160 C - Traveling Salesman around Lake](https://atcoder.jp/contests/abc160/tasks/abc160_c)

**Difficulty:126**

例2 のように反時計回りに訪ねた方が最短になる場合を考える。
家の位置を$\ 0,5,15\ $ではなく、$\ 20,25,15\ $と考えれば求めやすくなる。
このことから$\ A_1 + K,A_2 + K \dots A_{N-1} + K\ $を$\ A\ $に追加しておく。 
その後、家の移動にかかる距離を$\ A_{i+n-1}-A_i\ $で求める。
例2 では、最終的にリスト$\ A\ $は$\ 0,5,15,20,25\ $になっている。

```Python
k,n = map(int,input().split())
a = list(map(int,input().split()))
ans = 10 ** 8
for i in range(n-1):
    a.append(a[i]+k)
for i in range(n):
    ans = min(ans,a[i+n-1] - a[i])
print(ans)
```

#13. [AGC014 A - Cookie Exchanges](https://atcoder.jp/contests/agc014/tasks/agc014_a)

**Difficulty:178**

例2 のように、もし全員の持っているクッキーの数が同じだった場合、偶数枚なら全員が$\ (A+B)/2=C\ $、つまり$\ (14+14)/2=14\ $となり、何度交換しても枚数が変わらないので$\ -1\ $になる。
そうでないなら、誰かの枚数が奇数になるまでに何回交換できるか実際に交換を行い続ける。
ただし、元から誰かの枚数が奇数ならそもそも交換できないので$\ 0\ $になる。

```Python
a,b,c = map(int,input().split())
if a == b == c:
    if a % 2 == 0:
        print(-1)
        exit(0)
    else:
        print(0)
        exit(0)
ans = 0
while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
    al = b // 2 + c // 2
    bl = a // 2 + c // 2
    cl = a // 2 + b // 2
    a = al
    b = bl
    c = cl
    ans += 1
print(ans)
```

#14. [ABC161 C - Replacing Integer](https://atcoder.jp/contests/abc161/tasks/abc161_c)

**Difficulty:123**

$\ |N-K|\ $を繰り返していると、$\ 0 \le N \le 10^{18}、1 \le K \le 10^{18}\ $の制約で TLE になるので、法則を探す必要がある。
$\ N=7,K=5\ $ の場合、
$\ |7-5|=2,|2-5|=3,|3-5|=2\ $となるため、$\ N \mod K\ $が答えになる。
$\ N=7,K=4\ $の場合、
$\ |7-4|=3,|3-4|=1,|1-4|=3\ $となるため、$\ K-(N \mod K)\ $になる。
この 2 つのうち、答えが小さい方を出力する。

```Python
n,k = map(int,input().split())
print(min(n % k,k - n % k))
```

#15. [ABC132 C - Divide the Problems](https://atcoder.jp/contests/abc132/tasks/abc132_c)

**Difficulty:90**

問題数を同じになるように分類するには$\ N/2\ $ずつに分ける必要がある。
難易度もバラバラなので$\ d\ $をソートし、$\ d_1 \dots d_{N/2}\ $が ABC 、$\ d_{N/2+1} ... d_N\ $を ARC として考える。
上の条件を守りつつ難易度$\ K\ $を決めようとすると、考えられる$\ K\ $の範囲は$\ \max($ ABC $)<K \le \min($ ARC $)\ $になる。

```Python
n = int(input())
d = list(map(int,input().split()))
d.sort()
a = n // 2
b = a - 1
print(d[a] - d[b])
```

#16. [ABC142 C - Go to School](https://atcoder.jp/contests/abc142/tasks/abc142_c)

**Difficulty:86**

例1 から$\ A\ $が$\ 2,3,1\ $なら$\ 1\ $の生徒は$\ 2\ $番目、$\ 2\ $の生徒は$\ 3\ $番目、$\ 3\ $の生徒は$\ 1\ $番目となる。
別のリスト$\ L\ $を用意して、$\ L_{A_i}\ $に$\ i\ $を代入すれば、最終的に生徒が登校した順に$\ L\ $に格納されている。

```Python
n = int(input())
a = list(map(int,input().split()))
ans = ['0'] * n
for i in range(n):
    ans[a[i]-1] = str(i+1)
print(' '.join(ans))
```

#17. [ABC138 C - Alchemist](https://atcoder.jp/contests/abc138/tasks/abc138_c)

**Difficulty:86**

例2 から具材を昇順に入れれば最大になると予想できる。
試しに$\ 3,1,4,1,5,9,2\ $の食材が与えられたとき、昇順に順番に入れると$\ 6.53125\ $になり、これが最大値である。
一方、降順に順番に入れると$\ 1.53125\ $ととても低くなる。

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

#18. [ABC122 B - ATCoder](https://atcoder.jp/contests/abc122/tasks/abc122_b)

**Difficulty:85**

前から$\ S_i\ $が ACGT か調べていく。
ACGT ではない場合、そこまでの ACGT 文字列の長さを今までの長さの最大値と比較しておく。

```Python
s = input()
acgt = ['A','C','G','T']
ans = 0
p = 0
for i in range(len(s)):
    if s[i] in acgt:
        p += 1
    else:
        ans = max(ans,p)
        p = 0
print(max(ans,p))
```

#19. [ABC094 B - Toll Gates](https://atcoder.jp/contests/abc094/tasks/abc094_b)

**Difficulty:87**

ゴール$\ 0\ $か$\ N\ $に移動するためのコストを最小にするには、通過する料金所の数が少なければよい。
$\ 0 \le X\ $の間と、$\ X \le N\ $の間にある料金所の数をそれぞれ調べ、数が少ない方に移動し続ければコストが最小になる。

```Python
n,m,x = map(int,input().split())
a = list(map(int,input().split()))
le = m
for i in range(m):
    if a[i] > x:
        le = i
        break
ri = m - le
print(min(le,ri))
```

#20. [ABC116 B - Collatz Problem](https://atcoder.jp/contests/abc116/tasks/abc116_b)

**Difficulty:92**

$\ s\ $を問題文通りに計算し、その都度計算した$\ s\ $をリストに追加しておく。
その後、そのリストに同じ数字が存在するか確認し、存在する場合はそのリストの長さが答えになる。
これは 例1 で$\ 4\ $が 5 回目に、 例2 で$\ 4\ $が 18 回目に今までに出た数字がもう一度出たタイミングであり、答えにもなっているからである。

```Python
s = int(input())
t = []
t.append(s)
while True:
    if s % 2 == 0:
        s = s // 2
    else:
        s = s * 3 + 1
    t.append(s)
    if t.count(s) == 2:
        print(len(t))
        break
```