AtCoder Beginner Contest (ABC) 226 Pythonで参戦しました。B問題まで解説あり
前回の参戦
こんにちは。 めりーです。
今回のAtCoder Beginner Contest (abc) 226 大沼にはまりました。
なぜB問題が解けないんだああああああああああああああああああああああ
というわけで、結果はA問題のみ正解でした。
悲しいね。
というわけで懺悔を兼ねながら解説していきます。
言語はPython、提出はPyPyです。
目次
A問題
Round decimals
問題文
ある実数が小数第三位まで与えられています。
少数第一位を四捨五入した値は？
という問題。
四捨五入するにあたって、少数第一位を調べる必要がある。
そして、その調べた値によって、小数部を切り上げるのか、切り捨てるのか決める。
これをまとめると、
方針は、
1. 整数部と小数部を分けて入力。
2. 小数部の最上位の桁が4以下と5以上で場合分け。
3. 2の場合分けによって変化した整数部を出力。
という形になる。
というわけでコードがこちら。
x,y = input().split(".")
if int(y[0]) >= 5:
print(int(x)+1)
else:
print(x)
はい、いつもおなじみのsplit()を使ってます。
split()の引数に文字を指定すると、その文字で区切って入力してくれます。
今回は問題文的に絶対「.」が含まれているので、それで区切ります。
そして、小数第一位(y[0])が4以下なのか、5以上なのかで場合分けします。
5以上の場合は切り上げるので、整数部に1足して出力します。
4以下の場合は切り捨てるので、整数部をそのまま出力します。
これでこの問題は終わりです。
B問題 コンテスト編
Counting Arrays
問題文
滅茶苦茶沼沼不可避問題。
数列がN個与えられます。
数列は全部で何種類あるでしょうか？
という問題。
「なーんだ、setを使えば簡単じゃーん！！」
「error」
「じゃあ、問題文に書いてある通りに全探索で！！！」
「TLE」
「ふざけるなあああああああああああああああああああああ！！！！！！！！！！」
ってことが起こりました。
ダメだったコード
n = int(input())
suretu = []
for _ in range(n):
a = list(map(int,input().split()))
suretu.append(a)
ans = n
for i in range(n):
for i2 in range(i+1,n):
if suretu[i][0] == suretu[i2][0]:
if suretu[i] == suretu[i2]:
ans -= 1
print(ans)
はい、計算量が約N×(1/2)Nなので、(1/2)N2 = 2×1010くらいですね。
※AtCoderでは、約108くらいのループが回せるそうです。
suretuをsetにしてlenを使おうとしてもエラーになるし、どうしたらええんや～～～～～～～！！！！
B問題 コンテスト後編
というわけでコンテストが終わりました。
解説を見ました。
解説
Editorial - AtCoder Beginner Contest 226
意訳
「set使ったら簡単だよ！！」
set使ったらエラーで使えなかったんだが？？？？？？？？？？
というわけで正解のコードがこちらです。
n = int(input())
suretu = []
for _ in range(n):
a = input()
suretu.append(a)
print(len(set(suretu)))
エラー吐いたのはこっち
n = int(input())
suretu = []
for _ in range(n):
a = list(map(int,input().split()))
suretu.append(a)
print(len(set(suretu)))
というわけで、正しい方針は、
1. 入力する。
2. setで長さを数える。
で、よかったみたいですね。
さて、では、なぜ自分でコードを書いたときはエラーが出たのか。
それは、setではlistを要素に入れられない。ということです。
エラーを吐いたコードを見てもらえば分かると思いますが、suretuが二次元配列になっているのがわかると思います。
suretu = [[1,1],[1,2,3]]
みたいな感じ。
こういうのはsetでは使えないみたいです。
代わりに、
suretu = ["1 1","1 2 3"]
みたいなのはsetにできるのです。
なので、文字列として入力を扱えばsetで長さを正常に数えることができるのです。
というわけでした。
いやー、知らない性質が出てきて得られるものが多かったコンテストでした。
それでは！！
