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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 350

A問題：Past ABCs

A – Past ABCs

問題文(要約)

与えられた6文字の文字列 S について、その形式は先頭3文字が「ABC」と固定され、末尾3文字が数字であることが保証されています。この文字列がAtCoderで以前に開催されたコンテストの略称（例：ABC001からABC349まで、ただしABC316を除く）であるかどうかを判断する問題です。

解答

# 入力された文字列の末尾3文字を数値に変換
num = int(input()[3:])

# 数値が316以外で、1から349の間にある場合は"Yes"を、それ以外は"No"を出力
print("Yes" if (num != 316) and (1 < num < 350) else "No")

考え方）

下記の考え方を用いて解いています。

初めの3文字は ABC で固定　・・・　無視できます
後ろの3文字は数字で固定　・・・　数字型として扱えます
受け取った数字が 316 でないことを確認
受け取った数字が 0 より大きく、349以下であることを確認

コード詳細

入力文字列の取得と処理： input()[3:] で入力された文字列の先頭3文字を除外し、残りの3文字（数字部分）を取得します。
数値変換： 取得した文字列を int 関数を用いて整数に変換し、num に格納します。
条件判断と出力： num が316ではなく、かつ1から349の間にある場合に “Yes” を出力します。それ以外の場合は “No” を出力します。この条件はPythonの論理演算を用いて簡潔に書かれており、and 演算子で2つの条件が同時に真であるかをチェックしています。

B問題：Dentist Aoki

B – Dentist Aoki

問題

高橋君には、穴 1,2,…,N に 1 本ずつ、全部で N 本の歯が生えています。
歯医者の青木君は、これらの歯と穴に対して、 Q 回の治療を行います。
i 回目の治療では、穴 Ti を治療します。治療内容は次の通りです。

穴 Ti に歯が生えている場合、穴 Ti から歯を抜く。
そうでない ( 穴 Ti に歯が生えていない) 場合、穴 Ti に歯を生やす。

全ての治療が終わった後、高橋君に生えている歯の本数は何本ですか?

解答

# 入力: 歯の本数 n と治療回数 q
n, q = map(int, input().split())
# 入力: Q回の治療が行われる歯の穴番号
T = list(map(int, input().split()))

# 歯の状態を管理するリストを初期化（1は歯があり、0は歯がない）
# 0番目は使わないため、0で初期化
Tooth = [0] + [1 for _ in range(n)]

# 治療を行う: 指定された穴に対して歯があれば抜き、なければ生やす
for t in T:
    if Tooth[t] == 1:
        Tooth[t] = 0  # 歯を抜く
    else:
        Tooth[t] = 1  # 歯を生やす

# 残った歯の本数を出力
print(sum(Tooth))

考え方）

下記の考え方で問題を解いています。

歯の状態を管理するリストを作成
歯の状態リストの０番目は０で初期化　・・・　入力の番号と揃えています
治療した歯に対して歯の状態リストを更新（０→１、１→０）
１になっている歯が残っている歯であるため、歯の状態リストを合計

コード詳細

入力の処理： n (歯の本数) と q (治療回数) を入力から受け取ります。その後、q回の治療で対象となる穴番号をリスト T に格納します。
初期状態の設定： Tooth リストを初期化します。このリストは各歯の有無を表し、初期状態では全ての穴に歯があるとします（1が歯があることを意味します）。リストの0番目は使用しません。
治療のシミュレーション： T で与えられた穴番号に対してループを行い、その穴に歯があるかどうかを Tooth リストでチェックします。歯があれば抜き（0に変更）、なければ生やします（1に変更）。
結果の出力： 最終的に Tooth リスト内の1の数を合計して、生えている歯の総数を計算し出力します。

C問題：Sort

C – Sort

問題

(1,2,…,N) の並び替えである数列 A=(A₁,…,A_N) が与えられます。
次の操作を 0 回以上 N−1 回以下行うことで、A を (1,2,…,N) にしてください。

操作：1 ≤ i < j ≤ N を満たす整数の組 (i, j) を自由に選ぶ。A の i 番目と j 番目の要素を入れ替える。

なお、制約の条件下で必ず A を (1,2,…,N) にできることが証明できます。

解答

n = int(input())  # 入力: 数列の長さ N
A = list(map(int, input().split()))  # 入力: 数列 A

ANS = []  # 操作記録を格納するリスト

# 数列の要素を正しい位置に移動
for i in range(n-1):
    # i 番目の要素が正しい位置になるまで操作
    while i+1 != A[i]:
        tmp = A[i] - 1
        A[i], A[tmp] = A[tmp], A[i]  # i 番目と tmp 番目の要素を交換
        ANS.append((i+1, tmp+1))  # 交換操作を記録

print(len(ANS))  # 操作の回数を出力
for ans in ANS:  # それぞれの操作を出力
    print(*ans)

ポイント）

与えられた数列 A は (1,2,…,N) の並び替えであり、特定の操作を使用してこの数列を昇順に並べ替える必要があります。操作では、数列の任意の二つの異なる位置 i と j (ただし 1 ≤ i < j ≤ N) の要素を入れ替えることができます。下記の考え方で解いていきます。

正しい位置を見つける：各要素 A[i] がどこにあるべきかは、その値自体によって決まります。例えば、要素の値が 5 ならば、それは配列の5番目に位置するべきです。これは A[i] の値から直接 i 位置を算出できることを意味します。
最小スワップでの解法：最小限のスワップで数列を並べ替えるには、各要素が正しい位置にあるかどうかを確認し、間違っている位置にある要素を正しい位置に移動させます。この過程を「サイクリック置換」と呼びます。
サイクリック置換の適用：サイクリック置換では、ある要素 A[i] が正しい位置にない場合、その要素を正しい位置に移動し、その位置にあった要素をまた適切な位置へ移動します。これを繰り返し行い、ある要素が最終的に正しい位置に来るまで続けます。

解き方(詳細)：

初期設定： 数列の長さ N と数列 A を入力から取得します。
操作の記録リストの作成： 交換操作を記録するためのリスト ANS を作成します。
数列の要素を適切な位置に移動： N−1 回のループを用いて、各要素が正しい位置にあるか確認します。位置が正しくない場合は、その要素が本来あるべき位置を計算し、要素を交換します。
交換操作の記録： 交換が行われるたびに、操作の詳細 (交換する二つの要素の位置) を ANS リストに追加します。
結果の出力： 全ての操作が完了した後、操作の総数と各操作の詳細を出力します。