kojingharangの日記

SRM 552 Div1 250 FoxPaintingBalls

01:06 |

• N段の三角形が無限にある。１つ１つはi段目にi個の球を置く形でビリヤードみたいになっている
• 各球を赤緑青の三色どれかで塗る。接する球は同じ色には塗れない。
• 赤緑青の色はそれぞれ R, G, B 回使える。
• 全部が塗られた三角形は最大何個作れるか。
• N≦10^9, R, G, B≦10^18

• １コの三角形について、１番上と（もしあれば）２番目の色を決めるとあとは全部一意に決まる。
• その三角形で使う各色の回数 (a, b, c) を求めるのにしばらく苦労して謎の複雑な関数が完成
• その回数(a, b, c)を赤緑青に最適に割り振って R, G, B を超えなければいい
• 最適な割り振り方がわからず、謎の貪欲法でサンプルが通ったので提出
• →failed system test

• あとで
• M = N(N+1)/2 として、(a, b, c) = (M/3, M/3, M/3 + M%3) となるらしい。(証明できず)
• さらに解を仮定した２分探索をするらしい。
• （そういえばこないだの高さを調整する問題も２分探索が思いつかなかったなぁ）
• 解を mid として
• どんな割り振り方でも最低 M/3 ずつは消費するので、R, G, B からそれぞれ mid * M/3 を引いて
• 大丈夫なら、mid * M%3 の分を残りの R, G, B でまかなえるか判定する。

↓あとで (passed system test in practice room)

class FoxPaintingBalls {
	public:
	long long theMax(long long R, long long G, long long B, int N) {
		ll tot = (ll)N*(N+1)/2;
		ll to3 = tot/3;
		ll lo=0, hi=(R+G+B)/tot+1;
		while(lo+1<hi) {
			ll mid = (lo+hi)/2;
			ll r=R-mid*to3;
			ll g=G-mid*to3;
			ll b=B-mid*to3;
			//cout<<mid<<" "<<r<<" "<<g<<" "<<b<<endl;
			if(r>=0 && g>=0 && b>=0 && (tot%3 ? (mid <= (r+g+b)/(tot%3)) : 1)) lo=mid;
			else hi=mid;
		}
		return lo;
	}
};

ツイートする

SRM 552 Div1 500 FoxAndFlowerShopDivOne

01:06 |

• 残り 25 分くらい。
• grid に L or P or . が入っている。
• ２つの重ならない矩形内にて L の数(nL)と P の数(nP)の差が M 以内であるような最大の nL + nP を求める。
• grid の最大サイズ 30x30, M≦900

• 累積和を使ったとしても矩形１と矩形２をそれぞれ決めて判定すると 30^8 = 656*10^9 とかなのでだめ
• わからんね
• nL-nP ってそんなに種類ないからそれを使うんではないかと気づく
• nL-nP でソートして lower/upper bound とか使うのか？？
• 終了

• cafelier さんのをみると
• 分割軸を決めて(W+H通り)
• その左右or上下で全通り nL-nP, nL+nP を求めて
• その際 nL-nP が同じなら nL+nP が最大のものだけ残せばいいので map に記録していって
• 左右or上下から１コずつ全通りとってきて判定
• 最大でも (W+H)*(2*W^2*H^2 + 2*WH) ということで O(W^5) 程度に収まる模様。

• ↓実装練習 (passed system test in practice room)

class FoxAndFlowerShopDivOne {
	public:
	int theMaxFlowers(vector <string> F, int M) {
		int W=F[0].size();
		int H=F.size();
		
		// sum[y][x] is sum of [0, x) x [0, y)
		VVI sum(H+1, VI(W+1));
		VVI dif(H+1, VI(W+1));
		REP(x, W) REP(y, H) {
			sum[y+1][x+1] = (F[y][x]!='.' ? 1 : 0) + sum[y][x+1]+sum[y+1][x]-sum[y][x];
			dif[y+1][x+1] = (F[y][x]=='L' ? 1 : (F[y][x]=='P' ? -1 : 0)) + dif[y][x+1]+dif[y+1][x]-dif[y][x];
		}
		//cout<<sum<<endl;
		//cout<<dif<<endl;
		
		int ans = -1;
		REP(X, W) {
			map<int, int> hi0, hi1;
			// [0, X) x [0, H)
			for(int x0=0;x0<X;x0++) {
				for(int x1=x0;x1<X;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=0;y0<H;y0++) {
						for(int y1=y0;y1<H;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi0[D] = max(hi0[D], S);
							//cout<<MP(x0, MP(x1, MP(y0, y1)))<<" "<<S<<" "<<D<<endl;
						}
					}
				}
			}
			// [X, W) x [0, H)
			for(int x0=X;x0<W;x0++) {
				for(int x1=x0;x1<W;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=0;y0<H;y0++) {
						for(int y1=y0;y1<H;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi1[D] = max(hi1[D], S);
						}
					}
				}
			}
			FOR(e0, hi0) FOR(e1, hi1) if(abs(e0->first+e1->first)<=M) ans=max(ans, e0->second+e1->second);
		}
		
		REP(Y, H) {
			map<int, int> hi0, hi1;
			// [0, W) x [0, Y)
			for(int x0=0;x0<W;x0++) {
				for(int x1=x0;x1<W;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=0;y0<Y;y0++) {
						for(int y1=y0;y1<Y;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi0[D] = max(hi0[D], S);
						}
					}
				}
			}
			// [0, W) x [Y, H)
			for(int x0=0;x0<W;x0++) {
				for(int x1=x0;x1<W;x1++) {
					// [x0, x1] x [y0, y1]
					for(int y0=Y;y0<H;y0++) {
						for(int y1=y0;y1<H;y1++) {
							int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0];
							int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0];
							hi1[D] = max(hi1[D], S);
						}
					}
				}
			}
			FOR(e0, hi0) FOR(e1, hi1) if(abs(e0->first+e1->first)<=M) ans=max(ans, e0->second+e1->second);
		}
		return ans;
	}
};

ツイートする