ABC022-B - Bumble Bee を解く(1)

ABC022-B - Bumble Bee

蜂による花の受粉になぞらえた問題

少し入力例と出力例を見てみよう

入力例

5
1
2
3
2
1

出力例

2

入力例の "2" と "1" は2回目の出現

このように出現が2回目以降の数字が出てくる度に

それをカウントしていけばいいようだ

もちろん2回目だけでなく、3回目以降のものも別にカウントする必要がある

簡単に実装するにはどうするか…

たとえば以下のような数が与えられた場合は？

{1,2,3,4,3,2,3,4,4,3,2,3}

まずは何種類の数があるかを抽出してみる

{1,2,3,4} の4種類だ

4種類について、数を数えてみよう

1・・・1個

2・・・3個

3・・・5個

4・・・3個

"1" は 1個しかないので受粉しない（0）

"2" は 2個目と3個目が受粉する（+2）

"3" は 2個目と3個目と4個目と5個目が受粉する（+4）

"4" は 2個目と3個目が受粉する（+2）

つまり 0 + 2 + 4 + 2 = 8 で合計8個

受粉するということになる

上記の手順をコードに落とし込んでみる

提出したコード

# 入力
N=int(input())

l=[]
for i in range(N):
  l.append(int(input()))

# 種類を抽出
setl=list(set(l))

# (種類ごとの数-1)をカウント
c=0
for x in setl:
  c+=l.count(x)-1

# 出力
print(c)

提出結果はTLE！

このやり方では駄目か…

ABC022-B - Bumble Bee を解く(2) へ続く