TopCoder SRM 442 DIV 2
@Matsu4512 と @phyllo にホイホイ誘われてTopCoderの環境を入れました。
プラグイン環境について参考にしたのはこちら。
で、さっそく3人で過去問を75分でやってみました。
結果はProblem 250だけ正解、Problem 500はSystem Checkで2秒制限アウト、Problem 1000は＼(^o^)／
そこまで手も足もでないという感じではなかったのでちょっと頑張りたい。
Project Eulerやっててよかったなーって思いました。これをやってなかったらそれこそ手も足も出ていないはず。
Problem 250 SimpleWordGame
問題
Simple Word Gameは、与えられた辞書からできるだけ多くの単語を覚えるというゲームです。プレイヤーが正しく覚えた各単語のスコアは、単語の長さの2乗です。
あなたにはプレイヤーが記憶した単語が要素になっている String player が与えられます。同じ単語があった場合は、一度だけカウントします。また、それぞれ異なる単語が要素になっている String dictionary も与えられます。プレイヤーの合計のスコアを返しなさい。
http://www.topcoder.com/stat?c=problem_statement&pm=10465&rd=13750
解説
この問題を解くには、問題の条件を正確に理解することが必要です。playerの各固有の単語について、もしdictionaryの中に単語が見つかったときはその長さの2乗をスコアに加えます。このアルゴリズムをすばやく実装するためには、setのデータ構造がとても役に立ちますが、必ず必要というわけはありません。KnightOfTheSunの解法がシンプルな例です。
http://www.topcoder.com/wiki/display/tc/SRM+442
My code
class SimpleWordGame { public: int points(vector <string> player, vector <string> dictionary) { int result = 0; set<string> s; vector<string> p2; // 重複をなくす for(int i=0 ; i<(signed)player.size(); i++){ s.insert(player[i]); } sort(player.begin(), player.end()); for(int i=0 ; i<(signed)dictionary.size() ; i++){ if( s.find(dictionary[i]) != s.end()) p2.push_back(dictionary[i]); } for(int i=0 ; i<(signed)p2.size() ; i++){ result += p2[i].length()*p2[i].length(); } return result; } };
わざわざsetとか使わなくても良かった・・・たぶん15分ぐらい。
Problem 500 Underprimes
問題
数Xの素因数分解は、かけることでXと等しくなる素数列です。例えば、12の素因数分解は2*2*3です。1は素数ではないことに気をつけましょう。
Underprime は、素因数分解の要素の数が素数個になるような数です。例えば、12は素因数分解の要素が3つで、3は素数なのでUnderprimeです。与えられたAとBに対して、AとBの間のunderprimeの数を返しなさい。
http://www.topcoder.com/stat?c=problem_statement&pm=10274&rd=13750
解説
この問題はエラトステネスの篩を応用することで解けます。B以下の全ての数についてエラトステネスの篩を用い、数が素数かどうかを決めるboolを保存する代わりに、各数について素因数分解の要素の数、または0を保存します。
int howMany(int A, int B) { int primefactors[B+1]; //initialize primefactors array fill( primefactors, primefactors+B+1, 0); // with zeroes. primefactors[0] = primefactors[1] = 1; //0 and 1 are not primes for (int i=2; i<=B; i++) // if(primefactors[i] == 0) //it is a prime number for (int j=2*i; j<=B; j+=i ) // For each multiple of i for (int x = j; x%i == 0 ; x/=i ) // appropriately increase primefactors[j]++; // the number of prime factors. int c=0; for (int i=A; i<=B; i++) if( primefactors[ primefactors[i] ] == 0) //Is the number of prime c++; //factors a prime number? return c; }http://www.topcoder.com/wiki/display/tc/SRM+442
My code
//素数を max まで計算する deque<bool> p; void calc_prime(const int max){ for(int i=0 ; i<max+1 ; i++){ p.push_back(true); } p[0] = false; p[1] = false; double myEnd = sqrt(double(max)); for(int i=2 ; i < myEnd ; i++){ for(int j=2 ; i*j<=max ; j++){ p[i*j] = false; } } } // nの素因数分解し、素数の個数を返す。 int factNum(int n){ int ret=0; int i=0; while(n!=1){ i++; while(p[i] && n%i==0){ n = n/i; ret++; } } return ret; } class Underprimes { public: int howMany(int A, int B) { int result = 0; calc_prime(100000); for(int i = A; i<=B ; i++){ if(p[factNum(i)]) result++; } return result; } };
25分ぐらい。
そもそも素数を生成しすぎで、calc_primeに100000でなく B を渡してやればよかった。
素因数分解ももっとうまく書けるはずー・・・
Problem 1000 EqualTowers
問題
ジョニーは複数個の長方形のレンガを持っています。彼は塔を建てるために、互いの上にレンガを積むことができます。彼は、持っているレンガを使って同じ高さの塔を2つ作ろうとしています(各塔は少なくとも1つのレンガでできていなければいけません)。また、できるだけ高くしたいと考えています。全てのレンガを使う必要はありません。
あなたは各要素がレンガの高さである int[] bricks を与えられます。ジョニーが立てることのできる一番高い2つの塔の高さを返しなさい。等しい高さの2つの塔を建てることが不可能な場合は-1を返しなさい。
http://www.topcoder.com/stat?c=problem_statement&pm=10466&rd=13750
解説
まず始めに「全てのレンガの要素の合計は500000以上になることはない」という制約に注目しましょう。これより、最大の塔は高さが500000を超えることはありません。しかし、両方の塔は高さが等しくなるので、実際の最大限の大きさは 500000/2 = 250000です。
問題を分析しましょう。全てのレンガについて、1つ目の塔に積むか、2つ目の塔に積むか、それとも無視するかを決定することができます。まず高さが0の塔が2つあるところから始まり、最初のレンガを加えるかどうかから決めます。レンガを塔の1つに配置すると、問題はより一般的なものに変わります。「与えられた2つの塔、高さDの塔と高さ0の塔と複数個のレンガに対して、作ることのできる等しい高さの2つの塔の中で最も大きいものはどれか？」各レンガについてまた3つの選択をすることができます。ではK番目のレンガをどうするかを決定する方法を考えましょう。
レンガを無視すると決定した場合は、配列の次のレンガに進みます。レンガを大きい方に積む場合は、Dにbricks[k]が加えられます。(図A)他の決定としては、低い方の塔(高さ0と仮定しているもの)にレンガを積む場合があります。これには、レンガの高さがDより低い場合(図B)かD以上の場合(図C)があります。
それぞれの決定からは、Kより大きいindexのレンガしか使用できないという制約を除けば、一般的な状態(大きい方はD、小さい方は0の高さを持つ)の原則に従うsub-caseが導かれます。どちらの塔も0の高さでない2つの特別な場合(図Bと図C)は、D=D'を解くことで変形できます。点線の下の部分は無視して、後から付け加えることが出来ます。全てのレンガについて考慮し終えた時、高い方の塔は高さ0でなければいけません。そうでない場合は2つの塔の高さは異なっています。
問題を解くための再帰を作るためには、これまでの解析が役立ちます。しかし再帰のみでは実行時間制限を超えてしまうため、メモ化や動的計画法(DP)を使う必要があります。Kは高々50、Dは高々250000ですから、memory limitに十分収まります。
using namespace std; const int MAX_TOWER_SIZE = 250000; const int INF = 1000000; struct EqualTowers { int mem[50][MAX_TOWER_SIZE+1]; int subProblem(const vector<int>&bricks, int K, int D) { if(D>MAX_TOWER_SIZE) // Invalid case, return -INF; // difference is too large if(K== bricks.size() ) { if ( D == 0) //towers have equal sizes: return 0; //So it is a valid case with max increment 0 else return -INF ; //invalid case. } int &res = mem[K][D]; if(res!=-1) // memo-ization step return res; // // ignore this brick: int a = subProblem( bricks, K+1, D); // place this brick on the larger tower (A): int b = subProblem( bricks, K+1, D + bricks[K] ); // place this brick on the shorter tower: int c; if ( bricks[K] > D) c = D + subProblem( bricks, K+1, bricks[K]-D); //(C) else c = bricks[K] + subProblem( bricks, K+1, D-bricks[K]); //(B) res = std::max(a, std::max(b,c) ); //pick the largest tower // size increment. return res; } int height(vector <int> bricks) { memset(mem, -1, sizeof(mem)); // initialize memory int largest = subProblem(bricks, 0, 0); if( largest == 0) // for our subproblem, a par of towers return -1; // of size 0 is possible, but the problem // requires us to return -1 in this case. return largest; } };http://www.topcoder.com/wiki/display/tc/SRM+442
＼(^o^)／
