cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み
スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、
SRM | |
SRM442 の成績・ソース (要ログイン) : AC/WA/- : うひゃー
あとで | |
とりあえず通るには通ったけど、こんなもの*絶*対*に*ミスなく書けるわけがないし、解けたとはいえない…。どうしたものかな。x方向の分割とy方向の分割を分離して3分割を2段みたいな書き方をしたら少しはマシになるだろうか。
typedef long long LL; class BedroomFloor { public: long long numberOfSticks(int x1, int y1, int x2, int y2) { #define F(x) ((x)/5*5) // floor #define C(x) F((x)+4) // ceil LL b[6] = {}; if( F(x1)==F(x2) ) if( F(y1)==F(y2) ) { count_s(x1, x2, y1, y2, b); } else { count_s (x1, x2, y1, C(y1), b); count_my(x1, x2, C(y1), F(y2), b); count_s (x1, x2, F(y2), y2 , b); } else if( F(y1)==F(y2) ) { count_s(x1, C(x1), y1, y2, b); // count_mx(C(x1), F(x2), y1, y2, b); // count_s(F(x2), x2, y1, y2, b); } else { count_s ( x1 , C(x1), y1, C(y1), b); count_my( x1 , C(x1), C(y1), F(y2), b); count_s ( x1 , C(x1), F(y2), y2 , b); // count_mx(C(x1), F(x2), y1, C(y1), b); count_l (C(x1), F(x2), C(y1), F(y2), b); count_mx(C(x1), F(x2), F(y2), y2 , b); // count_s (F(x2), x2 , y1 , C(y1), b); count_my(F(x2), x2 , C(y1), F(y2), b); count_s (F(x2), x2 , F(y2), y2 , b); } return optimize(b[1], b[2], b[3], b[4], b[5]); } bool is_horizontal(LL x, LL y) { return x/5%2 == y/5%2; } void count_s(LL x1, LL x2, LL y1, LL y2, LL b[]) { if( is_horizontal(x1, y1) ) b[x2-x1] += y2-y1; else b[y2-y1] += x2-x1; } void count_my(LL x1, LL x2, LL y1, LL y2, LL b[]) { LL n=(y2-y1)/5, n1=n/2, n2=(n+1)/2; b[x2-x1] += 5 * (is_horizontal(x1,y1) ? n2 : n1); b[5] += (x2-x1) * (is_horizontal(x1,y1) ? n1 : n2); } void count_mx(LL x1, LL x2, LL y1, LL y2, LL b[]) { LL n=(x2-x1)/5, n1=n/2, n2=(n+1)/2; b[y2-y1] += 5 * (is_horizontal(x1,y1) ? n1 : n2); b[5] += (y2-y1) * (is_horizontal(x1,y1) ? n2 : n1); } void count_l(LL x1, LL x2, LL y1, LL y2, LL b[]) { b[5] += ((x2-x1)/5) * ((y2-y1)/5) * 5; } LL optimize( LL b1, LL b2, LL b3, LL b4, LL b5 ) { LL total = 0; for(int k=6*6*6*6*6; --k>0; ) { int k1 = k%6; int k2 = k/6%6; int k3 = k/6/6%6; int k4 = k/6/6/6%6; int k5 = k/6/6/6/6%6; if( 1*k1 + 2*k2 + 3*k3 + 4*k4 + 5*k5 <= 5 ) { LL n = 1LL<<62; if(k1) n = min(n, b1/k1); if(k2) n = min(n, b2/k2); if(k3) n = min(n, b3/k3); if(k4) n = min(n, b4/k4); if(k5) n = min(n, b5/k5); total += n; b1 -= n*k1; b2 -= n*k2; b3 -= n*k3; b4 -= n*k4; b5 -= n*k5; } } assert( b1==0 && b2==0 && b3==0 && b4==0 && b5==0 ); return total; } };
再々挑戦。
(x1,y1)-(x2,y2)が同じ5x5に収まるまで分解し尽くすようにしてみた。こんなもんかなあ。
class BedroomFloor { public: LL b[6]; long long numberOfSticks(int x1, int y1, int x2, int y2) { b[1] = b[2] = b[3] = b[4] = b[5] = 0; devideX_and_count(x1, x2, y1, y2); return optimize(); } // utils LL FLOOR(LL x) { return x/5*5; } LL CEIL (LL x) { return FLOOR(x+4); } // counting routines void devideX_and_count(LL x1, LL x2, LL y1, LL y2) { if( FLOOR(x1) == FLOOR(x2) ) devideY_and_count(x1, x2, y1, y2, 1); else devideY_and_count( x1, CEIL(x1), y1, y2, 1 ), devideY_and_count( CEIL(x1), CEIL(x1)+5, y1, y2, ((FLOOR(x2)-CEIL(x1))/5+1)/2 ), devideY_and_count( CEIL(x1)+5, CEIL(x1)+10, y1, y2, ((FLOOR(x2)-CEIL(x1))/5+0)/2 ), devideY_and_count( FLOOR(x2), x2, y1, y2, 1 ); } void devideY_and_count(LL x1, LL x2, LL y1, LL y2, LL rep) { if( FLOOR(y1) == FLOOR(y2) ) count(x1, x2, y1, y2, rep); else count(x1, x2, y1, CEIL(y1), rep), count(x1, x2, CEIL(y1), CEIL(y1)+5, rep*(((FLOOR(y2)-CEIL(y1))/5+1)/2) ), count(x1, x2, CEIL(y1)+5, CEIL(y1)+10, rep*(((FLOOR(y2)-CEIL(y1))/5+0)/2) ), count(x1, x2, FLOOR(y2), y2 , rep); } void count(LL x1, LL x2, LL y1, LL y2, LL rep) { if( x1/5%2 == y1/5%2 ) // is_horizontal b[x2-x1] += rep*(y2-y1); else b[y2-y1] += rep*(x2-x1); } // compute minimum number of 1x5 blocks required (by greedily removing larger blocks) LL optimize() { LL total = 0; for(int K=6*6*6*6*6; --K>0; ) { int k[] = {-1, K%6, K/6%6, K/6/6%6, K/6/6/6%6, K/6/6/6/6%6}; if( 1*k[1] + 2*k[2] + 3*k[3] + 4*k[4] + 5*k[5] <= 5 ) { LL n = 1LL<<62; for(int i=1; i<=5; ++i) if( k[i] ) n = min(n, b[i]/k[i]); for(int i=1; i<=5; ++i) b[i] -= n*k[i]; total += n; } } return total; } };
presented by
cafelier/k.inaba
under
