AtCoder Beginner Contest 200 A〜C問題

AtCoder Python

前書き

AtCoder Beginner Contest 200に参加しました。

A問題

  • 難易度：灰
  • 時間：2分

atcoder.jp

今、何世紀かを求める問題。

import math
N=int(input())
print(math.ceil(N/100))

B問題

  • 難易度：灰
  • 時間：8分

atcoder.jp

問題を誤読していた為、B問題の割に少々時間がかかってしまいました。
整数Nが200の倍数の場合 or not で場合分けする必要がありますが、これをすっ飛ばしてしまいました。

N,K=map(int,input().split())
for k in range(K):
  if N%200!=0: N=int(str(N)+'200')
  else: N=int(N/200)
print(N)

C問題

  • 難易度：？
  • 時間：45分

atcoder.jp

時間かかりすぎィ！！反省です。（毎回言ってる気がする）

与えられた整数の配列の各要素の差が200の倍数になる組み合わせを出力せよと言う問題。
ただ要素数 : Nが 2 ≤ N ≤ 2*10**5 なので、二重ループだとTLEになります。なので一重ループで解く必要があります。

最初、累積和関連かなと探っていました。ただし違ってました。

結論は以下のアルゴリズムです。
与えられた配列の数値を場合分けしていきます。

「二つの数値の差が200の倍数」ということは二つの要素には「以下の共通点」があります。

  1. 100で割った剰余が等しい（差が200の倍数（同様に100の倍数でもある）になるから当然）
  2. 100で割った商の奇数・偶数が一致（差が200の倍数のため）

サンプルに倣って考えていきましょう。

123 223 123 523 200 2000

1) 100で割った剰余が等しい
"23" => 123 223 123 523
"00" => 200 2000

2) 100で割った商の奇数・偶数が一致
"23"
[1]奇数：123 123 523 => 要素数：3
[2]偶数：223 =>  要素数：1

"00"
[3]偶数：200 2000 => 要素数： 2

上記の[1][2][3]の3パターンに分類できました。
最後に各パターンにおいて2つ以上存在するパターンにおいて、2つ選んだ組み合わせを算出するのみです。

import math
N=int(input())
A=list(map(int,input().split()))
list1 = [[0 for i in range(2)] for j in range(100)]

for i in range(N):
  list1[A[i]%100][(A[i]//100)%2]+=1
_sum=0
for i in range(100):
  for j in range(2):
    if list1[i][j]>1:
      _sum+=(list1[i][j]*(list1[i][j]-1)/2)
    
print(int(_sum))

おまけ

Pythonの基礎がすっ飛んでました。
以下の書き方だと同じ配列を複数定義してるだけなので、値を変更すると別の要素まで変更されてしまいます。
注意しましょう。

www.sejuku.net

list2 = [[0]*4]*2
for j in range(100):
  list2[0][0]+=1
print(list2)

[[100, 0, 0, 0], [100, 0, 0, 0]]