SRM 549
続きまして、7/9にあったSRM549
結果報告
250-600-950のセット
| Level | ProblemName | Status | Point |
| Easy | PointyWizardHats | PassedSystemTest | 121.13 |
| Medium | MagicalHats | Opened(Practiced) | 0.0 |
| Hard | CosmicBlocks | Opened | 0.0 |
なんで二部グラフの最大マッチングがEasyだったんだ…
Easy PointyWizardHats
問題
円錐が２つ重なったような帽子を作りたい。
帽子らしい形にするため、上の円錐の底面は必ず下の円錐の斜面のどこかで止まらなくてはならない。
上に乗せる用の円錐の集合と、下に乗せる用の円錐の集合が与えられるので、
そこから最大で何個帽子が作れるかを答えよ。
考えたこと
傾きと底面の半径の両方を考えないと帽子の組合せが正当かどうかわからないので、
単純なグリーディで解けるようなものじゃない気がする……
しかし、任意の円錐ペアを与えられた時、それで帽子が作れるかは簡単に判定できる。
と言うことは……先に上述条件でグラフを作っておけば、二分グラフの最大マッチングで解ける？
はは、まさかね、これEasyだし。
まさか………ね。
…………
いいよ実装してやんよ……ライブラリ？ そんなものはない(白目
コード
public: bool graph[103][103]; bool arrived[103]; int size; int size2; vector<int> dfs( int cur, int goal ){ vector<int> tmp; //cout << "now:" << cur << ":goal"<<goal << endl; if( cur == goal ){ tmp.push_back( goal ); return tmp; } arrived[cur] = true; if( graph[cur][goal] ){ vector<int> recret = dfs( goal, goal); recret.push_back(cur); return recret; } for( int i = 0 ; i < size+size2; i++ ){ if( arrived[i] ) continue; if( graph[cur][i] ){ vector<int> recret = dfs( i,goal ); if( recret.size() != 0 ){ recret.push_back( cur ); return recret; } } } return tmp; } int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius) { int result; size = topHeight.size(); size2 = bottomHeight.size(); memset( graph, false, sizeof(graph) ); for( int i = 0 ; i < size; i++ ){ for( int j = 0 ; j < size2; j++ ){ if( topRadius[i] < bottomRadius[j] && topHeight[i]*bottomRadius[j] > topRadius[i]*bottomHeight[j] ){ //cout << i << j << endl; graph[i][size+j] = true; } } } for( int i = 0 ; i < size+size2; i++ ){ for( int j = 0 ; j < size+size2; j++ ){ //cout << graph[i][j]; } //cout << endl; } for( int i = 0 ; i < size; i++ ){ graph[101][i] = true; } for( int i = 0 ; i < size2; i++ ){ graph[size+i][102] = true; } result=0; while(true){ memset( arrived,false,sizeof(arrived)); vector<int> route = dfs( 101, 102 ); if( route.size() == 0 ) break; result++; for( int i = 0 ; i+1 < route.size(); i++ ){ graph[route[i]][route[i+1]] = true; graph[route[i+1]][route[i]] = false; } } return result; }
Medium MagicalHats
問題
盤面にいくらか帽子が配置されている。
その帽子の中にはコインが入っているかもしれないし、入っていないかもしれない。
コインには値段が書かれており、書かれている値段が配列で与えられる。（つまり配列のサイズがコインの個数である）
プレイヤーはその帽子を１つずつnumGuess回裏返していく。
ゲームマスターは魔法使いなので、以下の条件をみたすのなら、帽子をひっくり返す前にコインの位置を好きに移動できる。
- 任意の行について、帽子の数とコインの数の総和は偶数
- 任意の列について、帽子の数とコインの数の総和は偶数。
ただし、帽子をひっくり返した箇所は、その後の結果が固定される。
プレイヤーもゲームマスターも常に最適な選択をした時、
プレイヤーが得られる金額はいくらになるか。
一つもコインを取れないときは-1を返せ。
考えたこと
条件がコインの値段に関係してないから、
得られるコインの数がわかれば、コインの値段を小さい順に足していって答えが求められるはず。
しかし、得られるコインの数を求めるのにはどうしたら良いんだろうか……それがわからんぞ。。
復習
0:まだ帽子があいてない
1:帽子open,コインがなかった
2:帽子open,コインがあった
の状態を用いてのdpでした。
こうやって言うとできそうな気がしつつ、実装してみたらバッグバグ。このあたりが正確にかけないとレベルアップは厳しいか…
あと、g++では__builtin_popcountという函数があるっていうのをいまだに使いこなせない。
と言うかmingwのコンパイラつかってるとこの函数使えないんですかね。
色々ググって、
http://topcoder.g.hatena.ne.jp/nitoyon/20080921/1222146441
こちらを使うことにしました。
と言うか、n&(n-1)をすると一番下のビットが消える、という仕組み完全に忘れてた。
この関数もしっかりストックしたい。
コード
template<class T> inline int __builtin_popcount( T n ){return (n==0)?0:(1+__builtin_popcount(n&(n-1)));} //(中略) public: int n_hat; int n_coin; int table[2000000]; bool available[2000000]; int pow3[15]; int getCode( int code, int k ){ return (code/pow3[k])%3; } int setCode( int code, int k , int val ){ return code + pow3[k]*val; } void printCode( int mask ){ for( int i = 0 ; i< n_hat;i++){ cout << getCode(mask,i) ; } } int rec(int mask, int numGuesses , int ans){ if( available[mask] == false ) return INT_MAX; if( table[mask] != -1 ) return table[mask]; if( numGuesses == 0 ) return ans; int ret = 0; /* for( int i = 0 ; i< n_hat;i++){ cout << getCode(mask,i) ; } cout << " " << numGuesses << " " << ans << endl; */ for( int i = 0 ; i < n_hat ; i++ ){ if( getCode( mask, i ) != 0 ) continue; int code1 = setCode(mask, i, 1); int code2 = setCode(mask, i, 2); int curans = min( rec( code1, numGuesses-1, ans ), rec( code2, numGuesses-1, ans+1) ); /* printCode(code1); cout << "vs"; printCode(code2); cout<< ":" <<curans << endl; */ ret = max( curans, ret ); } return table[mask]=ret; } int findMaximumReward(vector <string> board, vector <int> coins, int numGuesses) { int x = board.size(); int y = board[0].size(); //set xs,ys to the x or y cordinates of each hats vector<int> xs; vector<int> ys; memset( table, -1 ,sizeof(table)); memset( available, false, sizeof(available) ); for( int i = 0 ; i < x ; i++ ){ for( int j = 0 ; j < y ;j++ ){ if( board[i][j] == 'H' ){ xs.push_back(i); ys.push_back(j); } } } // create 3^k arrays pow3[0] = 1; for( int i = 1 ; i < 15; i++ ){ pow3[i] = pow3[i-1]*3; } n_hat=xs.size(); n_coin = coins.size(); //set the available states for( int i = 0 ; i < (1<<n_hat) ; i++ ){ if( __builtin_popcount( i ) == n_coin ){ int rows[20]={}; int cols[20]={}; for( int j = 0 ; j < n_hat; j++ ){ rows[xs[j]]++; cols[ys[j]]++; if( (i & (1<<j))!=0 ){ rows[xs[j]]++; cols[ys[j]]++; } } bool ok = true; for( int k= 0 ; k< 20 ; k++ ){ if( rows[k] %2 !=0 || cols[k]%2!=0 ){ ok = false; break; } } if( ok ) for( int j = 0 ; j <(1<<n_hat) ;j++ ){ //j represents the mask which has been opened //cout << "pattern" << i << ", hats:" << j << endl; int bit = 0; for( int k = 0 ; k < n_hat ;k ++ ){ if( (j & (1<<k))!=0){ //k-th hat is open int val = 1; if( (i&(1<< k)) != 0 ) val = 2; // state explanation // 0: hat not opened // 1: hat opened and no coin // 2: hat opened with a coin bit = setCode(bit, k , val); } } //if( !available[bit] )printCode(bit),cout<<endl; //cout << bit<<" is available" << endl; available[bit]=true; } } } if( !available[0] ) return -1; int num = rec(0, numGuesses, 0); sort( coins.begin(), coins.end() ); int result = 0; for( int i = 0; i < num ; i++ ) result+=coins[i]; return result; }
Hard Cosmic Blocks
一応開いたけど問題文を読んでよくわからなくて諦めた気がする。
