SRM 552
結果報告
250-500-1000のセット。
| Level | ProblemName | Status | Point |
| Easy | FoxPaintingBalls | PassedSystemTest | 86.34 |
| Medium | FoxAndFlowerShopDivOne | Opened(practiced) | 0.0 |
| Hard | -- | Unopened | 0.0 |
怒りの一発黄色復帰……というほど格好良い復帰方法じゃないですけれど
Easy撃沈者多め＋resubしたけどEasyは通ってた＋１チャレンジ成功、のお陰で一発で黄色に戻ってこれました。
Easy FoxPaintingBalls
問題
高さNの、n段目にn個のボールが置いてあるような三角形がある。
隣り合った色が同じにならないように、各ボールをRorGorBの色に塗って行きたい。
R,G,Bに塗れるボールの数の最大値を与えるので、この制約のもと何個の三角形が色塗り可能か答えよ。
考えたこと
頂点の色が決まったら左右対称を除いて色塗りの仕方固定されちゃうのか。
しかもボールの数って1,3,6,7,9,12,18...となっていくので、3で割り切れるか1余るかのどちらか。
つまり、一つの三角形を作るときに、R,G,Bは同じ個数のボールを塗るか、１色だけ１個余分にボールを塗るか、の２択である。
前者の場合はmin(R,G,B)/一個の三角形を塗るのに一色が塗るボールの数でおｋ。もちろんN=1の時はボールの数を返すようにしとく。
後者の場合は、min(R,G,B)/一個の三角形を塗るのに一色が塗るボールの数（の、少ない方）が、余力分より小さいなら、この数で塗れる。
そうでない場合は、余力が十分になるまで、三角形の数を減らしていけば良いかな。
提出した。
……あれ、これ、三角形の数を一個ずつ減らしていくとTLEするんじゃね？
R=1000000000000000000,
G=1000000000000000000,
B=1000000000000000000,
N=4
で試してみた。
…TLEきたー！
という訳で考え直す。
三角形の数を減らしていかなくてはいけない時、というのはつまり、
三角形を構成するボールの数を3M+1,min(R,G,B)/M=Kとすると、
R+G+B-3*MK < K
が成立している時で、
このKを一つつず小さくしながら、R+G+B-3MK>=KとはじめてなるKを答えることになる。
つまり、R+G+B>=(3M+1)Kであるから、K=(R+G+B)/(3M+1)を返すことさえ出来れば良い。
コード
long long theMax(long long R, long long G, long long B, int N_) { if( N_ == 1 ) return R+G+B; long long result=LLONG_MAX; ll N = (1LL+(N_))*N_/2; ll Bas = N/3; ll base[3] = {N/3,N/3,N/3}; ll total = (N/3)*3; int offset = N-total; for( int i = 0 ; i < N-total; i++ ){ base[2-i]++; } vector<ll> vec; vec.push_back(R); vec.push_back(G); vec.push_back(B); sort( vec.begin(), vec.end() ); for( int i = 0 ; i < 3 ; i++ ){ //ll tmp = vec[i]/Bas; //cout << vec[i] << " /" << Bas << ":" << tmp << endl; result = min( result, vec[i]/Bas); //cout << result << endl; } if( offset == 0 ){ return result; } else{ result = min( result, (R+G+B)/N); } return result; }
Medium FoxAndFlowerShopDivOne
長方形のフィールドに二種類の花が配置されている。
きつねさんはこのフィールドから、領域内の二種類の花の本数差maxdiffとなるような、互いに交わらない２つの長方形領域を選び、
その中の花を取得する事ができる。
最大何本の花を取得することが可能か？
考えたこと
圧倒的dp臭。
フィールドが30*30が最大であることから、本数差は900が上限になっていて、
ある領域内部で、二種の花の本数差がX( -900<=X <= 900)で、取得可能な花の本数最大値、とかを使って頑張るんじゃないかね。
と思ったところで時間切れ。
とりあえず、計算量30^6はギリギリセーフと読んで、(x,y)〜(x+h,y+w)までの各花の本数を数えて配列[x][y][h][w]にいれる所までやった。
復習
cafelierさんのコードをkojingharangさんが説明してるブログ（http://topcoder.g.hatena.ne.jp/kojingharang/20120817）を読んだ。
縦に二分されている２領域を考え、
上の領域の本数差がXであるときの取得可能な花の本数最大値を配列difftable1に用意 <- (30^4)くらいでできる
下の領域の本数差がXであるときの取得可能で花の本数最大値を配列difftable2に用意 <- (30^4)くらいでできる
あとは、上の領域で本数差がXである時、abs(X+Y)<=maxDiffとなるようなすべてのYをdifftable2から参照して、difftable1[X]+difftable2[Y]
の最大値を記憶する。 <-(30^4くらいでできる)
縦に二分する方法は30くらいあるので、ここまでで30^5である。
これを横の分割についても同様実行すれば良い。
コード
int theMaxFlowers(vector <string> flowers, int maxDiff) { int result; int N_L[31][31][31][31]; int N_R[31][31][31][31]; memset( N_L , 0 , sizeof(N_L)); memset( N_R, 0 , sizeof(N_R)); int height = flowers.size(); int width = flowers[0].size(); for( int x = 0 ; x < height; x++ ){ for( int y = 0 ; y < width; y++ ){ for( int h = 1 ; x+h-1 < height ;h++ ){ for( int w = 1 ; y+w-1 < width; w++ ){ for( int hh = 0 ; hh < h ; hh++){ for( int ww = 0; ww< w ; ww++ ){ if( flowers[x+hh][y+ww]=='L' )N_L[x][y][h][w]++; if( flowers[x+hh][y+ww]=='P' )N_R[x][y][h][w]++; } } //cout << "N_L(" << x << "," << y << ","<< h<<","<<w<<"):" << N_L[x][y][h][w]<< " "; //cout << "N_R(" << x << "," << y << ","<< h<<","<<w<<"):" << N_R[x][y][h][w]<< " "; } } } } result = -1; int diftable[2][1801]; for( int i = 1 ; i < height; i++ ){ // vertical partitioning memset( diftable, -1, sizeof(diftable)); for( int x = 0 ; x < i ; x++ ){ for( int y = 0 ; y < width ; y++ ){ for( int h = 1 ; x+h-1 < i; h++ ){ for( int w = 1 ; y+w-1 < width; w++ ){ int dif = N_L[x][y][h][w]-N_R[x][y][h][w]; int sum = N_L[x][y][h][w]+N_R[x][y][h][w]; diftable[0][900+dif]=max(diftable[0][900+dif],sum); //cout << dif <<", "<< sum << endl; } } } } //cout << endl; for( int x = i; x<height; x++ ){ for( int y = 0 ; y < width ;y++ ){ for( int h = 1; x+h-1 < height; h++ ){ for( int w = 1 ; y+w-1 < width ;w++ ){ int dif = N_L[x][y][h][w]-N_R[x][y][h][w]; int sum = N_L[x][y][h][w]+N_R[x][y][h][w]; diftable[1][900+dif]=max(diftable[1][900+dif],sum); } } } } for( int u = 0 ; u <= 1800; u++ ){ for( int d = 0 ; d <= 1800; d++ ){ if( diftable[0][u] == -1 || diftable[1][d] == -1 || abs(u+d-1800)> maxDiff) continue; //cout << u-900 << "," << diftable[0][u]; //cout << " " << d-900 << "," << diftable[1][d]; //cout << endl; result = max( result,diftable[0][u]+diftable[1][d] ); } } } for( int j = 1 ; j < width; j++ ){ // horizontal partitioni memset( diftable, -1, sizeof(diftable)); for( int x = 0 ; x < height ; x++ ){ for( int y = 0 ; y < j ; y++ ){ for( int h = 1 ; x+h-1 < height; h++ ){ for( int w = 1 ; y+w-1 < j; w++ ){ int dif = N_L[x][y][h][w]-N_R[x][y][h][w]; int sum = N_L[x][y][h][w]+N_R[x][y][h][w]; diftable[0][900+dif]=max(diftable[0][900+dif],sum); } } } } for( int x = 0; x<height; x++ ){ for( int y = j ; y < width ;y++ ){ for( int h = 1; x+h-1 < height; h++ ){ for( int w = 1 ; y+w-1 < width ;w++ ){ int dif = N_L[x][y][h][w]-N_R[x][y][h][w]; int sum = N_L[x][y][h][w]+N_R[x][y][h][w]; diftable[1][900+dif]=max(diftable[1][900+dif],sum); } } } } for( int u = 0 ; u <= 1800; u++ ){ for( int d = 0 ; d <= 1800; d++ ){ if( diftable[0][u] == -1 || diftable[1][d] == -1 || abs(u+d-1800)> maxDiff) continue; //cout << u-900 << "," << diftable[0][u]; //cout << " " << d-900 << "," << diftable[1][d]; //cout << endl; result = max( result,diftable[0][u]+diftable[1][d] ); } } } return result; }
