SRM624 Div1 Easy "BuildingHeights"
問題
TopCoder Statistics - Problem Statement
訳
バイトランドはたくさん高層ビルが建つ都市であり、ベースジャンプ(*)に最適な場所である。ダニーロは有名なベースジャンパーである。彼はバイトランドへ行き、そこにある建造物でベースジャンプをする計画を立てていた。
ダニーロはバイトランドで好きなだけジャンプを行うことができる。しかし、彼にはルールがあった。まず1つ目が、彼は同じ建物でジャンプするのは一回だけとしている。2つ目に、彼がジャンプする場所として選ぶ全ての建物は、同じ階であることとしている。(それぞれのジャンプのスタート地点が違う高さだと、正確なタイミングをとるのが難しいという安全面の理由がある)
フィリップはバイトランドの市長である。彼は都市の宣伝にもなることから、ダニーロが来る事を歓迎していた。もちろん、ダニーロにはより多くジャンプをしてもらえば、それだけよい宣伝になると考えていた。しかし、同じ高さの建物が十分にない場合どうなるか?この問題を回避するために、市長はダニーロが訪れる前に、手を打つことにした。フィリップはバイトランドのいくつかの高層ビルの階を増築することにしたのだ。
あなたはint配列のheightsが与えられる。これらはバイトランドにある高層ビルの階を現している。heightsが持つ要素の数をNとする。Mを1からNのそれぞれとしたときに、次のような質問に答えよ。
市長が少なくともM個のビルを同じ階にするために、追加する階の最小値はいくつか?
iを1からNまでとして、A[i]がM = iの時の答えだとする。そのときに(A[1] XOR A[2] XOR ... XOR A[N])の値を返せ。
制約
1 <= ビルの数 <= 4000
1 <= ビルの高さ <= 4000
考えたこと
こうゆうのはまずソートすると良いことが起きそう。
そうするとi番目のビルに高さを合わせる時に、i - 1, i - 2 ... のビルを増築すればよくなる。
i番目までの合計値をとっておけば、i - 1, i - 2 ... のビルの合計と、どれだけ増築すれば言いかが一瞬で分かる。
計算量はO(N^2)。
/_ノ ヽ、_\ ミ ミ ミ o゚((●)) ((●))゚o ミ ミ ミ 簡単だおwwwwwww /⌒)⌒)⌒. ::::::⌒(__人__)⌒:::\ /⌒)⌒)⌒) | / / / |r┬-| | (⌒)/ / / // Div1たいしたことないおwwww | :::::::::::(⌒) | | | / ゝ :::::::::::/ | ノ | | | \ / ) / ヽ / `ー'´ ヽ / / バ | | l||l 从人 l||l l||l 从人 l||l バ ン ヽ -一''''''"~~``'ー--、 -一'''''''ー-、 ン ヽ ____(⌒)(⌒)⌒) ) (⌒_(⌒)⌒)⌒))
/ ̄ ̄\ / _ノ \ | ( ●)(●) 30分以上かかってんじゃねーか . | (__人__) | ` ⌒´ノ . | } ミ ピコッ . ヽ } ミ /\ ,☆____ ヽ ノ \ \ / \ / く \. /\/ ─ ─ \ | `ー一⌒) / (●) (●) \ | i´ ̄ ̄ ̄ \ | (__人__) | \_ ` ⌒´ / / \
ソースコード
int N; int sum[4040]; class BuildingHeights { public: int minimum(vector <int> H) { N = H.size(); sort(H.begin(), H.end()); sum[0] = H[0]; for (int i = 1; i < N; i++) { sum[i] = sum[i - 1] + H[i]; } int result = 0; for (int L = 1; L < N; L++) { int best = H[L] * L - sum[L - 1]; for (int i = L + 1; i < N; i++) { best = min(best, H[i] * L - (sum[i - 1] - sum[i - L - 1])); } result ^= best; } return result; } };