初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC335_A-C問題】

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

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

こんな人にオススメしたい

競技プログラミング初心者で、問題の解き方がわからない方
AtCoderの公式解説は読んだが、内容が理解できなかった方
Pythonでの解法を知りたい方

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

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

今回の参加コンテスト(ABC335)
感想

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

AtCoder Beginner Contest 335

A問題：202<s>3</s>

A – 202<s>3</s>

問題文

英小文字と数字からなる文字列 S が入力されます。
S は 2023 で終わることが保証されます。
S の最後の文字を 4 に変更し、変更後の文字列を出力してください。

解答

# 標準入力から文字列Sを受け取る
S = input()

# 文字列Sの最初の文字から最後から2番目の文字までを順に出力
for i in range(len(S)-1):  # len(S)-1は最後の文字のインデックスより1小さい値
    print(S[i], end="")  # 各文字を改行せずに出力（最後の文字を除く）

# 最後の文字（'3'）を'4'に置き換えて出力
print(4)  # '4' を出力し、文字列の変更を完了する

解き方）

文字と数字の置き換えは、混在はエラーを起こしやすいため、最後の1文字を別に考えています。

プログラムがユーザーの標準入力を受け取ることを待機します。
ユーザーによって入力された文字列 S を受け取ります。この文字列は数字の「2023」で終わることが保証されています。
for ループを使用して、文字列 S の最初の文字から最後の文字のひとつ前までを一つずつ出力します。
- range(len(S)-1) は、文字列の長さから1を引いた範囲を生成し、これにより最後の文字は除外されます。
- print(S[i], end="") は、インデックス i の文字を出力し、行の最後に新しい行を始めずに次の文字を続けて出力します。
for ループが終了すると、print(4) が実行され、ループの出力に続けて「4」が出力されます。これにより、文字列の最後の文字が「4」に置き換わります。

B問題：Tetrahedral Number

B – Tetrahedral Number

問題

整数 N が与えられます。

非負整数の組 (x,y,z) であって x+y+z≤N を満たすものを辞書順で小さい方から順に全て出力してください。

解答

# 標準入力から整数 N を受け取る
n = int(input())

# 非負整数 i, j, k について、それぞれ 0 から N までループを行う
for i in range(n+1):  # i が 0 から N まで
    for j in range(n+1):  # j が 0 から N まで
        for k in range(n+1):  # k が 0 から N まで
            if i + j + k <= n:  # i, j, k の和が N 以下の場合
                print(i, j, k)  # 条件を満たす (i, j, k) の組を出力

解き方）

単純に三重ループを行い、i + j + k <= n を確認するだけで解けます。

標準入力から整数 N を受け取る。
i について、0から N までの範囲でループを開始する。
同様に j についても、0から N までの範囲でループを開始する。
k に関しても、0から N までの範囲でループを開始する。
それぞれのループ内で、i + j + k の和が N 以下であるかを確認する。
もし和が N 以下ならば、その時点での (i, j, k) の組を出力する。
すべての可能な組み合わせに対してステップ 2 から 6 を繰り返す。
これにより、(x, y, z) で x + y + z ≤ N を満たすすべての組を辞書順で出力する。

C問題：Loong Tracking

C – Loong Tracking

問題(要約)

高橋君は座標平面上で龍を操作するゲームを作成しました。

龍は 1 から N までの番号がついた N 個のパーツからなり、パーツ 1 を頭と呼びます。

最初パーツ i は座標 (i,0) にあります。以下のクエリを Q 個処理してください。

1 C: 頭を方向 C に 1 移動させる。ここで、C は R, L, U, D のいずれかであり、それぞれ x軸正方向、x 軸負方向、y 軸正方向、y 軸負方向を意味する。頭以外の全てのパーツは前のパーツに追従するように動く。すなわち、パーツ i (2≤i≤N) は移動前にパーツ i−1 があった座標に移動する。
2 p: パーツ p のある座標を求める。

解答

# NとQの値を入力から受け取る
n, q = map(int, input().split())

# ドラゴンの頭の初期位置を設定
head = [1, 0]
# 頭の位置を格納するリストを初期化
dragonHead = [(1, 0)]

# 各方向への移動を辞書で定義
C = {"R": (1, 0), "L": (-1, 0), "U": (0, 1), "D": (0, -1)}

# クエリ1の操作回数をカウントする変数
cnt = 0
# Q回のクエリを処理
for _ in range(q):
    a, b = input().split()
    # クエリ1の場合、ドラゴンの頭を移動
    if int(a) == 1:
        head[0] += C[b][0]
        head[1] += C[b][1]
        # 新しい頭の位置を追加
        dragonHead.append((head[0], head[1]))
        # 移動回数をインクリメント
        cnt += 1
    # クエリ2の場合、過去の位置を出力
    else:
        b = int(b)
        # 指定されたクエリが現在の移動回数を超えている場合
        if b > cnt:
            # 頭がまだ存在しない位置を出力
            print(*(b - cnt, 0))
        # 指定されたクエリが移動回数以内の場合
        else:
            # 過去の頭の位置を出力
            print(*dragonHead[cnt - b + 1])

解き方）

下記の考えを用いて問題を解きます。

龍の頭の位置を追跡：頭以外の部分は、頭が通ったルートを追跡する形になるため
移動回数が部位の番号より小さい時を例外として扱う(下図)

左図が０回移動。部位3は、(0, 3)、つまり（0, 3 – 0) => (0, 3)
右図が１回移動。部位3は、(0, 2)、つまり　(0, 3 – 1) => (0, 2)

n（グリッドのサイズ）と q（クエリの数）を入力から受け取ります。
龍の頭の初期位置として、グリッド上の点 (1, 0) を設定します。
各方向への移動を表す辞書 C を定義します。ここでは、「R」が右、「L」が左、「U」が上、「D」が下を意味します。
cnt（クエリタイプ1による動作の回数をカウントする変数）を0に初期化します。
q 回のクエリを処理するためのループを開始します。
各クエリのタイプ（a）とデータ（b）を入力から受け取ります。
クエリタイプ1の場合（a が1のとき）、辞書 C を使用してドラゴンの頭の位置を更新し、この新しい位置を dragonHead リストに追加します。
同時に cnt をインクリメントして、動作の回数を記録します。
クエリタイプ2の場合（a が2のとき）、指定された過去のクエリの位置を出力します。
- b が cnt より大きい場合、部位が龍の頭の位置まできていない状態のため (b-cnt, 0) を出力します。
- b が cnt 以下の場合、dragonHead リストから龍の過去の位置 cnt-b+1 を計算して出力します。