1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

[atcoder] ABC226 涙の反省記事

Posted at

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

ABC226にpython3で参戦。

三完で入茶させてクレメンスと息巻いていたところ、なんと__ABを通すのに40分+5ペナ__という最悪の事態に。

2021-11-07 22.40のイメージ.jpg

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

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

自分のコンテスト結果

2021-11-07 23.12のイメージ.jpg

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

ほな、また......

1
0
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?