【AtCoder】ABC221をPython3で解説（ABCD


ABCのA-D問題の解説。

https://atcoder.jp/contests/abc221

## 目次
[A - Seismic magnitude scales](#a---seismic-magnitude-scales)
[B - typo](#b---typo)
[C - Select Mul](#c---select-mul)
[D - Online games](#d---online-games)

## A - Seismic magnitude scales 

https://atcoder.jp/contests/abc221/tasks/abc221_a

### 解説

マグニチュード`A`の地震のエネルギーの大きさはマグニチュード`B`の自身のエネルギーの大きさの何倍かを求める問題。

このとき`A`は`B`以上であることがわかっているので、`A`から`B`を引いてあげた値分、32倍してあげるとよい。

### コード
```python
def main():
    a, b = map(int, input().split())

    print(32**(a-b))

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

## B - typo

https://atcoder.jp/contests/abc221/tasks/abc221_b

### 解説

文字列`S`と`T`が与えられ、`S`の隣り合う2文字を入れ替える操作を1回以下行うことで、`T`と一致するか求める問題。

まず、そもそも`S == T`であれば、入れ替える必要がないため、この時点で答えは`Yes`となる。

次に、入れ替える操作であるが、連続する2文字をいれかえればいいだけなので、`S[i], S[i+1] = S[i+1], S[i]`とし、値を入れ替えて判定する。`S`と`T`が合わなければ、また文字列をもとに戻し、文字列の長さまでこの操作を繰り返す。

### コード
```python
def main():
    S = list(input())
    T = list(input())

    ans = 'No'

    if S == T:
        ans = 'Yes'

    for i in range(len(S)-1):
        S[i], S[i+1] = S[i+1], S[i]
        if S == T:
            ans = 'Yes'
        S[i], S[i+1] = S[i+1], S[i]

    print(ans)

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

## C - Select Mul

https://atcoder.jp/contests/abc221/tasks/abc221_c

### 解説

入力した数字の文字列の中から、値を2つにわけ、その積の最大値を求める問題。

まず、積の最大値を求めたいので、入力した数字を降順に並び替える。さらに、積の最大値をとるためには、それぞれの桁数を最大にする必要がある。例えば、$1234$という数字があれば、$1 \times 234$よりも$12 \times 34$のほうが大きいことから明白である。

したがって、先程降順にソートした数字を1つずつ順番に、新たに2つの数字として振り分ける。

振り分けられた2つ数字の積では、まだ最大値とはえいえない。このとき桁数の少ない方の数字をできるだけ最大化してあげることで、積の最大値を求めることができる。つまり、2つの数字を桁数が高い方から順番に見ていき、その桁の値が異なる場合、値を入れ替えてあげることで、積の最大値となる2つの数字を求めることができる。

### コード1（for）
```python
def main():
    n = input()
    nsort = sorted(n, reverse=True) # 降順に並び替え

    a = nsort[0::2] # インデックス0から1つ飛ばしでリストわけ
    b = nsort[1::2] # インデックス1から1つ飛ばしでリストわけ
    
    for i in range(min(len(a), len(b))):
        if a[i] != b[i]:
            a[i], b[i] = b[i], a[i]
            break

    print(int(''.join(a)) * int(''.join(b)))

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

### コード2（bit全探索）
```python
def main():
    n = input()
    nsort = sorted(n, reverse=True)

    ans = 0

    for i in range(1 << len(nsort)):
        l = 0
        r = 0
        for j in range(len(nsort)):
            if i & (1 << j):
                l = l * 10 + ord(nsort[j]) - ord('0')
            else:
                r = r * 10 + ord(nsort[j]) - ord('0')

        ans = max(ans, l * r)

    print(ans)

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

## D - Online games

https://atcoder.jp/contests/abc221/submissions/me

### 解説

`i`番目のプレイヤーは、$A_i$日目から$B_i$日間連続でログインしている。このとき、`1`日目から`N`日目までのなかで、ちょうど`k`人がログインしていた日数を求める問題。

これは、ログインした日とログアウトした日に注目すると問題がとける。

まず、入力値である`a`と`b`について、`i`番目の人がログインした日を$a$で日数を`+1`、ログアウトした日を$a+b$で日数を`-1`とし、タプルとして管理する。

これら入力した値を昇順にソートしてあげることで、ログイン・ログアウトの情報が日付順になっているため、一つの配列で管理することができる。

この配列内のタプルを前から一つずつ見ていく。

まず、その日は、ログインしたのか、ログアウトしたのかを確認する。つまり、配列内のタプルの2番目の要素が`+1`か`-1`かを考える。これをある変数（`cnt`）で管理してあげることで、その日は何人がログインしているかを把握することができる。

この`cnt`は、次の日、つまり、配列内の次のタプルの1番目の値までの日数続くので、差分を計算して、事前に用意しておいた各日の人数を保存する配列`ans`の`cnt`番目に値をいれてあげるとよい。このとき`ans`は、`N`の最大値である、$2 \times 10 ^ 5$よりも多く要素を準備しておく。

これで求めた`ans`を1人からn人まで分出力すると`AC`。


### コード
```python
def main():
    n = int(input())
    x = []
    temp = 200010

    for _ in range(n):
        a, b = map(int, input().split())
        x.append((a, 1))
        x.append((a+b, -1))

    xsort = sorted(x)

    cnt = 0
    ans = [0 for _ in range(temp)]

    for i in range(len(xsort)-1):
        cnt += xsort[i][1]  # cnt人がログイン
        ans[cnt] += xsort[i+1][0] - xsort[i][0]

    ans = ans[1:n+1]  # 1人からn人までの答えを出力
    print(*ans)


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

## 編集後記

復習サボったらいけないですね...。