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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 341

A問題：Print 341

A – Print 341

問題文

正整数 N が与えられるので、 N 個の 0 と N+1 個の 1 からなる、0 と 1 が交互に並んだ文字列を出力してください。

解答

# 入力されたNに対して、"10"をN回繰り返し、最後に"1"を加えて出力
print("10" * int(input()) + "1")

考え方）

シンプルに “10” をN回繰り返すことにより解くことができます。最後に “1” を加え忘れることに注意。

int(input())でユーザーから入力された正整数Nを受け取ります。
"10"をNN回繰り返します。これにより、0と1が交互にN回並んだ文字列ができます。この時点で、0はNN個、1はN個です。
最後に+ "1"で文字列の末尾に1を追加します。これで1がN+1個になります。
この結果作成された文字列をprint関数を使って出力します。

B問題：B – Foreign Exchange

B – Foreign Exchange

問題(要約)

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

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

解答

n = int(input())  # 国の数Nを入力
A = list(map(int, input().split()))  # 各国の通貨の初期値

S, T = [], []  # Sは交換に必要な通貨の単位、Tは交換後に得られる通貨の単位

for _ in range(n-1):
    s, t = map(int, input().split())  # SとTの値を入力
    S.append(s)
    T.append(t)

for i in range(n-1):
    m = A[i] // S[i]  # 国iの通貨をS[i]単位で何回交換できるか
    A[i] -= S[i] * m  # 国iの通貨を交換に使用
    A[i+1] += T[i] * m  # 国i+1の通貨を交換で獲得

print(A[-1])  # 国Nの通貨の最終的な値を出力

解き方）

国iの通貨は、国i+1の通貨に変換できるため、各国の通貨において持っている通貨の最大変換を考えることにより、最終的に国N の通貨が最大になります。

国の数と各国の通貨の初期値を入力します。
交換レート（SとT）を入力し、リストに保存します。
各国に対して、可能な限り通貨を隣の国の通貨と交換します。交換は、自国の通貨がS[i]以上ある場合にのみ可能です。
国iから国i+1への通貨交換を繰り返し、最終的に国Nの通貨が最大になるようにします。
最終的な国Nの通貨の単位数を出力します。

C問題：Divide and Divide

C – Divide and Divide

問題(要約)

H行W列のグリッドがあり、各マスは陸(.)または海(#)です。グリッドの外周は全て海です。高橋君が宇宙船で不時着し、特定の手順(T文字列)に従ってN回移動しました。移動経路上のマスはすべて陸です。高橋君が現在いる可能性のあるマスの数を求めます。

解答

h, w, n = map(int, input().split())  # グリッドのサイズと移動回数を入力
T = input()  # 移動手順を入力
grid = [input() for _ in range(h)]  # グリッドの状態を入力

direction = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}  # 移動方向の定義

x, y = 0, 0  # 現在位置の初期化
minX, maxX = 0, 0  # x軸の移動範囲の初期化
minY, maxY = 0, 0  # y軸の移動範囲の初期化

for t in T:
    dy, dx = direction[t]  # 移動方向を取得
    y += dy  # y軸方向の移動
    x += dx  # x軸方向の移動
    minY = min(minY, y)  # y軸の最小移動範囲を更新
    maxY = max(maxY, y)  # y軸の最大移動範囲を更新
    minX = min(minX, x)  # x軸の最小移動範囲を更新
    maxX = max(maxX, x)  # x軸の最大移動範囲を更新

ans = 0  # 答えの初期化
for i in range(1 - minY, h - maxY):
    for j in range(1 - minX, w - maxX):
        if grid[i][j] != "#":  # 陸であるマスのみ検討
            y, x = i, j
            for t in T:
                dy, dx = direction[t]
                y += dy
                x += dx
                if grid[y][x] == "#":
                    break  # 海に当たったら中断
            else:
                ans += 1  # 移動経路が全て陸であればカウントアップ
print(ans)  # 結果の出力

解き方）

基本的な考え方は、全検索(下記)です。