AtCoder Beginner Contest 206を振り返る

全体の感想

C問題まではどうにかできましたが、D問題はTLEでした。実績は以下のような感じで徐々に下がってきてますね。。。

B - Savings

B - Savings

問題

i日目にi円を貯金箱に入れるとき、N円を超えるのは何日目か？

制約

1<=N<=10^9

回答

n = int(input())
t = 0
d = 0
while(True):
   d += 1
   t = (d*d + d)/2
   if t >= n:
       break
print(d)

コードとしてはかなりシンプルなんですが、Atcoderでは大体計算量が10^7を超えるとTLEになるので、Nが最大10^9の場合は単純なループではTLEになるのではないかとちょっと迷いました。後で解説を見てみたところ、N円になるにはN^0.5程度の日数で済むので上記のようなループでも問題ないとのことです。

C - Swappable

C - Swappable

問題

N個の整数からなる配列Aが与えられるので、以下の条件を満たす組み合わせを全て求める問題

1<= i < j <=N
A[i] ≠ A[j]

制限

2 <= N <= 3*10^5
1 <= A[i] <= 10^9

iとjで入れ子のループを書くと以下のように簡単に書けるんですが、

n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(len(a) - 1):
   for j in range(i+1, len(a)):
       if a[i] == a[j]: continue
       cnt += 1
print(cnt)

Nの最大数は3*10^5なので、これを多重でループするとあっという間にTLEになってしまいます。

工夫して書いたのが以下

n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt, i, dupulicate  = 0, 0, 1
while(i < n - 1):
   if a[i] == a[i+1]:
       dupulicate += 1
   else:
       cnt += (n - i - 1)*dupulicate
       dupulicate = 1
   i += 1
print(cnt)

ソートすることで同じ数字はまとめて処理してる感じですね。Whileが上手く使えたんじゃないかと思います。

ちなみに解説を見て書いたのが以下。

n = int(input())
a = list(map(int, input().split()))
c = {}
cnt = 0
for i in range(len(a)):
   cnt += i - c.setdefault(a[i], 0)
   c[a[i]] += 1 
print(cnt)

うーん非常に分かりやすいですね、同じ数字は記録しておいて足し上げする値から引いておくという。これをパッと思いつきたかったところ。