2019-06-10に投稿

AtCoder Beginner Contest 073CをPythonで解く

AtCoder Beginner Contest 073CをPythonで解く

今回は、AtCoder Beginner Contest 073Cを解いていきたいと思います。

問題文

あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。
最初、何も書いていない紙がある。
joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これをN回繰り返す。
その後、紙に書かれている数字がいくつあるかを答える。
joisinoお姉ちゃんが言った数字が、言った順番に A1,...,AN として与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。

こう考えた

  • 空の配列Lを作成
  • forで配列Lに要素が無ければappend
  • forで配列Lに要素があればremove
  • len(L)で答えを出力

🐍for1つしか使ってないイケてるコードが書けそうや

実際書いたコード

N=int(input())
L=[]
for i in range(N):
  A=int(input())
  if A in L:
    L.remove(A)
  else:
    L.append(A)
print(len(L))

結果

TLE

🐍for1つしか使ってないのになんでや!

解説を元に考え直す。

Aをソートすると、同じ数が隣り合うように並べ替えられる。

これを左か順にみていくと、奇数回登場する数が何種類あるかを数えることができる。

🐍実装してみよ。

書いたコード

N=int(input())
L=[]
for i in range(N):
  L.append(int(input()))
ans=0
for i in set(L):
  if L.count(i)%2==1:
    ans=ans+1
print(ans)

結果

TLE

🐍まじかよ。。

ListからSetに変えてみる

🐍set早いってまじかよ。。

書いたコード

n = int(input())
s = set()
for i in range(n):
  a = input()
  if a in s:
    s.remove(a)
  else:
    s.add(a)
print(len(s))

結果

AC

🐍まじかよ。。

🐍set()List()より早い。覚えた。

Originally published at www.coderecipe.org

view_list Pythonで競プロ
第2回 Pythonで競プロ|ABC129B|
第3回 Pythonで競プロ|ABC129C|
第4回 AtCoder Beginner Contest 073CをPythonで解く
第5回 AtCoder Beginner Contest 095CをPythonで解く
第6回 AtCoder Beginner Contest 088BをPythonで解く

aocory

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

関連記事

コメント