こんばんは。たゅと申します。
ABC226にpython3で参戦。
三完で入茶させてクレメンスと息巻いていたところ、なんと__ABを通すのに40分+5ペナ__という最悪の事態に。
Cは推定茶色中盤diffだったので、むしろよく粘ったと自分では納得しています。しかし、ABでここまで詰まることは完全に想定外だったので、コンテスト中は狂いそうでした。
この悔しさをなんとかポジティブな方向に昇華するために、記事を書いております。
概要としては、
ABC226のA,B問題について、python3で解説します。
Cも後で解答を見て余裕があれば復習として追記したいと思います。
A問題
小数点第3位までの小数が与えられ、四捨五入する問題です。
これだけ見ると猿でも解けそうなのですが、__浮動小数点の問題(多分)__でまさかの2ペナ。デカい声を出してしまいました。
__roundを使うとなんかWAが出る__ので、適切に処理する必要があります。
ポイントとして、入力はかならず3.000
のような形でされるという制約があります。
さらに、X < 100の制約より、入力をstringとして受け取った場合のlengthは必ず5か6になります。
このことを利用して、桁数でif文を分岐させ、それぞれ小数点第一位になる部分が5以上であるかどうかを判別し、四捨五入の実装を行います。
ACのコードはこちらです。
X = input()
if len(X) == 6:
if int(X[3]) >= 5:
print(int(float(X))+1)
else:
print(int(float(X)))
else:
if int(X[2]) >= 5:
print(int(float(X))+1)
else:
print(int(float(X)))
printのところでint(float(X))
のように書いていることに注意してください。
int(X)
と書くとエラー出ます。
ホンマ狂うって〜〜〜〜〜〜〜
B問題
リストのリスト(こういうの二次元配列って言うんですよね???)を受け取り、ユニーク化する問題。
普通にリストのリストを作ってset(list(li))
すると、TypeError: unhashable type: 'list'
が出ます。
全探索も、N <= 2 * 10 ** 5
の制約より、余裕でTLEします。
よって、計算量的にOKかつエラーを吐かせない工夫をする必要があります
Bで計算量削減の問題出されるとはマジで思ってませんでした。。。
コンテスト中に対処法をググりました。
こちらの記事の2の項を参考にしました。
要は、__「リストのリストをユニーク化することはできないよ!こういうことがしたいときは、タプルのリストに変換しよう!」__ということですね。
ACのコードはこちらです。
N = int(input())
li = []
for i in range(N):
sm_li = list(map(int, input().split()))
li.append(sm_li)
li_t = list(map(tuple, li))
li_u = set(list(li_t))
print(len(li_u))
本質的に重要なのは以下の部分です。
li_t = list(map(tuple, li))
li_u = set(list(li_t))
一旦リストのリストをタプルのリストに変換してからユニーク化しましょう。
自分のコンテスト結果
耐えた〜〜〜〜〜〜〜〜〜〜〜〜
ほな、また......