![見出し画像](https://assets.st-note.com/production/uploads/images/55334831/rectangle_large_type_2_dc781306696fb8ee65f17810ee05f0d3.png?width=1200)
AtCoder Beginner Contest 206を振り返る
全体の感想
C問題まではどうにかできましたが、D問題はTLEでした。実績は以下のような感じで徐々に下がってきてますね。。。
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
問題
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)
うーん非常に分かりやすいですね、同じ数字は記録しておいて足し上げする値から引いておくという。これをパッと思いつきたかったところ。
この記事が気に入ったらサポートをしてみませんか?