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

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 339

A問題：TLD

A – TLD

問題文

英小文字と . のみからなる文字列 S が与えられます。
S を . で分割したときの末尾の文字列を出力してください。
すなわち、. を含まない S の接尾辞のうち最長のものを出力してください。

解答

ANS=""  # 結果を格納する空文字列を初期化

# 入力された文字列を逆順に処理するためにreversedを使用し、リストに変換してからループ
for s in list(reversed(input())):
    if s != ".":  # 現在の文字が"."でなければ、ANSの前に追加
        ANS = s + ANS
    else:  # "."に達したらループを抜ける
        break
print(ANS)  # 結果を出力

考え方）

逆順で扱うことにより、途中のドットを考慮する必要がなくなります。

  1. 空文字列の初期化: 最初にANSという空の文字列を用意します。これは、最終的に出力される末尾の文字列を格納するために使用します。
  2. 入力文字列の逆順処理: 入力された文字列をinput()で受け取り、reversed()関数で逆順にします。これは、末尾の文字列を探すために、文字列の末尾から処理を開始するためです。
  3. ループによる文字処理: 逆順にした文字列を一文字ずつ処理します。このループ内で、各文字が”.”かどうかをチェックします。
  4. “.”が見つかるまでの文字列の結合: 現在の文字が”.”でない場合、その文字をANSの先頭に追加します。これにより、”.”に達するまでの文字列が逆順から正順に組み直されます。
  5. “.”に達したら終了: 文字が”.”である場合、ループから抜けます。これは、”.”を見つけた時点でそれより後ろ（元の文字列で言うと前）の文字列は必要ないためです。
  6. 結果の出力: 最後に、結合されたANSを出力します。これが問題で求められている、”.”で分割された末尾の文字列です。

B問題：Langton’s Takahashi

B – Langton’s Takahashi

問題(要約)

H行W列のトーラス状グリッド上で、初期状態として全てのマスが白で塗られている状況からスタートします。ここで、あるルールに従ってN回の操作を行った後のグリッドの状態を求める問題です。操作は、現在のマスが白なら黒に塗り替えて右回りに90度回転し1マス進む、黒なら白に塗り替えて左回りに90度回転し1マス進む、というものです。グリッドの端に達した場合は反対側に折り返します。

解答

# 入力を受け取る
h, w, n = map(int, input().split())

# グリッドを初期化（全てのマスを"."で表現）
grid = [["." for _ in range(w)] for _ in range(h)]

# 高橋君の初期位置と向きを設定
x, y = 0, 0  # (1,1)に対応するインデックスは(0,0)
direct = 0  # 向きを表す（0:上, 1:右, 2:下, 3:左）

# N回の操作を行う
for _ in range(n):
    if grid[y][x] == ".":  # 現在のマスが白の場合
        grid[y][x] = "#"  # 黒に塗り替え
        direct = (direct + 1) % 4  # 時計回りに90度回転
    else:  # 現在のマスが黒の場合
        grid[y][x] = "."  # 白に塗り替え
        direct = (direct - 1) % 4  # 反時計回りに90度回転

    # 向いている方向に応じて位置を更新
    if direct == 1:
        x = (x + 1) % w  # 右に進む
    elif direct == 2:
        y = (y + 1) % h  # 下に進む
    elif direct == 3:
        x = (x - 1) % w  # 左に進む
    else:
        y = (y - 1) % h  # 上に進む

# グリッドを出力
for g in grid:
    print("".join(g))

解き方）

グリッドが循環(トーラス状)になっているため、余りを用いたモジュロ演算を使ったラッピングを用いることにより、リストの範囲内を越えずに実装できます。

  1. 入力の受け取り: グリッドのサイズ(h行w列)と操作回数nを入力から受け取ります。
  2. グリッドの初期化: 最初に、h行w列のグリッドを作成し、全てのマスを白（”.”）で初期化します。
  3. 初期位置と向きの設定: 高橋君のスタート位置をグリッドの左上角（(0,0)）とし、上を向いている状態（direct = 0）から開始します。
  4. 操作の実行: 総回数n回の操作をループで実行します。各操作で現在のマスの色をチェックし、黒白を塗り替え、向きを変え、そして次のマスに進みます。
  5. 色の塗り替えと向きの変更: 現在のマスが白（”.”）なら黒（”#”）に塗り、時計回りに90度回転します。黒なら白に塗り、反時計回りに90度回転します。
  6. 位置の更新: 回転後の向きに応じて、高橋君の位置を更新します。トーラス状のグリッドなので、端に達した場合は反対側に折り返し(ラップアラウンド)します。
  7. グリッドの出力: 最終的なグリッドの状態を出力します。各行を文字列に結合して出力し、グリッドの各マスが最終的にどの色で塗られているかを表示します。

C問題：Perfect Bus

C – Perfect Bus

問題(要約)

バスがN回停車し、各停車で乗客がA人増えるか減る（Aが負の場合）ことが与えられます。乗客数は常に非負（0以上）でなければならないという条件のもと、与えられた情報に矛盾しない現在のバスの乗客数の最小値を求めます。

解答

n = int(input())  # 停車回数Nを入力
A = list(map(int, input().split()))  # 各停車での乗客数の変化をリストAに格納

ans = 0  # 現在の乗客数の最小値を保持する変数

for a in A:  # 各停車での乗客数の変化についてループ
    if ans + a < 0:  # もし現在の乗客数と変化量を足した結果が負になるなら
        ans = 0  # 乗客数を0にリセット（負の乗客数はありえないため）
    else:
        ans += a  # そうでなければ変化量を現在の乗客数に加算
print(ans)  # 最終的な乗客数の最小値を出力


解き方）

下記の考え方で解いていきます。

  • 乗客の数がどの時点でも負になることはない
  • 乗車順で考える

つまり、乗車順で考えたときに、負になる場合は、その人数分最初に乗っていたことになります。

  1. 入力の受け取り: 停車回数nと各停車時の乗客数の変化Aを入力から受け取ります。
  2. 乗客数の最小値の初期化: 現在の乗客数の最小値を表す変数ansを0に初期化します。
  3. 各停車時の処理: リストAの各要素（各停車時の乗客数の変化）についてループを行います。
  4. 乗客数の非負の保証: 乗客数が負になる場合は、その時点でansを0にリセットします。これにより乗客数が常に非負であることを保証します。
  5. 乗客数の更新: 乗客数が負にならない場合は、変化量aを現在の乗客数ansに加算します。
  6. 結果の出力: ループ終了後、ansには与えられた条件に矛盾しない現在の乗客数の最小値が格納されています。これを出力します。

感想

今回のコンテストではC問題まで解くことができましたが、B問題でかなり手こずり、結果的に良い順位を得ることはできませんでした。

A問題では、与えられた文字列から最後のドット以降を見つけ出す問題でした。ドットがいくつか途中に含まれているため、最初はどう進めば良いか少々迷いました。しかし、文字列を逆から読むというアプローチによって、この問題を解決することができました。

B問題に関しては、トーラス状のグリッド上での移動という、初めて聞く概念に戸惑いました。特に、「トーラス状」という言葉の意味を理解するのに時間がかかり、問題文の理解に苦戦しました。実装の際には、配列の範囲を超えたときの処理にも頭を悩ませましたが、復習を通じてモジュロ演算を利用することでスマートに解決できることを学びました。

C問題は、ループ処理を駆使することの重要性を問う内容でした。幸い、私はすぐに適切なアプローチを思いつくことができ、正解に辿り着けました。ループを活用して徐々に解答に近づけていくプロセスは、プログラミングの面白さを改めて感じさせてくれました。

2024年に入って以降は苦戦が続いており、順位も510位にまで下がってしまいました。しかし、今回B問題で学んだことを活かして、次回はもっと効率良く、正確に問題を解けるようになりたいです。

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

コメント

タイトルとURLをコピーしました