【AtCoder】ABC216をPython3で解説（ABCDE）

ABC216のA-E問題の解説。

https://atcoder.jp/contests/abc216

## 目次
[A - Signed Difficulty](#a---signed-difficulty)
[B - Same Name](#b---same-name)
[C - Many Balls](#c---many-balls)
[D - Pair of Balls](#d---pair-of-balls)
[E - Amusement Park](#e---amusement-park)

## A - Signed Difficulty
### 解説

$X.Y$を$Y$に対して、$X$の表示方法を変えるという条件分岐問題。
`.`に対して、2つに分けることができれば`AC`。

### コード

```python
def main():
    x, y = map(int, input().split('.'))

    if 0 <= y and y <= 2:
        print(str(x)+'-')
    elif 3 <= y and y <= 6:
        print(str(x))
    elif 7 <= y and y <= 9:
        print(str(x)+'+')

if __name__ == '__main__':
    main()

```

## B - Same Name
### 解説

問題文を簡潔にまとめると、ひとりひとり順番に名前を記録していき、記録した名前の中に同姓同名の名前があれば、`Yes`を出力、なければ、`No`を出力するという問題。

そのとおりに実装すれば`AC`。

### コード
```python
def main():
    n = int(input())

    names = []

    for i in range(n):
        s, t = map(str, input().split())
        if (s, t) in names:
            print('Yes')
            exit()

        names.append((s, t))

    print('No')

if __name__ == '__main__':
    main()
```

## C - Many Balls
### 解説

箱の中にボールを1つ増やすのと、箱の中のボールの数を2倍にする、という2つの操作ではこの中のボールの数をちょうど`N`個にする方法を探す問題。

合計120回という制約があるが、例えば、魔法Bだけを最大回数使った場合、最大値は$2^{120}$、つまり、$1.3 \times 10^{36}$なので、制約$(1 \leq N \leq 10^{18}) \leq 10^{36}$より十分満たしています。したがって、2倍が使えるときは積極的に魔法Bを使います。

解法の1つとして、`N`を逆順に操作するという方法があります。`N`が偶数のときは2で割った数を`N`に再代入、`N`が奇数のときは1を引いた数を`N`に再代入、これを`N`が0よりも大きいときに続けて、`A, B`を順番に並べます。

最後にこの順番は逆順で操作しているので、文字列自体を反転させることで`AC`できる。


### コード
```python
def main():
    n = int(input())

    ans = ''

    while n > 0:
        if n % 2 == 0:
            n //= 2
            ans += 'B'
        else:
            n -= 1
            ans += 'A'

    print(''.join(list(reversed(ans))))

if __name__ == '__main__':
    main()
```

## D - Pair of Balls
### 解説

今、$1$以上$N$以下で表される色を持ったボールが$2N$個ある。各色で塗られたボールは、ちょうど2個ずつ存在することが保証されている。
このとき、$i$番目の筒に$k_i$個のボールが入っている。上から$j$番目のボールの色は$a_{i, j}$で表される。

このとき、異なる2つの筒の一番上にある色のなかに同じ色があれば、それを取り出し、筒の中を空にすることができるかという問題。

ある容器から取り出す操作があるので、`deque`を使うのが無難である。

まず、それぞれのボールを保存する筒と、筒の一番上のボールを保存する容器を用意する。このとき、同じ色を持つボールを管理する容器として、`deque`を用いる。

すべての筒の一番上のボールを保存する容器を`top`とする。`top`にボールを入れるとき、筒の番号を挿入する。こうすることで、次にボールとりだす筒を判定することができる。

各筒から一番上のボールをそれぞれ1つとりだし、その2つについて、ボールの色が揃っているかどうか判定する。もし色が揃っているボールが存在したら、`que`に追加する。もし、`que`に値がない、つまり、色が揃っているボールの色が存在しなくなったら、`while`ループを抜けて判定に入る。

どれかの筒に1つでも値が残っていたら、今回の「筒の中を空にする」という条件をみたしていないので、`if`が`False`となる。逆に、筒がすべて空になっていれば条件を見対しているので、`if`が`True`になる。

### コード
```python
def main():
    from collections import deque

    n, m = map(int, input().split())
    tubes = []

    for _ in range(m): # それぞれのボールを保存する筒を準備する
        k = int(input())
        tube = list(map(lambda x: x-1, list(map(int, input().split()))))
        tubes.append(tube)

    top = [[] for _ in range(n)] # n色分の容器を用意

    for i in range(m):
        if tubes[i]:
            top[tubes[i][-1]].append(i)

    que = deque([i for i in range(n) if len(top[i]) == 2]) # 同じボールが2個ある容器をqueに入れる

    while que:
        v = que.popleft()
        i, j = top[v]

        tubes[i].pop() # tubeから揃ったボールを取り出す
        tubes[j].pop() # tubeから揃ったボールを取り出す

        if tubes[i]:
            top[tubes[i][-1]].append(i) # 新しいボールをtopに追加
            if len(top[tubes[i][-1]]) == 2: # 同じ色のボールが2つ揃ったら
                que.append(tubes[i][-1]) # queに追加

        if tubes[j]:
            top[tubes[j][-1]].append(j) # 同様
            if len(top[tubes[j][-1]]) == 2:
                que.append(tubes[j][-1])

    if all(not tubes[i] for i in range(m)): # すべてのtubeが空、つまり、[]であれば
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()
```

## E - Amusement Park
### 解説

`N`個のアトラクションにそれぞれの満足度が与えられいて、1回乗るごとにそのアトラクションの満足度は1減少する。また、アトラクションは$K$回まで乗ることができる。

このとき、高橋くんの最終的な「満足度」の最大値はいくつかを答える問題。

$A$をソートして、常に最大値を取り続けるという方法が考えられるが、この操作を$K$回行うと、制約が最大$2 \times 10^9$なので、AtCoderの判定には間に合わない。

では、どうすればよいか。以下の記事でも解説しているが、1) 最大値を求める、2) 制約が$10^9$、という2つが読み取れるので、**二分探索**を用いることで、今回の答えを求めることができる。

二分探索を用いて、どんな判定問題を考えればいいかというと、以下のような数列$B$を考えて、

$B = [1, 2, ..., A_1, 1, 2, ..., A_2, ..., 1, 2, ..., A_N]$

> 数列$B$に含まれているm以上の値は$K$個以下か？

という単調性を持つ問題を考えれば良い。この$m$を求める操作に、二分探索を用いる。

例えば、$A = [10, 8, 6]$という数列$A$で$K = 5$のときを考える。これは、$B = [1, 2, ..., 10, 1, 2, ..., 8, 1, 2, ..., 6]$から、$m$以上の値を持つものが$K$個以下であるかを判定すれば良い。

二分探索によりこの$m$は8であることがわかる。よって$B$から、`8, 8, 9, 10`の4つがとりだせる。これは合計$K$回以内を満たしている。$5 - 4 = 1$でまだ1回分残っているがとりあえずは気にする必要はない。

これで$B$の値を全部足せば良い、が、制約が大きいので実際に$B$という数列を作り出すことはできない。ではどうすればよいかというと、「$1$から$A$までの和」から「$1$から求めた$m$までの和」を引くことで、$B$を再現することができる。参考までに$1$から$n$までの和を示した式を以下に示しておく。

> $\frac{1}{2} n (n+1)$

これで、$B$から取り出した$m$以上の和を実装できる。残りの1回分は$m$から1引いた数を$K$回分、先程の答えに足してやれば、最大の「満足度」を求めることができる。

二分探索について深堀りしたい方は、こちらの記事からさまざまな問題に取り組んでいただきたい。

https://qiita.com/uniTM/items/2f2a38f225f04154df9a

### コード
```python
def main():

    def is_ok(x):
        now = 0
        for i in range(n):
            if alist[i] >= x: # A_iがx以上の数であるとき
                now += alist[i]-x+1 # iのアトラクションに何回乗ったか
        return now <= k

    # めぐる式二分探索
    def meguru_bisect(ng, ok):
        while (abs(ok - ng) > 1):
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    n, k = map(int, input().split())
    alist = list(map(int, input().split()))

    ng, ok = -1, 2*10**9+1

    ok = meguru_bisect(ng, ok)

    temp = 0
    cnt = 0

    for i in range(n):
        if alist[i] >= ok:  # Aの中でok以上の数ならば
            cnt += alist[i] - ok + 1  # アトラクションiに乗った回数
            # 初項A公差-1の0までの和と初項ok公差-1の0までの和を引いた値（満足度）
            temp += alist[i]*(alist[i]+1)//2 - ok*(ok-1)//2

    if ok != 0:
        temp += (ok-1) * (k-cnt) # アトラクションの残り回数を使い切る

    print(temp)


if __name__ == '__main__':
    main()
```

## 編集後記

E問題、二分探索ということに気づけて、初めて解けるかなーと思ったが、条件文を全く思いつくことできず、コンテストが終了してしまった...。