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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 318

A問題：Full Moon

A – Full Moon

問題(要約)

高橋くんは満月が好きで、今日からN日までの期間内で、M日ごとに満月を見ることができるとき、彼が満月を見られる日の総数を求めてください。

解答

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

# 満月を見られる日の数を計算
result = (n - m) // p + 1

# 結果を出力
print(result)

input()関数を使用して、スペースで区切られた整数を受け取ります。それぞれ、nは日数の上限、mは最初の満月が見られる日、pは満月を見る間隔を表します。
(n - m) // pを計算します。これは、高橋くんが最初の満月を見た日（m日目）から始めて、満月を見るたびにp日ずつ経過する間隔で、n日までの期間内に満月を見る回数を計算しています。この部分は高橋くんが満月を見る回数です。
計算結果に1を加えて、高橋くんが満月を見る日の総数を計算します。最初の満月を見た日を含むため、+1が行われています。
最終的な結果をprint()関数を使って出力します。

B問題：Overlapping sheets

B – Overlapping sheets

問題(要約)

座標平面上にN枚の長方形のシートがあり、各シートはx軸およびy軸に平行な長方形領域を覆っています。1枚以上のシートによって覆われている領域の面積Sは、与えられた下記条件下で整数であることが証明されています。整数となるSを求めてください。

各シートが覆う長方形領域の各辺はx軸またはy軸に平行
i枚目のシートはちょうどAi≤x≤BiかつCi≤y≤Diを満たす領域を覆う

解答

# シートの数を入力
n = int(input())

# 座標平面を表す2次元リストmpを初期化
mp = [[0 for _ in range(101)] for _ in range(101)]

# 各シートの情報を処理
for _ in range(n):
    a, b, c, d = map(int, input().split())
    
    # シートの覆う範囲を2次元リストmpに1でマークする
    for i in range(c, d):
        for j in range(a, b):
            mp[i][j] = 1

# シートに覆われている領域の面積を計算
ans = 0
for r in mp:
    ans += sum(r)

# 結果を出力
print(ans)

以下詳細

最初にシートの数（n）を受け取ります。
座標平面を表す2次元リストmpを初期化します。この2次元リストの要素は0で初期化され、各セルは座標平面上の1つの点を表します。リストのサイズは101×101で、座標平面が0から100の範囲で設定しています（A, B, C, Dの制限より）。
各シートの情報（a, b, c, d）を処理します。各シートは、座標平面上の長方形領域を指定します。この領域内のセルを1でマークして、その領域がシートに覆われていることを示します。
シートに覆われている領域の面積を計算するため、2次元リストmp内の1の合計を求めます。これが答えとなり、ansに格納されます。
最後にansを出力して、覆われている領域の面積を表示します。

C問題：Blue Spring

C – Blue Spring

問題(要約)

高橋君はN日間の鉄道旅行を計画しており、各日に運賃の通常料金を支払うか、1日周遊パスを使用するかを選べます。各日の通常料金（F_i円）と、1日周遊パスのセット（D枚でP円）が与えられます。最小の費用でN日間の旅行をするために必要なお金を求めてください。

解答

考え方）

通常の運賃料金を降順にソートし、D日分を1日周遊パスで置き換えた場合を求め、whileを用いて最小の費用を見つけています。

# 入力を受け取る
n, d, p = map(int, input().split())
F = sorted(list(map(int, input().split())), reverse=True)

# 通常料金を降順にソートし、初期の合計金額を計算
ans = sum(F)
tmp = sum(F)
cnt = 1

# パスを購入するかどうかのループ
while ans >= tmp:
    ans = tmp
    # パスを購入して通常料金を減算し、新しい合計金額を計算
    tmp = tmp - sum(F[(cnt-1)*d:cnt*d]) + p
    cnt += 1

# 最小の費用を出力
print(ans)

以下詳細

最初に、鉄道旅行の日数（n）、1日周遊パスのセットに含まれる日数（d）、1日周遊パスの価格（p）を受け取ります。
通常の運賃料金（F_i円）をリストFに受け取り、降順にソートします（大きい順に並べます）。ソートすることで、通常の運賃を高い順に利用することを想定しています。
ans変数に通常の運賃料金の合計を設定し、tmp変数にも同じ値を設定します。また、cnt変数を初期化します。
whileループは、ans（現在の最小費用）がtmp（新しい費用）より大きい場合に続きます。この条件が満たされる間、パスを購入するかどうかを判定し続けます。
ループ内で、ansをtmpにコピーし、tmpから現在のパスを使用して通常の運賃料金を差し引き、新しい合計金額を計算します。その後、cntをインクリメント（１を加算）します。
ループが終了すると、最小の費用（ans）が計算され、それが出力されます。