PythonでAtCoder Beginner Contest 271 の解説とか感想とか(A~D問題)

AtCoder Beginner Contest 271のA～D問題を解いたので、その解説や感想などを書いていきます！

緑コーダー以下くらいの方の参考になればと思います。

言語はPythonを使って解いていきます！

KYOCERA Programming Contest 2022（AtCoder Beginner Contest 271） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A: 484558
B: Maintain Multiple Sequences
C: Manga
D: Flip and Adjust
おわりに

A: 484558

与えられた数字を16進数で表現する問題です。

真面目にしようとすると、与えられた数字を16で割って各桁に対応する数字を求めることになります。

ただ、Pythonにはformatというものがあり、これを使うと数字を16進数へと変換してくれます。（16進数以外にも8進数に変換することもできます！）

また、このformatには何桁で出力するかというのも指定することができるので、2桁の16進数というformatで出力すると良いですね。

こんな感じのコードになると思います。

02というのが0埋めの2桁で、Xが16進数ということを表しています。

n = int(input())

print('{:02X}'.format(n))

B: Maintain Multiple Sequences

複数の数列が与えられたときに、指定された数列の指定されたところにある数字を答える問題です。

Pythonにはリストというデータ格納方法があるので、このリストに数列を入れると扱いやすいです。

与えられる配列は1文字目に数列の長さを表す数字が入っているのと、リストはインデックスが0から始まることに注意して、以下のようなコードで提出しました。

n, q = map(int,input().split())

A = []
for _ in range(n):
    a = list(map(int,input().split()))
    A.append(a[1:])

for _ in range(q):
    s,t = map(int,input().split())

    print(A[s-1][t-1])

C: Manga

操作（持ってる漫画を2冊売って1冊新たに買う）を任意の回数繰り返したときに、最大何巻まで読めるかという問題です。

シミュレーションしながら答えを求めることにします。

持っている漫画を巻数順にソートしたとき、小さい順で巻数を見て次の巻が連続になっていなければ、2冊以上持っている or 持っている中で最大の巻数を売って次の巻を買うとすれば良いはずです。

これを実現するために、dequeを使うと良いです。

dequeはキューという、配列の先頭もしくは後ろの要素を追加したり取り出したりすることが得意なデータ構造です。（ロケット鉛筆みたいな）

このdequeを使って、基本は先頭から要素を取り出して（小さい順に巻数を読んでいることに相当）いき、取り出した要素が不連続なら後ろから2個取り出す（2冊売って次の巻を買う操作に相当）という操作をできなくなるまですれば答えがでてきます。

また、2冊以上ある巻を先に売った方が効率が良いので、そういう巻はdequeを作るときに1つはちゃんとした順番で、残りはdequeの後ろに入れればよいです。

計算量はソートの部分がネックとなりO(NlogN)で解けると思います。

コードはこんな感じになりました。

from collections import deque

n = int(input())
A = list(map(int, input().split()))

A.sort()

s = set(A)
# キューは重複なしのキューを先に作って、被っている冊数分だけ後ろに適当な数字を入れる
queue = deque(s)
for _ in range(n - len(s)):
    queue.append(1)

ans = 0

while len(queue) > 0:
    a = queue.popleft()
    if ans + 1 == a:
        ans += 1

    else:
        queue.appendleft(a)
        if len(queue) > 1:
            b = queue.pop()
            c = queue.pop()
            ans += 1
        else:
            break
print(ans)

解説を見ると2分法を使うやり方も載っており、競プロ典型のときに出てきたやつだ！とも思いましたが、なかなか思いつくのは大変ですね…

D: Flip and Adjust

カードに書かれた数字の和をある数字にできるか判定する問題です。

カードの表裏に数字が書かれているのですが、これを全探索しようとするとO(2^N)となってしまい、とてもじゃないですが計算が終わりません。

そこで動的計画法を用いることにします。

dp[i][j] i枚目までのカードを用いて和をjにできる。その置き方はH, Tをつかった文字列であらわされる。（和をjにできないなら-1）

という配列をつくって

i枚目のカードに対して、dp[i-1][j]のすべてに対して、値が-1でないなら

　　　　dp[i][j+a_i]=dp[i-1][j] + ‘H’

　　　　dp[i][j+b_i]=dp[i-1][j] + ‘T’

と値を更新していけばよいです。なお、j+a_iとj+b_iが同じときはどっちかだけを代入すれば十分です。

最後に、dp[-1][s]が-1でなければ和をSにできるので、そのときの値（’HTTHT…’）を出力すれば答えになります。

コードはこんな感じになりました。

n,s = map(int,input().split())

A = []
for _ in range(n):
    a,b = map(int,input().split())
    A.append([a,b])

dp = [[-1 for _ in range(s+200)] for _ in range(n+1)]
dp[0][0] = 0

c = 0
for a in A:
    if c == 0:
        dp[c+1][a[0]] = 'H'
        dp[c+1][a[1]] = 'T'
        c = 1
        continue
    for i in range(s):
        if dp[c][i] != -1:
            dp[c+1][i+a[0]] = dp[c][i]+'H'
            dp[c+1][i+a[1]] = dp[c][i]+'T'

    c += 1

if dp[-1][s] == -1:
    print('No')
else:
    print('Yes')
    print(dp[-1][s])