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

ABC230のA-E問題の解説。

https://atcoder.jp/contests/abc230

## 目次
[A - AtCoder Quiz 3](#a---atcoder-quiz-3)
[B - Triple Metre](#b---triple-metre)
[C - X drawing](#c---x-drawing)
[D - Destroyer Takahashi](#d---destroyer-takahashi)

## A - AtCoder Quiz 3

https://atcoder.jp/contests/abc230/tasks/abc230_a

### 解説

42回以降に開催されたコンテストには、コンテストの名前に1大きい数が割り振られている。
このとき、`N`回目に開催されたAGCを`AGCXXX`の形式で出力するという問題。

42回以降は`if`を使って条件分岐ができる。`AGCXXX`にするためには、空いている場所を0で埋める必要がある。

これは、pythonでは、`zfill()`を使うことで、0埋めができる。`数字.zfill(何桁まで0を埋めるか)`と書くことで`AC`できる。

https://note.nkmk.me/python-zero-padding/


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

    if n >= 42:
        print('AGC' + str(n+1).zfill(3))
    else:
        print('AGC' + str(n).zfill(3))

if __name__ == '__main__':
    main()
```
## B - Triple Metre

https://atcoder.jp/contests/abc230/tasks/abc230_b

### 解説

入力された文字列`S`が、`oox`を$10^5$つなげた文字列`T`のなかに存在するかどうかを求める問題。

これは、`if`文だけで実装できる。`if 探したい文字列 in 探し出してくる文字列:`と書くことで、もし、探したい文字列が、探し出してくる文字列のなかにあれば`True`を返してくれる。

### コード
```python
def main():
    s = input()
    t = 'oxx'*(10**5)
    
    if s in t:
        print('Yes')
    else:
        print('No')
        
if __name__ == '__main__':
    main()
```
## C - X drawing

https://atcoder.jp/contests/abc230/tasks/abc230_c

### 解説

$N \times N$のマス目があり、はじめはすべて白く塗られている。このとき、次の条件を満たすマス目を黒く塗る。

・$max(1−A,1−B)≤k≤min(N−A,N−B)$をみたす全ての整数 k の$(A+k,B+k)$

・$max(1−A,B−N)≤k≤min(N−A,B−1)$をみたす全ての整数 k の$(A+k,B−k)$

このとき、$P≤i≤Q かつ R≤j≤S$をみたす各マス$(i,j)$がそれぞれ何色で塗られているか求める問題。

どちらの条件をややこしく見えるが、言い換えるとかんたんになる。

1つ目は、$max(1−A,1−B) \leq k \leq min(N−A,N−B)$だが、これは、

$1-A \leq k \leq N-A$　かつ　$1-B \leq k \leq N-B$

と言い換えることができる。これについて、それぞれの不等式にAとBを足してあげると、

$1 \leq A+k \leq N$　かつ　$1 \leq B+k \leq N$

と言い換えることができる。

さらに、$A+k$を$i$、$B+k$を$j$とすると、

$1 \leq i \leq N$　かつ　$1 \leq j \leq N$　かつ　$i-j=A-B$

と同じである。

2つ目も同様に考えると、

$1 \leq i \leq N$　かつ　$1 \leq j \leq N$　かつ　$i+j=A+B$

となる。

これについて、$P≤i≤Q$かつ$R≤j≤S$における$(i,j)$で、どちらかの条件を満たしたときに`#`、それ以外であれば`.`を出力すれば良い。

### コード
```python

def main():
    n, a, b = map(int, input().split())
    p, q, r, s = map(int, input().split())
    
    for i in range(p, q+1):
        axis = []
        for j in range(r, s+1):
            if (i-j) == (a-b):
                axis.append('#')
            elif (i+j) == (a+b):
                axis.append('#')
            else:
                axis.append('.')
        print(''.join(axis))
        
                
if __name__ == '__main__':
    main()
```
## D - Destroyer Takahashi

https://atcoder.jp/contests/abc230/tasks/abc230_d

### 解説

$N$枚の壁があり、壁$i$は$L_i$列目から$R_i$列目に存在する。この壁には、$D$列の範囲にパンチができ、パンチが一部分でも壁に触れれば、全体が破壊される。

このときすべての壁を破壊するためには、少なくとも何回のパンチが必要かを求める問題。

結論から言うと、「右端の位置の数字が0に近い壁から優先的に破壊していく」という方法で行う。

まず、壁の右端の位置を、昇順にならべかえる。これを1枚ずつ見ていく。

破壊した壁の右端の位置からパンチの幅までに、今見ている壁の左端の位置が含まれているかどうかを判定する。

もし含まれていれば、壁が部分的に破壊されている、つまり、壁が破壊されているので、次の壁をみる。

もし含まれていなければ、今見ている壁はまだ破壊されていないので、パンチをして壁を破壊（`ans+=1`）し、その壁の右端の値を保存する。これがはじめの「破壊した壁の右端」、に相当するので、すべての壁をみることで、最小のパンチ数を求めることができる。

![Qiita-8.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/644067cd-230a-b81d-c346-d2f8950cece6.jpeg)


この問題は、**区間スケジューリング**問題と呼ばれている。以前開催されたコンテストでも、このような問題を取り扱っている。

https://qiita.com/uniTM/items/0dbd7ec962186c005c08

![Qiita-7.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/4983910c-cbe9-e926-5079-85c3f0ce2ebd.jpeg)


### コード
```python
def main():
    n, d = map(int, input().split())
    lrlist = [list(map(int, input().split())) for _ in range(n)]

    sort_lrlist = sorted(lrlist, key=lambda x: (x[1], x[0]))

    ans = 0
    x = -(10**10)

    for l, r in sort_lrlist:
        if x + d - 1 < l:
            ans += 1
            x = r

    print(ans)


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

## 編集後記

区間スケジューリング問題...。勉強します。