TopCoder: SRM434: Division2 :Easy-problem

さて、以前のエントリーにでTopCoderの説明みたいなのをしたけど、今回はきまぐれにTopCoderの問題の解説をしてみようと思う｡
でもあんまり難しいとちゃんと解説できないかもしれないし、第1回目だし、一番簡単な問題でいいかな｡

======   Question ==========
タイトルの回の問題は…
「引数として与えられる二つの配列A, B(長さは一緒)を考えた時、それぞれの要素同士を乗算して、その積を足して、その和が最小となる組み合わせを求め、その和を返せ」
って感じ｡
具体的に例を示すと…
A=[1,4,6,2]
B=[10,4,5,5]
１つずつ要素を掛けて、それを足して、答えが最小になるようにだから…
Answer= 1*10 + 2*5 + 4*5 + 6*4 = 64　

こんな感じの計算をするメソッドを作るのがタスクなんだけど…まあ簡単だよね?
じゃあ、問題の解法を続きで解説します｡


========   Answer  ===========
さて大体の人は解説の必要もないと思うけど、まあ一応載せておきます｡

つまり、解が最小になるようにすればいいんだから…
①  Aの最小の要素とBの最大の要素を見つけて掛け合わせる
②  そのときに使ったそれぞれの要素を配列から消去
③  その積を全体の合計に足す
④  ①②③の工程を残りの要素数が０になるまで繰り返す
って感じのアルゴリズムでいけそうだな｡

ってことで、解等例のコード（C++）｡
--------------------------------------
int minimalArrangement(vector <int> A, vector <int> B){
sort(A.begin(),A.end());
sort(B.begin(),B.end());
int s = 0;
for(int i = 0; i < A.size(); i++)
s += A[i] * B[B.size() - 1 - i];

return s;
}
--------------------------------------
何をやっているかって言うと、
①A、Bをソーティング
②Aの先頭から、Bの最後尾から、順に乗算して、積を適当な変数に加算
って感じです｡たいしたことはやって無いよね?（でも、TopCoderは問題文が英語だし制限時間もあるしで、コーディングスキルの他に数学英語の速読力も必要なんだよね orz）
ちなみにこっちにはJavaで書いたコードも置いてあるのでよければ参考に｡

TopCoderには日本人が異様に少なくて寂しいので、もし興味が湧いたなら是非一度みんな遊び感覚で挑戦してみるといいと思う｡タダだし｡
では｡