【ABC340】競プロのA-C問題を40代サラリーマンがPython解説！初心者にもわかりやすく

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC340のA問題〜C問題の自身の解答と解答説明をしていきます。

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回の参加コンテスト(ABC340)

AtCoder Beginner Contest 340

A問題：Arithmetic Progression

A – Arithmetic Progression

問題文

初項が A、末項が B、公差が D であるような等差数列を出力してください。なお、そのような等差数列が存在する入力のみが与えられます。

解答

# 入力を受け取り、整数に変換
a, b, d = map(int, input().split())

# 等差数列の各項を出力
print(*list(x for x in range(a, b + 1, d)))

考え方）

range関数の第２項目は、与えた数字の一つ前までなので、 b + 1 を行なっています。

1. 入力受付: input().split()で入力を受け取り、map(int, ...)でそれぞれ整数に変換しています。
2. 数列の生成と出力: range(a, b + 1, d)で初項aから末項bまでの等差数列を生成し、print(*list(...))でリスト内包表記を用いて生成した数列の各項をスペース区切りで出力しています。

B問題：Append

B – Append

問題(要約)

空の数列Aに対して、Q個のクエリを順番に処理する問題です。

1. 1 x: 数列Aの末尾にxを追加する。
2. 2 k: 数列Aの後ろからk番目の値を出力する。

解答

# クエリの数を入力
q = int(input())

# 空の数列Aを初期化
A = []

# Q回のクエリを処理
for _ in range(q):
    # クエリの種類と値（または位置）を入力
    n, s = input().split()
    if n == '1':
        # クエリ1の場合、数列Aの末尾にsを追加
        A.append(s)
    else:
        # クエリ2の場合、数列Aの後ろからs番目の値を出力
        print(A[-int(s)])

解き方）

クエリ 2 k の場合の後ろから x番目を A[-x] を用いることにより簡単に解くことができます。

1. クエリの数受付: 最初にクエリの数qを入力として受け取ります。
2. 数列Aの初期化: 空の数列Aを初期化します。
3. クエリの処理: q回のループを使用して、各クエリを処理します。
   • クエリ1の処理: 入力されたnが'1'の場合、A.append(s)を用いて数列Aの末尾に要素sを追加します。
   • クエリ2の処理: 入力されたnが'2'の場合、print(A[-int(s)])を用いて数列Aの後ろからint(s)番目の値を出力します。

C問題：Divide and Divide

C – Divide and Divide

問題(要約)

黒板に整数Nが書かれています。2以上の整数がなくなるまで、黒板に書かれた整数を1つ選び、それを消して新たに2つの整数を書く操作を繰り返します。操作には費用がかかり、操作を行えなくなった時点での総費用を求めます。

解答

def div_num(x, memo):
    # xが2未満なら費用は0
    if x < 2:
        return 0
    
    # 既に計算済みならその値を返す
    if x in memo:
        return memo[x]
    
    # xを2で分割
    a = x // 2
    b = x - a
    
    # 分割した値に対して再帰的に処理を行い、結果をメモ化
    memo[x] = x + div_num(a, memo) + div_num(b, memo) if a != b else x + 2 * div_num(a, memo)
    
    return memo[x]

# 入力されたNに対して関数を実行
print(div_num(int(input()), {}))


解き方）

メモ化再帰の考え方を用いて解いています。memo[x]に以前の計算を登録することにより、再計算を避けて時間の効率化を行なっています。

1. 基本条件の確認: 入力されたxが2未満の場合、操作は不要なので費用は0円です。
2. メモ化の活用: 以前に計算したxの結果を辞書memoに保存しておき、同じ計算を避けることで効率化します。
3. 数の分割: xを2で分割し、aとbとして、それぞれに対して同じ操作を再帰的に適用します。
4. 費用の計算とメモ化: 分割した数に対する操作費用を再帰的に計算し、その和に現在のxの値を加えたものが現在の操作での総費用になります。この値をmemoに記録して、次回以降同じxが出たときの計算を省略します。
5. 結果の出力: 最初に入力されたNに対して定義した関数を実行し、その結果を出力します。

感想

今回は、B問題までしか解くことができませんでした。

A問題は等差数列の出力が問われており、Pythonのrange関数をうまく使えば簡単に解けるタイプでした。

B問題は今週は比較的簡単で、リストのスライスに関する理解があれば速やかに解答に至れたはずです。

C問題には大きな挑戦がありました。制約が10¹⁷と非常に大きく、これが問題の難易度をぐっと引き上げていました。また、問題文にはゲルシュゴレンの括弧（天井括弧や床括弧）が登場し、私はこれが初見だったため理解に時間がかかりました。問題文をじっくり読み解くことで、内容は理解できたものの、解法を実装できたものの、時間制限超過で不正解。さらに1時間以上をかけて実行時間削減を試みましたが、解答には至りませんでした。正解のコードを見ると、メモ化再帰を活用することで効率的に解けていました。メモ化再帰は今回初めて深く学んだ概念で、非常に役立つ知識でした。ただし、私の環境では@cacheデコレータを使用できなかったため、代わりに辞書を使った独自のメモ化を行いました。

2024年に入ってからは苦戦が続き、順位も509位に落ち込んでしまいました。しかし、今回学んだメモ化再帰を次回以降の問題解決に生かし、順位回復を目指していきたいと思います。

それでは、皆さんも競プロライフを楽しんでくださいね！(*＾▽＾)／