きままにものづくり

日々の気付いたことなんかを書いてます。

SRM606Div1Easy

問題

1から1,000,000,000までで1つだけ選び、その数字を当てるゲームを考える。guessは予測の数字であり、answerは予測の数字からの差分の絶対値を示す。選ばれた数字を求めよ。複数候補がある場合は-1を、嘘をつかれてる場合は-2を出力する。

解法

解の候補を全列挙し、出現回数を調べれば答えが求まる。1から1,000,000,000の配列を保持するのは無理なので二分探索木であるmapを用いる。

計算量

挿入:  O(log N)
探索:  O(N)
全体:  O(N log N)

コード