得点 (Score) 解説
O(n^2) 解法
ある人x について, 自分より上の得点をとった人がk 人いるとすれば, その人の順位はk + 1 位となる.
最も単純な解法としては, 自分より上位の人数をO(n) 時間で求めることである.
n 人についてO(n) 時間の処理を行うので, 計算量はO(n^2) になる.
コード例 (C++, 24 行)
O(n) 解法
O(n^2) 解法では, n が大きいと実行時間に間に合わない. そこで, 以下の様な工夫を行う.
この問題に於いて, 得点としてありうる数値は 0 点 から 100 点 までの 101 個の整数値であることに注意する.
すなわち, この101 個の数値について, それぞれの順位を前計算しておけば, それぞれの人の点数に対応する順位をO(1) 時間で出力することで, 順位の出力がO(n) 時間で行える.
順位の前計算は, 次のようにして行える.
- ある点をとった人の人数を管理する配列bucket を用意する.
- 入力時に, x 点をとった人がいればbucket[x]を1 増加させる.
- ある得点の順位を記録する配列rank を用意する.
- rank[100] は1 であり, 100 より小さい数値xについて, rank[x] = bucket[x + 1] + rank[x + 1] となる. これを99 から 0 まで降順に求めていく.
rank[x] の計算は100 回の計算で行えるため, 計算量はO(n + 100) となる.
コード例 (C++, 29 行)
コメント
最終更新：2013年02月24日 18:33
