こんにちは、こんぶちゃ(茶コーダー)です！
初心者視点から競プロAtCoderのABC354のA問題〜C問題の自身の解答と解答説明をしていきます。
- 競技プログラミング初心者で、問題の解き方がわからない方
- AtCoderの公式解説は読んだが、内容が理解できなかった方
- Pythonでの解法を知りたい方
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。
では早速行ってみましょう！
今回の参加コンテスト(ABC354)
A問題：Exponential Plant
問題文
高橋君は植物を育てています。その植物の発芽時の高さは 0cm です。発芽した日を 0 日目としたとき、発芽してから i(0 ≤ i) 日目の夜には 2icm 植物の高さが伸びます。
高橋君の身長は Hcm です。
高橋君は毎朝この植物と背比べをします。植物の高さが高橋君の身長より高くなるのは発芽から何日目の朝か求めてください。
解答
h = int(input()) # 高橋君の身長Hを入力
i = 0 # 日数をカウントするための変数
plant = 0 # 植物の高さを初期化
while plant + 2**i <= h: # 植物の高さが高橋君の身長以下である限り繰り返す
plant += 2**i # 植物の高さに2^iを加算
i += 1 # 日数を1増加
print(i + 1) # 植物が高橋君の身長を超えるのはi+1日目の朝考え方）
日数と植物の高さを示す変数を定義し、日数カウントをしつつ植物の高さを更新していきます。
コード詳細
- 初期化: 高橋君の身長をhとして入力し、日数をカウントする変数iと植物の高さを示す変数plantを初期化します。
- ループ開始: 植物の高さが高橋君の身長を超えるまでループを続けます。
- 高さの更新: 各日ごとに植物の高さに2のi乗を加えます。
- 日数の更新: 日数カウンターiを1増やします。
- 結果出力: ループが終了した時点で、植物が高橋君の身長を超えた日数（i + 1）を出力します。
B問題：AtCoder Janken 2
問題（要約）
N 人の AtCoder ユーザーが集まり、 AtCoderじゃんけん2 を行います。i 人目のユーザー名は Si 、レートは Ci です。
AtCoderじゃんけん2 は以下の手順で行われます。
- それぞれのユーザーに、ユーザー名の辞書順に 0,1,…,N−1 の番号を割り当てる。
- N 人のレートの総和を T とする。番号 T mod N を割り当てられたユーザーが勝者となる。
勝者のユーザー名を出力してください。
解答
n = int(input()) # ユーザー数Nを入力
S = [] # ユーザー名のリスト
total = 0 # レートの総和を初期化
for _ in range(n): # N人のユーザーについて
s, c = input().split() # ユーザー名とレートを入力
S.append(s) # ユーザー名をリストに追加
total += int(c) # レートを総和に加算
print(sorted(S)[total % n]) # ユーザー名を辞書順に並べ、勝者のユーザー名を出力考え方）
下記のポイントを抑えて解いていきます：
- N人のレートの総和を求める
- 辞書順のユーザー名のリストを作成する
- 辞書順のユーザー名から T mod N 番目を出力する
コード詳細
- 初期化: ユーザー数Nを入力し、ユーザー名のリストSとレートの総和を保持する変数totalを初期化します。
- 入力処理: 各ユーザーの名前SとレートCを入力し、ユーザー名をリストSに追加、レートをtotalに加算します。
- 辞書順にソート: ユーザー名リストSを辞書順にソートします。
- 勝者の決定: レートの総和totalをユーザー数Nで割った余りをインデックスとして、勝者のユーザー名を出力します。
C問題：AtCoder Magics
問題 (要約)
高橋くんはN枚のカードを持っています。各カードには強さとコストがあります。強さが高くコストが低いカードであれば、強さが低くコストが高いカードを捨てます。この操作をできなくなるまで繰り返した後、残るカードの集合を求めます。
解答
n = int(input()) # カードの枚数Nを入力
cards = {} # カードの強さとコストをキーとする辞書
for i in range(n): # 各カードについて
a, c = map(int, input().split()) # 強さaとコストcを入力
cards[(a, c)] = i + 1 # カードの強さとコストをキーに、カードの番号を値にする辞書を作成
sortedCards = sorted(cards) # カードを強さとコストでソート
minCs = [float('inf')] * n # 各位置の最小コストを保持するリストを初期化
minC = float('inf') # 最小コストを無限大で初期化
# 後ろから順に、最小コストを更新
for i in range(n - 1, -1, -1):
minC = min(minC, sortedCards[i][1])
minCs[i] = minC
ans = [] # 捨てられなかったカードのリスト
# 各カードについて、最小コストと比較
for i in range(n):
if sortedCards[i][1] <= minCs[i]:
ans.append(cards[sortedCards[i]]) # カード番号を追加
print(len(ans)) # 残ったカードの枚数を出力
print(*sorted(ans)) # 残ったカードの番号をソートして出力解き方）
強さとコストの二つのパラメータを比較する必要があります。特定のパラメータ（例えば強さ）で昇順に並び替えた後、もう一つのパラメータ（コスト）を比較していく必要があります。二重のfor文で実装すると制限時間を超過するため、強さ昇順におけるコストの最小値を効率的に求めます。
コストの最小値は、強さ昇順に並び替えたリストを逆順に走査しながら、その時点までのコストの最小値を記録することで求めることができます。
この方法により、実行時間をO(3N)で解くことができます。
解き方(詳細)：
- 初期化: カードの枚数Nを入力し、カードの強さとコストを保持する辞書cardsを作成します。
- 入力処理: 各カードの強さaとコストcを入力し、それをキーとしてカードの番号を値に持つ辞書を作成します。
- ソート: カードを強さとコストでソートしたリストsortedCardsを作成します。
- 最小コストの更新: 後ろから順に見ていき、現在位置までの最小コストを保持するリストminCsを更新します。
- 捨てるカードの判定: 各カードについて、そのコストが現在位置までの最小コスト以下である場合、カードの番号をリストansに追加します。
- 出力: 残ったカードの枚数と番号をソートして出力します。
感想
今回はC問題まで解けました^^
A問題は、植物の高さと身長を比較する問題でした。植物の高さが2のi乗ずつ増えるため、while文を用いて日数を増やしつつ植物の高さを増加させることで解決できました。
B問題は、ユーザー名を辞書順に並べ、その中で特定の順番にあるユーザー名を求める問題でした。問題文の理解に少し手間取りましたが、ユーザー名を辞書順に並び替え、T mod N 番目のユーザー名を出力することで解決できました。
C問題は、強さとコストの二つのパラメータを考慮する問題でした。最初は強さ順に並び替えたパラメータを用いてコストを全検索しましたが、実行時間超過で不正解でした。効率的な方法を考え、強さ順におけるコストの最小値のリストを用いることで効率的に解決できました。試験時間内に回答に辿り着けたことに非常に満足です。
今回C問題まで解けたことで、レーティングが少し上がり558になりました。過去の最高レーティング566に近づいてきたので、この勢いで自身の最高レーティングを更新できるように頑張ります。
皆さんも競技プログラミングを楽しんでくださいね！(*＾▽＾)／
コメント