AtCoder Beginner Contest 200 A〜C問題
前書き
AtCoder Beginner Contest 200に参加しました。
B問題
- 難易度:灰
- 時間:8分
問題を誤読していた為、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分
時間かかりすぎィ!!反省です。(毎回言ってる気がする)
与えられた整数の配列の各要素の差が200の倍数になる組み合わせを出力せよと言う問題。
ただ要素数 : Nが 2 ≤ N ≤ 2*10**5 なので、二重ループだとTLEになります。なので一重ループで解く必要があります。
最初、累積和関連かなと探っていました。ただし違ってました。
結論は以下のアルゴリズムです。
与えられた配列の数値を場合分けしていきます。
「二つの数値の差が200の倍数」ということは二つの要素には「以下の共通点」があります。
- 100で割った剰余が等しい(差が200の倍数(同様に100の倍数でもある)になるから当然)
- 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の基礎がすっ飛んでました。
以下の書き方だと同じ配列を複数定義してるだけなので、値を変更すると別の要素まで変更されてしまいます。
注意しましょう。
list2 = [[0]*4]*2 for j in range(100): list2[0][0]+=1 print(list2) [[100, 0, 0, 0], [100, 0, 0, 0]]