【AtCoder】ABC222をPython3で解説（ABCD）

ABC222のA-D問題の解説。

https://atcoder.jp/contests/abc222

## 目次
[A - Four Digits](#a---four-digits)
[B - Failing Grade](#b---failing-grade)
[C - Swiss-System Tournament](#c---swiss-system-tournament)
[D - Between Two Arrays](#d---between-two-arrays)

## A - Four Digits

https://atcoder.jp/contests/abc222/tasks/abc222_a

### 必要な知識

- zfill()
- f文字列

### 解説

与えられた整数を4桁になるように、0を加える問題。

Pythonでは、指定した桁数を0で埋めてくれる`zfill()`というものがあるので、こちらを使うとかんたんに`AC`できる。

### コード1
```python
def main():
    n = input()
    print(n.zfill(4))

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

また、f文字列を使う方法もある。

### コード2

```python
def main():
    n = int(input())
    print(f'{n:04d}')

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

## B - Failing Grade

https://atcoder.jp/contests/abc222/tasks/abc222_b

### 必要な知識

- for
- (filter)

### 解説

学生の点数`a`から、`P`未満の点数をとった人数を数える問題。

これは、`for`と`if`を使うことで`AC`できる。

### コード1
```python
def main():
    n, p = map(int, input().split())
    alist = list(map(int, input().split()))

    cnt = 0

    for a in alist:
        if p > a:
            cnt += 1

    print(cnt)

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

また、`filter()`を用いても求めることができる。

### コード2
```python
def main():
    n, p = map(int, input().split())
    alist = list(map(int, input().split()))

    ans = len(list(filter(lambda x: x < p, alist)))

    print(ans)

if __name__ == '__main__':
    main()
```
## C - Swiss-System Tournament

https://atcoder.jp/contests/abc222/tasks/abc222_c

### 必要な知識

- sort()
- 二重ループ
- 2次元配列

### 解説

1位, 2位 と 3位, 4位...と連続する順位の人同士でじゃんけんさせて、勝利した方に+1ポイントをあたえる。その後、「勝数が多い」または「番号が小さい」人を上位として並び替えをし、同じことを繰り返す。

連続する人同士のじゃんけんは2倍したインデックス番号とそれに1を足したインデックス番号の手を参照してくれば良い。

問題なのが並び替えだ。勝数が多い、はかんたんに並び替えできるが、番号が小さいとなると同時に並び替えができなくなる。ここで、番号が小さい順番にソートする頃を前提に、勝数が多い順にするのではなく、勝数をマイナスの値にして並び替えすると、どちらも小さい順番に並び替えするだけでいい。

### コード
```python
def main():
    n, m = map(int, input().split())
    alist = []

    for i in range(2*n):
        temp = list(input())
        alist.append(temp)

    person = [[0, i] for i in range(2*n)]

    for i in range(m):
        person.sort()
        for j in range(n):
            right = alist[person[2*j][1]][i]
            left = alist[person[2*j+1][1]][i]
            if right == 'G' and left == 'C':
                person[2*j][0] -= 1
            elif right == 'C' and left == 'P':
                person[2*j][0] -= 1
            elif right == 'P' and left == 'G':
                person[2*j][0] -= 1
            elif right == left:
                pass
            else:
                person[2*j+1][0] -= 1

    person.sort()
    for i in range(2*n):
        print(person[i][1]+1)

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

## D - Between Two Arrays

https://atcoder.jp/contests/abc222/tasks/abc222_d

### 必要な知識

- **DP**
- 累積和
- （MODで割ったあまり）

### 解説

与えられた`a`と`b`の間の数字から、`[1, 2, 3, 3, 4, ...]`のような右側に一方的に増加する数列は何個あるかを求める問題。

普通に全通りやろうと思うと、最悪計算量が$3000^{3000}$で確実に間に合わない。そこで、DPを活用する。今回は、`1, 2, 3, ..`のように単調に増加するかどうかだけを判断すればいいので、ひとつ前の値がわかれば、答えを導き出すことができる。

コードの解説をする。まず、DPの配列、そして、その次の値を保持する配列`nxt`を用意する。一番外側のループは、Cの配列の長さ分回す。次のループは、`a`から`b`の値に対して、後に求める1つ前の累積和`dp`をみて、`a`から`b`に当たる値を`nxt`に保存する。この配列を`dp`として渡し、累積和をとる。ここで累積和を取る理由は、先程にも述べたとおり、1つ前までの値を参照すれば良いので、その値までの値の個数で答えとなる`C`の数列の個数が決まるからである。

最終的な答えは、`C`の一番最後の値を答えてあげれば`AC`。

### コード
```python
def main():
    MOD = 998244353

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

    m = 3000

    dp = [1] * (m+1)

    for i in range(n):
        nxt = [0]*(m+1)
        for j in range(alist[i], blist[i]+1):
            # 1つ前の累積和を見て
            # aからbに当たる値をnxtに保存
            nxt[j] = dp[j]

        dp = nxt

        # 累積和
        # 1つ前の値までに値が何個あるかで数列の個数が決まる
        for i in range(m):
            dp[i+1] += dp[i]
            dp[i+1] %= MOD

    print(dp[m])


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

## 編集後記
DPの解説記事をおいおい出そうかな
自分でもまだ全然なれてない部分がある...