こんにちは、こんぶちゃ(茶コーダー)です！
初心者視点から競プロAtCoderのABC357のA問題〜C問題の自身の解答と解答説明をしていきます。
- 競技プログラミング初心者で、問題の解き方がわからない方
- AtCoderの公式解説は読んだが、内容が理解できなかった方
- Pythonでの解法を知りたい方
まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。
では早速行ってみましょう！
今回の参加コンテスト(ABC357)
A問題：Sanitize Hands
問題文(要約)
宇宙人が順番に手を消毒します。各宇宙人はそれぞれ特定の数の手を持っており、すべての手を1回ずつ消毒したいと考えています。ボトルに入った消毒液でちょうどM本の手を消毒できるとき、何人目の宇宙人までがすべての手を消毒できるかを求めます。消毒液が不足している場合でも、消毒を始めた宇宙人はその分を使い切ります。
解答
n,m = map(int,input().split()) # nとmを入力から取得
H = list(map(int,input().split())) # 各宇宙人の手の数を入力からリストとして取得
for i in range(n): # 各宇宙人についてループ
m -= H[i] # 消毒液の量からその宇宙人の手の数を引く
if m < 0: # 消毒液が足りなくなったら
exit(print(i)) # その時点の宇宙人の番号を出力して終了
print(n) # すべての宇宙人が消毒できた場合はnを出力考え方）
下記の方針に従って解いていきます。
- 消毒液の量から宇宙人の手の数を引く
- 消毒液が足りなくなったら、その時点の宇宙人の番号を出力する
- 全ての宇宙人が消毒できた場合は、宇宙人の数 n を出力する
コード詳細
- 入力の取得:
- 最初に、宇宙人の人数 n と消毒液で消毒できる手の数 m を取得します。
- 次に、各宇宙人が持つ手の数 H をリストとして取得します。
- 消毒のシミュレーション:
- ループを使って各宇宙人について順番に処理します。
- 各宇宙人の手の数を m から引きます。
- 消毒液が足りなくなった場合の処理:
- 消毒液が足りなくなった場合（m < 0）、現在の宇宙人の番号を出力してプログラムを終了します。
- 全員が消毒できた場合の処理:
- すべての宇宙人が消毒できた場合、宇宙人の総数 n を出力します。
B問題：Uppercase and Lowercase
問題
英小文字と英大文字からなる文字列 S が与えられます。S の長さは奇数です。
S に含まれる大文字の個数が小文字の個数よりも多ければ、S に含まれる全ての小文字を大文字に変換してください。
そうでない場合は、S に含まれる全ての大文字を小文字に変換してください。
解答
S = input() # 文字列 S を入力から取得
upper, lower = 0, 0 # 大文字と小文字のカウンタを初期化
for s in S: # 文字列 S の各文字についてループ
if s.isupper(): # 文字が大文字かどうかをチェック
upper += 1 # 大文字カウンタを増加
else:
lower += 1 # 小文字カウンタを増加
# 大文字の数が小文字の数より多ければ全て大文字に変換、そうでなければ全て小文字に変換して出力
print(S.upper() if upper > lower else S.lower())考え方）
文字列を1文字ずつ大文字か小文字かを確認し、数が多い方に合わせて文字列Sを変換していきます。
コード詳細
- 入力の取得:
- 文字列 S を入力から取得します。
- カウンタの初期化:
- 大文字のカウンタ upper と小文字のカウンタ lower を0に初期化します。
- 文字の判定とカウント:
- 文字列 S の各文字について、ループで順に処理します。
- 文字が大文字なら upper を増加させ、小文字なら lower を増加させます。
- 条件に応じた変換:
- 大文字の数が小文字の数より多ければ、文字列 S の全ての文字を大文字に変換して出力します。
- そうでなければ、文字列 S の全ての文字を小文字に変換して出力します。
C問題：Sierpinski carpet
問題(要約)
カーペットのレベル K を次のように定義します。
• レベル 0 のカーペットは黒いマス # 1個のみからなる 1×1 のグリッドです。
• レベル K > 0 のカーペットは 3^K × 3^K のグリッドで、このグリッドを 3^(K-1) × 3^(K-1) のブロック 9 個に分割したとき、中央のブロックはすべて白いマス . からなります。その他の8個のブロックはレベル (K-1) のカーペットです。
非負整数 N が与えられたとき、レベル N のカーペットを出力します。
解答
def generate_carpet(lv):
if lv == 0: # レベル0のカーペットは黒いマス1個のみ
return ['#']
lower_carpet = generate_carpet(lv - 1) # レベル(lv-1)のカーペットを再帰的に生成
size = len(lower_carpet) # レベル(lv-1)のカーペットのサイズ
carpet = []
for row in lower_carpet: # 上部の3行分のカーペットを生成
carpet.append(row * 3)
for row in lower_carpet: # 中央の3行分のカーペットを生成（中央のブロックは白いマス）
carpet.append(row + '.' * size + row)
for row in lower_carpet: # 下部の3行分のカーペットを生成
carpet.append(row * 3)
return carpet
n = int(input()) # レベルNを入力から取得
carpet = generate_carpet(n) # レベルNのカーペットを生成
for row in carpet: # カーペットを出力
print(row)解き方）
作成したいカーペットの構成：
- マス目を９分割
- 中央のブロックが白いマス
- 他のブロックが一つ下のレベル
このブロックの中身：- マス目を９分割
- 中央のブロックが白いマス
- 他のブロックが一つ下のレベル
上記のように同じ構成が繰り返されています。そのため、再帰を用いて解いていきます。ポイントになる部分は：
- レベル０の時は、黒いマス・・・再帰の下限条件
- ３つの行（上部・中央・下部）に分けてカーペットを作成
解き方(詳細)：
- カーペットの生成関数の定義:
- 関数 generate_carpet を定義し、レベル lv のカーペットを生成します。
- ベースケースの処理:
- lv が 0 の場合、黒いマス # のみからなる 1×1 のグリッドを返します。
- 再帰的なカーペットの生成:
- lv が 0 でない場合、レベル lv-1 のカーペットを再帰的に生成します。
- カーペットの組み立て:
- レベル lv-1 のカーペットを使って、上部、中央部、下部の3つの部分に分けて新しいカーペットを構築します。
- 上部と下部はレベル lv-1 のカーペットを3倍に繰り返します。
- 中央部は中央のブロックを白いマス . に置き換え、左右にレベル lv-1 のカーペットを配置します。
- 入力の取得とカーペットの生成:
- ユーザーからレベル N を入力として取得し、レベル N のカーペットを生成します。
- カーペットの出力:
- 生成したカーペットの各行を順に出力します。
感想
今回はB問題までしか解けませんでした。
A問題は、宇宙人の手をどこまで消毒できるかの問題であり、特定条件までの順番を探すものでした。for文とif文を用いて特定条件の位置を探すことで解決できました。
B問題は、大文字と小文字の判断と大文字/小文字変換の問題でした。isupper()やislower()関数を用いることで、文字を一つずつ確認し、数が多い方に合わせて元の文字列を大文字または小文字に変換することで解決できました。この問題は、関数を知っていればすぐに解ける問題でした。
C問題は再帰を扱う問題でした。問題の構成上、再帰を用いることはすぐにわかったのですが、自身で実装することができませんでした。2次元リストで扱おうと考えましたが、再帰的に仕組みを作れず断念しました。回答などを参考にして、最終的にはcarpetのリストを1次元で扱い、上部・中央・下部に分け、下位カーペットを繰り返して解決できました。
今回はオンタイムで参加できず、レーティングは変わりませんでしたが、C問題は歯が立ちませんでした。今回、復習も兼ねて数回解いて再帰のやり方が再理解できたので、次回の再帰問題は解けるようになりたいと思います。
皆さんも競技プログラミングを楽しんでくださいね！(*＾▽＾)／
コメント