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

ABC230のA-E問題の解説。

目次

A - AtCoder Quiz 3
B - Triple Metre
C - X drawing
D - Destroyer Takahashi

A - AtCoder Quiz 3

解説

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

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

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

コード

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

解説

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

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

コード

def main():
    s = input()
    t = 'oxx'*(10**5)

    if s in t:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

C - X drawing

解説

$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)$で、どちらかの条件を満たしたときに#、それ以外であれば.を出力すれば良い。

コード

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

解説

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

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

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

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

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

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

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

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

コード

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()

編集後記

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