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

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

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

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

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

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

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

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

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

AtCoder Beginner Contest 334

A問題：Christmas Present

A – Christmas Present

問題文

野球少年の高橋君は今年とても良い子にしていたので、サンタさんはバットかグローブのうち値段が高い方を高橋君にプレゼントすることにしました。

バットの値段が B 円、グローブの値段が G 円 (B ≠ G) のとき、サンタさんが高橋君にプレゼントするのはどちらですか？

解答

# ユーザーからバットとグローブの価格を入力として受け取る
b, g = map(int, input().split())

# if文をprint文の中にまとめて記載
print("Bat" if b > g else "Glove")

解き方）

通常のif文を用いて条件毎分岐をさせることもできますが、print文に組み込むことですっきりとした回答が作れます。

b, g = map(int, input().split()):
- この行はユーザーからの入力を受け取ります。ユーザーが空白で区切られた2つの数値を入力すると、input().split() がそれを文字列のリストに分割します。例えば、”300 500″という入力があった場合、split() によって ["300", "500"] というリストに変換されます。
- map(int, ...) 部分は、そのリストの各要素を整数に変換します。この例では、文字列のリスト ["300", "500"] が整数のリスト [300, 500] に変換されます。
- b, g にこのリストをアンパックして代入することで、バットの価格 b とグローブの価格 g が得られます。
print("Bat" if b > g else "Glove"):
- この行は、Pythonの条件式（三項演算子）を使用しています。条件式は 真偽値を評価する式 if 条件 else 別の式 という形式で、条件が True の場合は最初の式が、False の場合は else の後の式が評価されます。
- ここでの条件 b > g は、バットの価格 b がグローブの価格 g より高いかどうかをチェックします。
- 条件が True（バットの価格がグローブの価格より高い）なら “Bat” が出力され、False（バットの価格がグローブの価格以下）なら “Glove” が出力されます。

B問題：Christmas Trees

B – Christmas Trees

問題

東西に無限に伸びる道路があり、この道路上のある基準となる地点から東に xm のところにある地点の座標は x と定められています。特に、基準となる地点から西に xm のところにある地点の座標は −x です。

すぬけ君は今から、座標が A である地点を基点にして Mm おきにクリスマスツリーを立てます。すなわち、座標がある整数 k を用いて A+kM と表されるような地点それぞれにクリスマスツリーを立てます。

高橋君と青木君はそれぞれ座標が L,R (L≤R) である地点に立っています。高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を求めてください。

解答

# 整数 A, M, L, R をユーザーから入力として受け取る
a, m, l, r = map(int, input().split())

print((r-a)//m - (l-1-a)//m)

解き方）

ポイントは、「Lの位置にあるツリーも含めるか」という点です。

青木君の位置Rに関して: 「Rから基準点までの距離をMで割った数」は、基準点からRまでにあるツリーの本数を示します。この計算では、Rの位置にあるツリーも含まれます。
高橋君の位置Lに関して: 一方で、「Lから基準点までの距離をMで割った数」だけでは、Lの位置にあるツリーを含めることができません。なぜなら、この計算では「Lの位置よりも1つ前」までのツリーの本数になってしまうからです。だから、高橋君が立っているLの位置にもツリーがある場合、それを含めるために「L-1」を使って計算します。

L-1の部分に対して、簡単な例で考えます。

例）基準点から東に5mごとにクリスマスツリーを立てるとします。つまり、M（ツリーを立てる間隔）は5mです。そして、高橋君が座標10に、青木君が座標20に立っているとします。

ここで、高橋君と青木君の間にあるツリーの本数を数えたいと思います。基準点からの距離を5で割ると、ツリーがどこにあるかがわかります。

青木君の位置（R = 20）にあるツリーを数える: 青木君は座標20に立っています。20を5で割ると4になります。つまり、基準点から青木君の立っている位置までには、4本のツリーがあります（座標0, 5, 10, 15, 20）。
高橋君の位置（L = 10）にあるツリーを数える: 高橋君は座標10に立っていますが、10を5で割るだけでは、座標10にあるツリーはカウントされません。なので、L-1、つまり9を5で割ります。9を5で割ると1になります。これは基準点から高橋君の立っている位置のちょっと前（座標9）までのツリーの本数です。

では、この2つの結果を使って、高橋君と青木君の間にあるツリーの本数を計算します。

青木君の位置までのツリーの本数（4）から、高橋君の位置のちょっと前までのツリーの本数（1）を引きます。つまり、4 – 1 = 3。これが高橋君と青木君の間にあるツリーの本数です。実際に数えてみると、座標10, 15, 20にツリーがありますね。

C問題：Socks 2

C – Socks 2

問題(要約)

高橋君はN組の靴下を持っており、それぞれの組は異なる色のペアです。彼はいくつかの靴下（K枚）を失くしてしまい、残った靴下で新しいペアを作りたいと思っています。新しいペアを作る際、靴下の色が異なるほど「奇妙さ」が増し、この奇妙さの総和を最小にしたいです。問題は、靴下を最適にペアリングしたときの奇妙さの総和の最小値を求めることです。

解答

# itertoolsからaccumulateをインポートし、累積和の計算に使用
from itertools import accumulate

# 標準入力から数列の長さnと問題の条件Kを読み込む
n, k = map(int, input().split())
# 標準入力から数列Aを読み込む
A = list(map(int, input().split()))

# 前半部の差分を格納するリストを初期化
pre = [0] * (k // 2)
# 後半部の差分を格納するリストを初期化
suf = [0] * (k // 2)

# 数列Aの偶数インデックスについて差分を計算し、preとsufリストに格納
i = 0
while i // 2 < k // 2:
    pre[i // 2] = A[i + 1] - A[i]  # 前半の差分を計算
    suf[-i // 2 - 1] = A[-i - 1] - A[-i - 2]  # 後半の差分を計算
    i += 2

# preリストの累積和を計算し、端に0を加えて初期値と最終値を追加
cumulative_pre = [0] + list(accumulate(pre)) + [0]
# sufリストの累積和を計算し、逆順にしてから累積和を取り、再度逆順に戻す
_cumulative_suf = list(accumulate(reversed(suf)))
cumulative_suf = [0] + list(reversed(_cumulative_suf)) + [0]

# 最小の奇妙さを格納するための変数を無限大で初期化
ans = float('inf')
# 全ての偶数インデックスについて最小の奇妙さを探索
i = 0
while i < k:
    # 累積和を使い、前半と後半の和の最小値をansに格納
    ans = min(ans, cumulative_pre[i // 2] + cumulative_suf[i // 2 + 1])
    i += 2
# 計算した最小の奇妙さを出力
print(ans)

解き方）

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

ペアになっている靴下を考えない: もし靴下がちょうどペアになっているなら、その部分については考える必要がありません。なぜなら、既にペアになっている靴下は奇妙さを増やすことがないためです。
余る靴下をどうするか: 靴下の総数が奇数の場合、1足だけ余ってしまいます。この余った靴下をどのペアから取り除くかによって、奇妙さが変わります。
偶数の位置にある靴下に注目: 靴下の番号が偶数の場所だけ見ていきます。なぜなら、奇数の位置にある靴下を除外した場合、残った靴下で作るペアの奇妙さが小さくなるからです。
全ての組み合わせで奇妙さを計算: 前半と後半の靴下を使って、全ての組み合わせで奇妙さを計算します。そして、もっとも小さな奇妙さが答えになります。
累積和を使う: 累積和とは、ある点までの靴下のペアの差分を全部足したものです。これを使うことで、どの靴下を余らせると奇妙さが最小になるかを簡単に計算できます。

コードの詳細の考え方は以下になります。

入力の取得: 数列の長さnと数kを読み取り、次に数列Aの各要素を読み取ります。
前処理: preとsufという2つのリストを用意します。これらは、数列の前半と後半の各要素間の差（隣接する要素の差）を格納するためのものです。
差分の計算: whileループを用いて、数列Aの要素についてペアの差分を計算します。preは前半部分、sufは後半部分の差分を保持します。ここでは偶数インデックスのみを考慮しています。
累積和の計算: accumulate関数を使ってpreとsufの累積和を計算し、新しいリストcumulative_preとcumulative_sufに格納します。これにより、任意の区間の和を効率的に計算できるようになります。
最小奇妙さの計算: 初期値として無限大をansに設定し、whileループを使って可能なすべての位置で奇妙さの最小値を探索します。ここでは、前半の累積和と後半の累積和を足し合わせることで、ある要素をペアから除外した場合の奇妙さを計算しています。
結果の出力: 最小値として計算されたansを出力します。