こんにちは、こんぶちゃ(茶コーダー)です！
初心者視点から競プロAtCoderのABC326のA問題〜C問題の自身の解答と解答説明をしていきます。
- 競技プログラミング初心者で、問題の解き方がわからない方
- AtCoderの公式解説は読んだが、内容が理解できなかった方
- Pythonでの解法を知りたい方
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。
では早速行ってみましょう！
- 尺取法(Sliding Window) ・・・ 問題C
今回の参加コンテスト(ABC326)
A問題：2UP3DOWN
問題(要約)
高橋君が100階建てのビルにいます。彼は2階分までの上りまたは3階分までの下りであれば階段を使い、それ以外の場合はエレベーターを使います。高橋君がX階からY階への移動に使うのは階段ですか？階段の場合は、Yes を、エレベーターの場合は Noを出力してください。
解答
# 入力を受け取る
x, y = map(int, input().split())
# 階差が -3 以上 3未満の範囲にあるかを判定する
if -3 <= y - x < 3:
print('Yes') # 移動に階段を使う場合、'Yes'を出力
else:
print('No') # 移動にエレベーターを使う場合、'No'を出力解き方）
- 問題理解: 高橋君は2階分までの上りまたは3階分までの下りであれば階段を使い、それ以外の場合はエレベーターを使うことができます。
- 入力受け取り: ユーザーからX階とY階を受け取ります。
- 移動可能性の判定: 判定条件
-3 <= y - x < 3が成り立つ場合、つまりY階からX階への差が -3 以上 3 未満の場合、高橋君は階段を使って移動可能です。 - 結果の出力: 移動が可能な場合は’Yes’を出力し、そうでない場合は’No’を出力します。
B問題：326-like Numbers
問題(要約)
与えられた正整数N以上の範囲で、百の位の数と十の位の数の積が一の位の数と等しい「326-like number」と呼ばれる特定の条件を満たす最小の3桁の正整数を求める問題です。制約の範囲内では必ず解が存在します。
解答
# 入力を受け取る
n = int(input())
# 百の位の数と十の位の数の積が一の位の数と等しい326-like numberを探す
while int(str(n)[0]) * int(str(n)[1]) != int(str(n)[2]):
n += 1
# 最小の326-like numberを出力
print(n)以下詳細
- 入力受け取り: 最初にユーザーから整数
Nを受け取ります。これが与えられた条件以上の数である326-like numberを求める対象です。 - 条件の確認とループ:
whileループを使用して、与えられた条件（百の位の数と十の位の数の積が一の位の数と等しい）を満たすかどうかを確認します。str(n)[0]はnの百の位の数字を、str(n)[1]は十の位の数字を、str(n)[2]は一の位の数字を取得します。この3つの数字を使って条件を確認し、条件を満たさない場合はnを1つずつ増やして新しい数を試します。 - 条件が満たされたら出力: ループが条件を満たす最小の数を見つけたら、その数を出力します。
C問題：Peak
問題(要約)
数直線上にN個のプレゼントがあり、各プレゼントは座標Aiに置かれています。あなたは数直線上の長さMの半開区間[x, x+M)を選んで、その範囲内に含まれるプレゼントを全て獲得できます。具体的には、実数xを選び、プレゼントの座標がx以上かつx+M未満のものを獲得できます。最大で何個のプレゼントを獲得できるか？
解答
for文のネストをするとTLE(実行時間制限超過)になってしまうため、尺取法を用いて解いていきます。
# 入力を受け取る
n, m = map(int, input().split())
# プレゼントの座標を昇順にソート
A = sorted(list(map(int, input().split())))
# 尺取法で範囲内のプレゼント数を数える
left, right = 0, 1 # 左端と右端のポインタを初期化
max_cnt = 1 # 初期値は1つのプレゼントを選んだ場合
while right < n:
if A[right] - A[left] < m:
max_cnt = max(max_cnt, right - left + 1) # 最大のプレゼント数を更新
right += 1 # 右端を伸ばす
else:
left += 1 # 左端を右に移動
# 結果を出力
print(max_cnt)
- プレゼントの座標をソートする: 与えられたプレゼントの座標を昇順にソートします。これにより、数直線上のプレゼントの配置が整理されます。
- 尺取法の使用: 尺取法を使って、範囲内のプレゼント数を効率的に数えます。左端（left）と右端（right）の2つのポインタを使います。
- 範囲内のプレゼント数を数える: 右端を動かしながら、プレゼントの座標がM以下になる範囲を探します。範囲内のプレゼント数を数えながら、最大のプレゼント数を更新します。
- 範囲内のプレゼント数が最大の場合を保持: 尺取法を使って範囲内のプレゼント数を数え、その中で最大のプレゼント数を保持します。
- 結果を出力: 最大のプレゼント数を出力します。
感想
今週もC問題まで解けました！ラッキーな部分もありましたが、嬉しいです !^^!
B問題は、各桁を数字で扱いつつ、数字として扱ってインクリメントをする必要がありました。当初どのように扱うか悩みましたが、全体を文字列で扱い、各桁を取り出し、そこからまた数字に戻す方法を取りました。もっとすっきりとした回答があると思いますけど、型変換をすぐにできるようになった所は実力がついたと思います。
C問題は、初めはリストを昇順に並べ替え、for文のネストで解きましたが、TLE(実行時間制限超過)で不正解でした。尺取法を見つけて、実装してみたところAC(正解)を得ることができました。ウィンドウ枠をずらしていくイメージが湧きやすく、簡単な実装でしたので、次回も機会があればどんどん使っていきたいと思います。
Ratingも自身の最高点の555点になれたので、この勢いでレベルアップを図っていきたいと思います。
それでは、良い競プロライフを～！(*＾▽＾)／
コメント