AtCoder Beginner Contest 200(京セラプログラミングコンテスト2021)のABC問題をPythonで解答

久しぶりにAtCoderコンテストに参加したので、自分が書いたPythonのコードを共有します。
Atcoderの解答は基本C++の解答コードが掲載され、Pythonの解答コードはないので、参考になれば幸いです。
残念ながら、解くことができたのはABC問題で、DやE、Fまでは解けていません。

A - Century

問題設定

問題文：西暦N年は何世紀ですか？
入力：西暦N年のNを標準入力
出力：何世紀が整数で出力
問題URL

ABC200のA問題のPythonの解答コード

N = int(input())
N = int((N - 1)/100) +1;
print(N)

ABC200のA問題のPythonの解答コード解説

1行目で西暦N年を整数としてint型で標準入力し、変数Nに格納
2行目で何世紀か計算
3行目で出力

西暦N年から何世紀か計算する問題。
つまづきポイントは1世紀＝西暦1年～西暦100年までという点。
単純に100で割るだけだと、西暦100年や西暦200年が次の世紀にカウントされてしまうため、先に1引くことで対処している

B - 200th ABC-200

問題設定

問題文：整数Nが与えられます。以下の操作をK回行った後の整数Nを出力してください。

• 整数Nが200の倍数であれば、Nを200で割る。
• そうでなければ、整数NをNの後ろに文字列として200を付け加えた整数に置き換える。

入力：整数Nと整数Kを入力
出力：問題に記載された操作を行った後の整数Nを出力
問題URL

ABC200のB問題のPythonの解答コード

N,K = map(int,input().split())
for i in range(K):
    if N % 200 == 0 :
        N = int(N /200)
    else :
        N = N *1000 + 200
print (N)

ABC200のB問題のPythonの解答コード解説

1行目で整数Nと整数Kを入力。mapを使った入力
2行目でKの回数forループを実行
3,4行目で200で割り切れる(200の倍数)の場合は200で割る
5,6行目で200の倍数でない場合に数字の末尾に200加える
7行目で操作した結果を出力

問題の記載された通りの操作を実装。
除算をすると、整数が小数点を含むようになるため、int型に変換処理を施しておく。
200の倍数でない場合に、末尾に200足す処理は、整数Nを1000倍し、200足せばOK。

C - Ringo's Favorite Numbers 2

問題設定

問題文：200という整数が大好きなりんごさんのために、次の問題を解いてください。N個の正整数からなる数列Aが与えられるので、以下の条件をすべて満たす整数の組(i,j)の個数を求めてください。

Ai − Ajは 200の倍数である。

入力：数列数Nと数列Aを入力
出力：問題に記載された条件を満たす個数を整数で出力
問題URL

※C問題から計算量を考慮しないといけなくなります。そのまま条件通りに解を求めても、TLEになってしまいます。

ABC200のC問題のPythonの解答コード(TLE解答)

N = int(input())
A = [int(e) for e in input().split()]
count = 0
for i in range(N):
    for j in range(i+1,N):
        if (A[i]- A[j])%200 == 0:
            count = count + 1
print(count)

ABC200のC問題のPythonの解答コード解説(TLE解答)

問題文の通りにコードを実装した結果、計算量がO(N^2)になってしまい、TLE出力してしまいます。

ABC200のC問題のPythonの解答コード(正答)

N = int(input())
A = [int(e) for e in input().split()]
B = [0 for i in range(200)]
count = 0
for i in range(N):
    B[A[i]%200] = B[A[i]%200] + 1
for i in range(200):
    count = int(count + B[i]*(B[i]-1)/2)
print(count)

ABC200のC問題のPythonの解答コード解説(正答)

計算量を少なくするために発想の転換が求められます。
条件である「(Ai-Aj)が200の倍数になる」をどう読み替えられるかが試される問題です。
上記条件は「Ai(mod 200)とAj(mod 200)が等しい」という形に置き換えられます。

例) 「201と601は余りがともに1」→601-201=400で200の倍数

数列すべてに対し、200で割った余りを求め、余りの個数が同じになったものを数えます。
200で割った余りなので、0~199までの200個のどれかに分類されます。
0-199の余り200パターンをforループで処理し、余りの個数Xから2組の数列のペアを抽出します。
X個ある中から2つ取り出す場合の数の計算の計算はxC2となるため、X(X-1)/2で計算します。
この方法であれば、計算量はO(N)となるため、TLE解答のO(N^2)よりも短時間で計算でき、時間内に解答を導くことができます。

終わりに

ここまでC問題を解説したものの、実は時間内にC問題は解けていません(汗)
計算量O(N^2)でTLEに陥ることには気づいたものの、「Ai(mod 200)とAj(mod 200)が等しい」に読み替えることができませんでした。
解答を読んで、場合の数まで出てきたことにアハ体験を受けたので、自分なりの理解をまとめてみました。