(ABC292)A-C問題のpythonでの解法

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

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

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

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

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

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

今回使用した機能・アルゴリズム

英小文字→大文字化　・・・　A問題
約数列挙　　　　　　・・・　C問題

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

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

AtCoder Beginner Contest 292

A問題：CAPS LOCK

A – CAPS LOCK

問題(要約)

英小文字列が与えられ、英大文字列に変換する。

解答

print(input().upper())

考え方

input()で入力を受け取る
upper()で大文字に変換
print()で大文字変換したものを出力

1行で処理するとPythonっぽくてかっこいい。

B問題：Yellow and Red Card

B – Yellow and Red Card

問題(要約)

N人のサッカー選手が試合をし、反則に応じてイエローカードかレッドカードが提示される。選手xが退場処分を受けたかどうかを回答する。

退場の条件

イエローカードを２回掲示される
レッドカードを掲示される

解答

# 入力 n,q を受け取る。
# input()で入力"n q"受け取り、split()でスペース区切りに分割(リスト化)
# map関数を用いて、リスト化しているそれぞれの値を整数(int)型に変換(キャスト)
# 右辺は2つの値が出てくるため、n,q の二つの変数を準備しておき、それぞれに代入
n,q=map(int,input().split())

# 下記参照
player = [0] * (n+1)

for _ in range(q):
    e, x = map(int,input().split())
    if e==1:
        player[x]+=1
    elif e==2:
        player[x]+=2
    else:
        if player[x]>=2:
            print("Yes")
        else:
            print("No")

考え方

各プレイヤーの累積カード枚数を記録するための配列を準備する
＊入力される選手番号が1始まりのため、n+1の配列を準備(0番目は使わない)
for文をイベント回数分繰り返す(q回)
毎回2つの数字が入力されるため、e, x で入力を受け取る
eの条件により条件分岐を行う
- e=1の時、選手x番の配列に1をたす(イエローカード)
- e=2の時、選手x番の配列に2をたす(レッドカード)
- その他(e=3)の時、選手x番の配列の数字により下記2つの条件に分ける
  - 選手x番の配列が2以上なら退場しているため、”Yes”を表示
  - 選手x番の配列が2未満なら退場していなため、”No”を表示

C問題：Four Variables

C – Four Variables

問題(要約)

正数の組(A, B, C, D)であって、AB + CD = N を満たすものの個数を求める

解答

# 約数を高速で列挙する関数を定義
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# 上記は自作関数の定義になるため、コードとしてはここから
# 整数nの入力を受け取る
n=int(input())
# 回答の組み合わせを数え上げるためcntを定義(0で初期化)
cnt = 0

# 下記参照
for ab in range(1,n):
    cd = n - ab
    cnt += len(make_divisors(ab)) * len(make_divisors(cd))

print(cnt)

考え方

A, B, C, D が正数であることから、abの取りうる範囲は1〜 n-1までの範囲となる
また、ab + cd = n であることから、cd = n – ab となり、取りうる範囲は n-1 〜 1 までとなる
全ての組み合わせを確かめる為に、for文をabの取りうる範囲の1〜 n-1にセットする
A * B => ab の取りうる組み合わせを求める。つまり、abの約数の数を求める。
- 自作関数(make_divisors)にabを渡すことにより、abの約数の配列を返す(*1)
- abの約数の数の配列の長さをlenで数えることにより、abの取りうる組み合わせがわかる
C * D => cdに関しても上記abと同様に求める
abの通り数 * cdの通り数により、想定される通り数を求め、cntに足していく
for文でabの値を順次増やしていくことにより、全パターンを確認する

*1 自作関数 make_divisiors(n) に関して以下のページを参考にしています。

　関数 make_divisors(n)：約数を高速で列挙するコード(Python)

# 約数を高速で列挙する関数を定義
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

考え方

約数は、ある数(n)を割り切れる整数であるため、nを1から順番に割れるかを確認していく
1. 約数は常に対の形になるため下側(ここでは割る方：lower_divisors)、上側(ここでは右辺：upper_divisors)を保存する配列を準備する
  (例：6の約数は、1, 2, 3, 6。計算上は、6 ÷ 1 = 6, 6 ÷ 2 = 3 になる)
2. while文で i * i ( iの２乗)、つまりnの半分のところまで下記を繰り返す
  - n が i で割り切れたら( n % i == 0)、下側配列に i を追加する
    - i が n で割った商を同じでなければ、上側の配列に n ÷ i の商を追加する
      (例：n = 4, i = 2の時に、n ÷ i = 2 となり、i と商が一致。すでに i が下側の配列に約数として登録されているため、重複しないように上側配列には登録しない)
  - i に1を足し、whileに戻り、次の i を試す
3. 下側配列と上側配列を組み合わせる。ただし、上側配列は、降順で登録されているためスライスを用いて順番を逆順にする。
  - upper_divisors[::-1]の”[]”部分は、開始位置、終了位置、増分を示す。” : “は省略記号
  - 増分がマイナスの場合は、後ろから逆順で要素を取り出す。
    (例：配列A = [1,3,7]の時、A[::-1] = [7,3,1])
4. returnを用いて上記3 で作った配列を返す