蟻本初級編攻略 - 2-4 二分探索木
蟻本の章名である「二分探索木」というサブタイトルを付けたが、Pythonなので二分探索木使わない。setもdictもハッシュマップだ。
ABC085 B問題 Kagami Mochi
上に乗せる鏡餅は下の餅より直径が小さくなくてはいけないという制約のもと、何段の鏡餅が作れるかという問題。
制約は言い換えれば「同じ直径の鏡餅は使えない」ということ。なので直径の重複を除いて数えればいい。
n = int(input()) print(len(set(int(input()) for _ in range(n))))
Pythonなのでsetにしてlenをとるだけ。set化がO(n)、lenがO(1)。
ABC091 B問題 Two Colors Card Game
青と赤のカードに文字列が書いてあって、ある文字列を選ぶとその文字列が書いてある青いカードの数だけポイントがもらえ、赤いカードの数だけポイントが減る。ポイントを最大化する文字列は何か、という問題。
青いカードに書かれている文字列のうち、青いカードの数と赤いカードの数の差額で最も大きいもの、あるいは0が答え：
from collections import Counter n = int(input()) ss = Counter(input() for _ in range(n)) m = int(input()) ts = Counter(input() for _ in range(m)) answer = max(cs - ts[s] for s, cs in ss.items()) print(answer if answer > 0 else 0)
標準ライブラリに入っている、dictを拡張したCounterクラスを使っている。上記のロジックをそのままで記述している。
Counter作成はO(n)、ss.items()のループは全部でO(n)、ts[s]はO(1)、maxはO(n)、と全体でもO(n)の計算量。
