Python初心者のためのABC200

A問題
B問題
C問題

A問題

西暦と世紀の関係を観察してみる．西暦 $N$ 年が $X$ 世紀になるとすると，

N	X
1 〜 100	1
101 〜 200	2
$\vdots$	$\vdots$
2901 〜 3000	30

どうやら

$N$ を100で割る（割った値を $N_0$ とする）

$N_0$ を整数に切り上げた値を $X$ とする

とすれば良さそう．割り算は / を使えばできるし，整数への切り上げはググると math.ceil という関数が出てくる．これらを使って，

from math import ceil

N = int(input())
N0 = N / 100
X = ceil(N0)
print(X)

とすればACできる．

しかし，この解き方はオススメしない．

Pythonの数値には，整数型 int と小数型 float の2種類がある．上のコードにおける各数値の型は以下のようになっている．

N = int(input()) # int
N0 = N / 100     # float
X = ceil(N0)     # int

今回の問題の場合は扱う数が比較的小さいので問題ないが，float の計算は一般には誤差が生じてしまう．例えば，222222222222222222を111111111111111112で割って整数に切り上げた値は1（1.999... -> 1）だが，

from math import ceil
print(ceil(222222222222222222/111111111111111112))

> 2

となってしまう．そのため，数値はなるべく int のままで扱う方が望ましい． Pythonでは，整数の割り算は // と % で行うことができる．

a, b = 7, 3
print('aをbで割った商:', a//b)
print('aをbで割った余り:', a%b)

> aをbで割った商: 2
> aをbで割った余り: 1

これを用いれば，「 $N$ を100で割った余りを整数に切り下げた値」は N//100 で求めることができる．一方，整数に切り上げた値はというと，

$a, b$ を整数とする． $\frac{a}{b}$ を整数に切り上げた値は $\lfloor\frac{a+b-1}{b}\rfloor$ で求められる．

ということを利用すれば，

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

のようにしてACを得られる．上記のコードでは，数値を終始 int で扱っているため誤差の心配はない．

B問題

atcoder.jp

変数の型には，A問題で扱ったような int や float の他に，文字列 str というものが存在する．それぞれで行うことのできる操作が違うので，型にゆるいPythonといえども明示してやる必要がある．

int_100 = 100    # int
str_100 = '100'  # str

print(int_100 + int_100)
> 200

print(str_100 + str_100)
> 100100

数値に対する + は足し算だが，文字列に対する + は結合をあらわす．数値と文字列同士を足し算しようとするとエラーになる．今回の問題のポイントを整理すると，

決められた操作を $K$ 回行う -> for を使う

$N$ の値に応じて操作が異なる -> if を使う

数値的な操作と文字列的な操作の2種類がある -> int，str を使い分ける

となるので，以上を丁寧に実装してやると良い．

N,K = map(int,input().split())

# 操作をK回繰り返す
for i in range(K):

  # Nが200で割り切れるかどうかで場合分け
  if N%200==0:
    N = N//200
  else:
    N = str(N)  #文字列に変換する
    N = N + '200'
    N = int(N)  #整数に戻す

print(N)

なお，else 以下の操作は「 $N$ を1000倍してから200を足す」という操作に置き換えれば，いちいち文字列に変換する必要はなくなる．基本的に文字列の結合は遅く文字列の長さに比例した計算時間がかかるため，長い文字列の結合を扱う問題の場合には注意する必要がある．

C問題

atcoder.jp

まずは素直に実装してみる．

N = int(input())
A = list(map(int,input().split()))

ans = 0

for i in range(N):
  for j in range(i+1,N):
    if (A[i]-A[j])%200==0:
      ans += 1

print(ans)

無事TLEが得られる．この方法だと，調べる必要のある $(i,j)$ の組は ${}_{N}\mathrm{C}_2$ 通りあり， $N\le 2\times 10^5$ という制約から最大で $10^{10}$ 通り程度になる． AtCoderのジャッジシステムにおいて2秒以内で可能な計算回数は $10^7\sim 10^8$ 程度であるため，上記の解法では制限時間に間に合わないことが分かる．計算量の話をする際によくオーダーという言葉が用いられるが，上記の解法は $N^2$ に比例した計算時間がかかる $O(N^2)$ の解法である．今回の問題の場合， $O(N^2)$ の解法では例えC++などの速い言語を用いたとしてもTLEしてしまうため，別の解法を考える必要がある．

ここで $j$ を固定した場合に条件をみたす $i$ の個数の効率的な求め方を考えてみる．条件を満たす $i$ というのは，

$i \lt j$ をみたす

$A_i$ と $A_j$ を200で割った余りが等しい

ようなものである． $i$ の値自体に興味はなく， $i, j$ の大小関係と $A_i, A_j$ を200で割った余りさえ気にすればいいことが分かる．そのため，

$cnt_j[k$ ]： $A_1,\dots,A_{j-1}$ のうち200で割った余りが $k$ であるような要素の個数

のようなリストがあれば，ある $j$ に対して条件をみたす $i$ の個数は $cnt_j[A_j\%200$ ]で求められる．また， $cnt_j$ は $cnt_{j-1}[A_{j-1}\%200$ ] に1を足しただけの $cnt_{j-1}$ と等しいので， $j$ が小さい順に同じリストを使い回して値だけを更新していけば良い．

N = int(input())
A = list(map(int,input().split()))

ans = 0
cnt = [0]*200

for a in A:
  k = a % 200
  ans += cnt[k]
  cnt[k] += 1

print(ans)

なお，前処理として $A$ の要素全てを200で割った余りに変換しておいたり，最初に「 $A$ の要素のうち200で割った余りが $k$ であるような要素の個数」を求め，各 $k$ に対して「200で割った余りが $k$ であるような $A$ の異なる2つの要素を選ぶ場合の数」を求めて足し合わせても良い．

N = int(input())
A = list(map(int,input().split()))

# 各要素を200で割った余りに変換
A = [a%200 for a in A]

ans = 0
cnt = [0]*200

for a in A:
  cnt[a] += 1
  
for c in cnt:
  ans += c*(c-1)//2  # c個の要素から異なる2つの要素を選ぶ場合の数

print(ans)

いずれの解法も $N$ に比例した計算時間しかかからない $O(N)$ の解法であるため，無事ACを獲得できる．

きゃねろぐ

とある「おひさま」の徒然日記

Python初心者のためのABC200

A問題

B問題

C問題