【ABC309】競プロのA-C問題を40代サラリーマンがPython解説！初心者にもわかりやすく

abc309 AtCoder

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

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

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

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

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

今回使用している機能・アルゴリズム
  • defaultdict (コンテナデータ型、辞書のサブクラス)　・・・　問題C

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

AtCoder Beginner Contest 309

A問題：Nine

A – Nine

問題(要約)

1から９までの数字が書かれた 3 x 3 の盤面が与えられる。左上から右上、次の行・・・、右下の順。与えられた A, B が左右で隣接しているかを判断する。ただし A < B の関係が成り立つ

解答

# 番号1
a,b = map(int,input().split())

# 番号2
if a + 1 != b:
    exit(print("No"))

# 番号3
if a==3 or a==6:
    exit(print("No"))

# 番号4
print("Yes")

考え方 (下の番号は、コード内のコメント番号と連携している)

A < B の条件が成り立つため、隣り合う条件としては下記になる

  • A, Bが連番になっている
  • A がマス目の端にこない
    ただし、A<Bの関係から、Aが9をとることはない

上記の条件に当てはまる場合は、”No” を出力し、それ以外の場合は、”Yes” を出力する

以下、プログラム内容詳細

  1. 入力a, bを受け取る。map関数を用いて整数化している
  2. AとBの数が連番になっていないか確認、つまり、A+1 と B が等しくないかを確認する
    • 等しくない場合は、左右隣同士になることがないため、”No”を出力しプログラムを終了させる
  3. A がマス目の端に配置されているか確認、つまり、A が 3, 6 と等しいかを確認する
    • Aが3, 6 と等しい場合は、左右隣同士になることがないため、”No”を出力しプログラムを終了させる
  4. 途中でプログラムが終了しなければ、問題の条件を満たすため、”Yes”を出力させる

B問題：Rotate

B – Rotate

問題(要約)

N行N列のマス目が与えられる。マス目の外側に書かれた整数を時計回りに1個ずらした時のマス目を出力する

解答

# 番号1
n=int(input())
A=[list(input()) for _ in range(n)]

# 番号2
outers=[]

# 番号3
# 番号3-1
for j in range(n):
    outers.append(A[0][j])

# 番号3-2
for i in range(1,n):
    outers.append(A[i][n-1])

# 番号3-3
for j in range(n-2,-1,-1):
    outers.append(A[n-1][j])

# 番号3-4
for i in range(n-2,0,-1):
    outers.append(A[i][0])

# 番号4
shiftedOuters = [outers[-1]] + outers[:-1]

# 番号5
cnt=0

# 番号6
# 番号6-1
for j in range(n):
    A[0][j]=shiftedOuters[cnt]
    cnt+=1

# 番号6-2
for i in range(1,n):
    A[i][n-1]=shiftedOuters[cnt]
    cnt+=1

# 番号6-3
for j in range(n-2,-1,-1):
    A[n-1][j]=shiftedOuters[cnt]
    cnt+=1

# 番号6-4
for i in range(n-2,0,-1):
    A[i][0]=shiftedOuters[cnt]
    cnt+=1

# 番号7
for i in range(n):
    for j in range(n):
        print(A[i][j],end="")
    print()

考え方(下の番号は、コード内のコメント番号と連携している)

周囲の要素のみの配列を作成 -> 作成した配列を一つずらす -> 配列Aの周囲にずらした配列を適用する

  1. 入力 n, A を受け取る
    • nは整数型に変換する
    • Aは文字列のまま受け取り配列に変換する
      ＊ 数字としての意味がなく、文字列のままの方が計算されずに扱いやすい
      • 内包表記を用いて、N行分をリスト形式で取り込む
  2. 周囲の要素を格納しておく配列outersを用意する
  3. 周囲の要素を配列outersに格納していく。左上 -> 右上 -> 右下 -> 左下 -> 左上 の順番で登録していく
    1. 左上 -> 右上： 各要素をappendでoutersに格納してく
    2. 右上 -> 右下： A[0][n-1] の要素は 番号3-1 で格納済みなので、i は1〜始める
    3. 右下 -> 左下： A[n-1][n-1] の要素は 番号3-2 で格納済み。
      　　　　　　　j は n-2 から -1 ずつしていく必要がある
      　　　　　　 ＊ rangeの範囲に注意が必要。降順で0までの場合は、-1に設定する
    4. 左下 -> 左上：A[n-1][0] の要素は 番号3-3 で格納済み。
      　　　　　　 また、A[0][0] の要素は 番号3-1 で格納済み。
      　　　　　　 こちらもrangeの範囲に気をつけながら範囲を設定する
    5. 注意：P0 は、配列Dに含まれない場合なので、P0の場合は辞書型に登録しない
  4. outersの要素を1つ右にシフトし、shiftedOutersを作成する
    • スライサを用いて最後の要素を1番目、残りを後ろに組み合わせる
      ＊ 要素一つの場合は、配列でなくなるために [ ] をつけることにより、一つでも配列化する
      　 （配列同士の組み合わせを行うために行なっている）
  5. shiftedOutersの要素を一つずつ取り出すためのcnt変数を準備する
  6. 番号3で要素を抽出したが、今度は配列Aの各要素を上書きしていく。
    cntを +1 ずつする事により順番に取り出すことができる
    1. 左上 -> 右上
    2. 右上 -> 右下
    3. 右下 -> 左下
    4. 左下 -> 左上
  7. 番号6で配列A自身を更新できたため、更新した配列Aを出力していく
    • 要素間にスペースが入らないように、end=”” を用いている
    • 行毎に改行を入れるためにprint()を用いている

C問題：Medicine

C – Medicine

問題(要約)

N種類の薬が処方され、i 種類目の薬はai日間、毎日 bi 錠の薬を飲む必要がある。飲む薬の数が、K 錠以下になる非を求める

解答

# 番号1
from collections import defaultdict

# 番号2
drags=defaultdict(int)
total=0

# 番号3
n,k=map(int,input().split())
for _ in range(n):
    a,b=map(int,input().split())
    total+=b
    drags[a]+=b

# 番号4
if total <= k:
    exit(print(1))

# 番号5
for key,value in sorted(drags.items(), key=lambda x:x[0]):
    total -= value
    if total <= k:
        exit(print(key+1))

考え方(下の番号は、コード内のコメント番号と連携している)

１日目の錠数の数をだし、昇順にした日付毎に錠数を減らしていく。K錠以下になった日付を出力する

以下詳細

  1. 辞書型のdefaultdictをインポートする
  2. 日付と飲む錠数、飲む錠数の数を格納する変数を準備する
    • 変数dragsを辞書型で宣言する。日付aiをkey、錠数biをvalueとする
    • 錠数を記憶するためのtotalを準備する
  3. 入力を受け取る
    • n, k は整数型に変換する
    • for文を用いて a, b を受け取る
      • a, b を整数型に変換する
      • 錠数をtotalに加える事により、1日目の飲む錠数の数を求める
      • 変数dragsに日付と錠数を記憶させる
        • 同じ日付で複数の錠剤を飲む可能性もあるため、錠数は加算方式を採用する
  4. totalの数が k 錠以下の場合を判断する
    • これが成り立てば、1日目でK錠以下を達成しているため1を出力させる
  5. dragsに登録されている日付と錠数をfor文を用いて確認する
    • sorted関数を用いる事により、薬を飲み終わるのが早い順に並び替える
      • .items()を用いる事により、各項目のkey, valueを指定できるようにする
      • 並び替えのkeyにlambda関数を用いて、日付にアクセルをする
      • totalの数から飲み終わった錠数を減算する
      • 減算した値がk錠以下可動かを判断する
        • k錠以下の場合は、日付(カウンタ変数 key)を出力する
        • 飲んでいる錠数の最後の日が日付になるため、key + 1 を出力する

補足：辞書型のdictとdict.items()の違い

辞書型dictをdict.items()で用いる時の違いを下記でまとめてもらいました

違いdictdict.items()
概要辞書型オブジェクトを表すキーと値のペアを表す
返り値キーを使用して値にアクセスする(key, value) のタプルとしてキーと値のペアを返す
使用例my_dict['key']for key, value in my_dict.items():
必要な時値を直接取得する場合キーと値のペアを両方使う場合
ChatGPTにまとめてもらいました

感想

今週はリアルタイム参加ができず、別で各問題を解きました。 プレッシャーがない中ですが、C問題に今週も苦戦(´・ω・｀) あーでもない、こーでもない考えること半日（睡眠時間も入っています）、やっとAC解答に辿り着きました。リアルタイム参加では完全にタイムオーバーですね。とはいえ、自力で回答まで行けたことに満足しています。

最近はC問題で苦戦することが多いんですよね。たくさん問題を解いた方がいいんですけど、pythonでのvisualization(グラフ化)にはまってしまっています。グラフの連続処理などAtCoderで培ったアルゴリズムの考え方が生きてきます♪( ´▽｀)

その時に興味があることを全力で行いながら、AtCoderのコンテストはマイペースに続けていこうと思います。

それでは、良い競プロライフを〜！(*＾▽＾)／

コメント

タイトルとURLをコピーしました