|
|
|
|
|
||
|
||
| 
つい先週参加したばかりで自分の中で盛り上がってるTopCoderですが、SingleRoundMatch(SRM)のDiv2(Rating1200点以下の人用)の一番簡単な250点問題はこんなのです。*1
// PROBLEM STATEMENT
//
You are given numbers A0, X, Y, M and n.
Generate a list A of length n according to the following recurrence relation:
A[0] = A0
A[i] = (A[i - 1] * X + Y) MOD M, for 0 < i < n
Return the minimal absolute difference between any two elements of A.
DEFINITION
Class:MinDifference
Method:closestElements
Parameters:int, int, int, int, int
Returns:int
Method signature:int closestElements(int A0, int X, int Y, int M, int n)
で、次のメソッドを完成させるわけです。
public class MinDifference { public int closestElements(int A0, int X, int Y, int M, int n) { } }
そこのid:Hash、id:diouf21、楽しそうな気がしませんか?
そうそう、TopCoderをやるときには必ずプラグインを入れてから自分の好きなエディタでやりましょう。問題文がローカルに残らないと復習しにくいからね。
プラグイン導入はTopCoderでCodeProcessor+TZTester+FileEdit - Gulfweedのページにわかりやすい解説があります。
|
サンプルが人数60人に対して問題数が10、さらに問題の上限と下限が全部同じなので、Greedyに全部やれば埋まるんじゃね?と思った。
#include <iostream> using namespace std; #define Fill(a, b) memset(a, b, sizeof(a)) int main() { bool opinion[60][10] = { {true, true, true, true, false, true, true, false, true, true }, {true, false, true, true, false, true, false, true, true, true }, {false, true, true, true, true, true, false, true, true, true }, {true, false, true, true, false, true, false, false, true, false}, {true, true, false, false, false, true, false, false, true, true }, {true, false, true, false, false, true, false, false, true, false}, {true, false, false, true, false, false, false, false, false, true }, {false, false, true, true, false, false, true, true, true, false}, {false, true, false, false, true, true, true, false, true, true }, {true, false, true, true, true, true, true, true, false, true }, {false, true, false, false, true, false, true, false, true, true }, {true, true, true, false, true, false, true, false, true, true }, {false, true, true, true, true, false, true, true, true, true }, {false, false, true, false, false, false, true, true, true, true }, {true, true, true, true, false, true, false, false, true, false}, {false, false, true, false, false, true, true, false, false, true }, {true, true, false, true, false, true, true, true, true, true }, {true, false, false, false, true, false, false, false, false, true }, {false, true, true, true, false, false, false, false, false, false}, {false, true, true, false, false, false, false, true, true, false}, {false, true, false, false, false, false, false, false, true, false}, {true, false, true, true, true, false, true, true, false, true }, {false, false, false, false, true, true, false, true, true, true }, {false, true, true, true, false, false, true, true, true, true }, {true, false, false, false, true, false, true, true, true, false}, {true, true, true, true, true, true, true, false, false, false}, {true, false, true, false, true, false, true, false, true, true }, {false, false, true, false, false, false, false, false, false, true }, {true, false, true, true, false, true, true, false, false, true }, {true, true, true, true, true, true, false, true, false, true }, {false, true, true, false, true, false, false, false, false, true }, {true, true, true, true, false, false, true, true, true, true }, {false, true, true, false, false, true, false, false, true, false}, {true, false, false, true, true, false, true, false, true, false}, {true, false, false, true, true, true, true, false, true, true }, {true, true, false, true, true, false, false, false, true, true }, {true, false, true, false, true, true, true, false, true, true }, {true, true, false, false, true, true, true, true, true, false}, {true, true, false, false, true, false, true, true, true, false}, {false, true, true, false, false, false, false, true, false, true }, {true, true, true, true, false, true, true, false, true, true }, {true, false, true, true, true, false, true, true, true, true }, {false, true, false, false, false, true, true, false, true, true }, {true, false, true, true, false, false, false, true, false, true }, {false, false, false, false, false, false, true, false, true, false}, {false, false, true, false, false, true, true, true, true, true }, {false, true, true, true, true, true, false, false, false, false}, {true, true, false, false, true, false, true, false, false, false}, {true, false, true, true, false, false, true, true, false, true }, {false, false, false, false, false, false, false, true, false, true }, {false, false, false, false, true, true, false, false, true, false}, {true, true, true, true, true, true, false, false, true, false}, {true, true, true, true, true, true, false, true, true, false}, {false, false, false, true, true, false, false, false, false, true }, {true, false, false, false, false, true, false, true, true, true }, {false, false, false, false, false, false, true, true, false, true }, {false, false, true, false, true, false, true, true, false, true }, {true, false, true, true, true, true, true, false, true, true }, {true, true, false, false, true, false, true, true, true, true }, {false, false, false, true, true, false, true, true, false, true } }; int cap[10][2] = { {3, 5}, {3, 5}, {3, 5}, {3, 5}, {3, 5}, {3, 5}, {3, 5}, {3, 5}, {3, 5}, {3, 5} }; int mem[10]; bool used[60]; int wariate[60]; Fill(used, false); Fill(mem, 0); Fill(wariate, -1); for (int i=0; i<60; i++) { for (int j=0; j<10; j++) { if (opinion[i][j] && mem[j] < cap[j][1] && wariate[i] == -1) { mem[j]++; used[i] = true; wariate[i] = j; } } } bool allFull = true; for (int j=0; j<10; j++) { if (mem[j] < cap[j][1]) { cout << "Exp No." << j << " is not satisfied : " << mem[j] << endl; allFull = false; } } if (allFull) { cout << "All Experiments are filled by max capacity"; } return 0; }
実行結果
/Users/suzukitomohiro/srm% ./a.out
All Experiments are filled by max capacity
サンプルデータなら、偶然全部の実験に5人を割り振れたよ!
めでたしめでたし?
|
この問題はどう解けばいいんだ？ / LiosK-free Blog
この実験に割り当てる問題で、最大で人数を11人、実験の数を20、一つの実験の容量を10と仮定する。
次のrecurという関数が表す状態を考える。状態の数は最大で(2の10乗*20*10)存在する。
recurは次の引数をとり、この状態のときに条件を満たす実験の数が最大でいくつできるかを返す。
実験番号はそれぞれの実験に割り当てられた番号で0からはじまる。
誰が既に実験に割り当てられたかというmaskという引数は人数の数分の幅を持つビットで、例えば4人のとき(0, 1, 2, 3番目の人がいるとして)
以上の引数を持つrecurは自分自身を再帰的に呼び出して、さまざまな状態に移ったときの最大値を使って自分が返す値を求める。
ちなみに
また、テストケースも1つしかやってないので間違っている可能性が高い。つまりは上のような手法があるよ、ということを伝えたかっただけ。
#include <vector> #include <queue> #include <iostream> using namespace std; #define Fill(a, b) memset(a, b, sizeof(a)) typedef vector<int> vi; typedef vector<string> vs; class MatchExperiments { public: vector <vector <bool> > mc; vi ec; vi em; int memN; int expN; int dp[1<<10][20][10]; int recur(int mask, int expNum, int curCap) { int tmpmax = 0; if (dp[mask][expNum][curCap] != -1) { return dp[mask][expNum][curCap]; } if (expNum >= expN) { return 0; } if (curCap < 1) { // 実験[expNum]が人でいっぱいになったとき. 最小限の人数は確保されている return 1 + recur(mask, expNum+1, ec[expNum+1]); } // 現在の実験に人をさらに割り当てるとき for (int i=0; i<memN; i++) { if ((mask&(1<<i)) == 0 && mc[i][expNum]) { // 実験に割り当てられていないi番目の人を実験[expNum]に割り当ててみる tmpmax = max(tmpmax, recur(mask|(1<<i), expNum, curCap-1)); } } // 現在の実験に人を割り当てるのをやめて、次の実験に進んだ場合 if (em[expNum] <= ec[expNum] - curCap) { // 次の実験に移る際に、実験[expNum]が最小限の人数を確保しているとき tmpmax = max(tmpmax, 1 + recur(mask, expNum+1, ec[expNum+1])); } else { // 次の実験に移るけど、最小限の人数を確保しいていないとき tmpmax = max(tmpmax, recur(mask, expNum+1, ec[expNum+1])); } dp[mask][expNum][curCap] = tmpmax; return tmpmax; } int mostExperiments(vector <vector <bool> > memberConditions, vector <int> expCapacities, vector <int> expMinCapacities){ mc = memberConditions; ec = expCapacities; em = expMinCapacities; memN = mc.size(); expN = ec.size(); Fill(dp, -1); return recur(0, 0, ec[0]); } private: void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { // Boolean of who accept which experiment vector<vector <bool> > Arg0(4); vector <bool> t0(4); t0[0] = true; t0[1] = false; t0[2] = true; t0[3] = true; Arg0[0] = t0; vector <bool> t1(4); t1[0] = true; t1[1] = true; t1[2] = true; t1[3] = true; Arg0[1] = t1; vector <bool> t2(4); t2[0] = false; t2[1] = false; t2[2] = true; t2[3] = true; Arg0[2] = t2; vector <bool> t3(4); t3[0] = true; t3[1] = true; t3[2] = true; t3[3] = false; Arg0[3] = t3; // Capacities vector<int> Arg1(4); Arg1[0] = 1; Arg1[1] = 2; Arg1[2] = 4; Arg1[3] = 2; // Minimum Capacities vector<int> Arg2(4); // Minimam capacities Arg2[0] = 1; Arg2[1] = 1; Arg2[2] = 3; Arg2[3] = 2; int Arg3 = 3; verify_case(0, Arg3, mostExperiments(Arg0, Arg1, Arg2)); } public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); } }; int main() { MatchExperiments ___test; ___test.run_test(0); }
テストvector <vector <bool> >の定義、もっといい方法ないのかなぁ。
vector <vector <bool> > Arg0 = {{false, false, true}, {true, false, true}, {false, true, false}};
みたいにやりたい。
ちなみにこの解放はTopCoder SRM397Div.2 1000の問題の解法を参考にしてみました。
また、「参加できる実験が少ない人を、割当人数下限の一番少ない実験に割り当てていく」というid:Mishoのシンプルな解法があるので、id:MIshoがそれを書いてくれると思います。
さすが！
でも、やりたい！！！！！！
卒研テーマ決定が終わって学内の発表が終わったらやってみよぉ
でも初級者のウチからトップレベルを見るのは大切かもしれん