水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 103:C - /\/\/\/

問題

C - /\/\/\/

解法

数列の奇数個目と偶数個目で新しく数列を2つつくり,それぞれの中で最も多く登場する要素の数を N / 2 から引いたものが答えになるが,これだと,それぞれ同じ数字が当てはまってしまう場合が考えうる.そのため,「最も多く」ではなく「1,2番目に多く」に変更すれば解くことができる.O(NlogN).

解答

Submission #3292454 - AtCoder Regular Contest 103

考察ミスで 1 WA してしまった.

f:id:babcs2035:20180929230734p:plain