[atcoder] ABC226 涙の反省記事

こんばんは。たゅと申します。

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))

一旦リストのリストをタプルのリストに変換してからユニーク化しましょう。

自分のコンテスト結果

耐えた〜〜〜〜〜〜〜〜〜〜〜〜

ほな、また......