Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

 | 

2015-02-04

SRM 648 Div1 550 KitayutaMart

13:29 | SRM 648 Div1 550 KitayutaMart - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 648 Div1 550 KitayutaMart - kojingharangの日記 SRM 648 Div1 550 KitayutaMart - kojingharangの日記 のブックマークコメント

  • i*2^j (1≦i≦K, 0≦j) 円のりんごが 1 個ずつある。合計金額が最小になるように N 個買った時、最高値のりんごの値段を mod 10^9+7 で求めよ。
  • N, K≦10^9
  • ぬぬぬ
  • 表を 1 コずらして 2 で割ると元の表と同じになるから、そんな感じで再帰でわーっとやるのかな
  • 合計が最小になるように買うということは i*2^? を買うなら I*2^? (I≦i) はすべて買うはずだ
  • f(N) = (合計, 最高値) として
  • f(N) = どこまでの i を買うかを K 種類ためしつつ、Sum, V = f(N-今取ったやつ) として (Σi+Sumが最小になるやつ, その時のV)
  • でなんか規則的だから調べる i は実はすごく狭いのかな...
  • わからん
  • あとで
  • 最高値が V のときに買った総数 n_upto(V) は規則的ゆえに分かるので、V で二分探索すればいいのか
  • (N,K)=(1000000000,1) のとき V が大きすぎてだめだ...
  • 最高値が K+1 以上のときは K のりんごは必ず L 個買うとする
  • i*2^j (1≦i≦K, 0≦j≦L) の KL 個も必ず買うことになる
  • L は、1 ≦ N-KL ≦ 最高値が K のときに買う個数 な最小の L がいいっぽい
  • 例えば (N,K)=(41,10)だと n_upto(10)=18なので (L,残り)=(3,11),(4,1)がありうる
  • 答えは n_upto(X)≧残り な最小の X について max(K*2^L, X*2^L (ずれた分) )ということで
  • L=3 なら X=7, 答え=56
  • L=4 なら X=1, 答え=80
  • ...みたいに, うまく証明できないけど L は小さい方が良さそう
  • (詳しくは http://dojiboy9.atspace.cc/contest/view-post.php?p=kitayutamart に書かれているのかもしれない)
  • ということでそんな感じで書いた
  • Accepted in practice
  • もやもやが残る...
// num of cells which value <= v
ll n_upto(ll v) {
	ll ans = 0;
	while(v) {
		ans += v;
		v/=2;
	}
	return ans;
}

ll lb(int N, int K) {
	ll lo=0, hi=K;
	// n_upto(lo)<N<=n_upto(hi)
	while(lo+1<hi) {
		ll mid = (lo+hi)/2;
		if(N<=n_upto(mid)) hi=mid; else lo=mid;
	}
	return hi;
}

class KitayutaMart {
	public:
	int lastPrice(int N, int K) {
		ll countWithinK = n_upto(K);
		ll fillCount = N - countWithinK;
		ll fillLines = (fillCount + K - 1) / K;
		ll restCount = N - fillLines*K;
		return (modll(2)^fillLines) * lb(restCount, K);
	}
};


SRM 648 Div1 250 AB

13:30 | SRM 648 Div1 250 AB - kojingharangの日記 を含むブックマーク はてなブックマーク - SRM 648 Div1 250 AB - kojingharangの日記 SRM 648 Div1 250 AB - kojingharangの日記 のブックマークコメント

  • A,Bからなる長さ N の文字列 s を、s[i]='A', s[j]='B', i＜j な (i, j) が K 個になるように作れ。無理なら "" を返す。
  • 2≦N≦50, 0≦K≦N(N-1)/2
  • BBB があったとして、そこに A を入れる操作を考えると
  • BBBA なら +0
  • BBAB なら +1
  • BABB なら +2
  • ABBB なら +3
  • と、割と自由度が高く数字を増やせることがわかる。
  • B が M 文字あるところに A を 1 個入れると 0〜M が作れる。
  • 一度置いた A は次に置く A にとっては無視できるのでなんか作りやすそうだ。
  • B の個数 0〜N それぞれについて、K を貪欲に減らしていきつつどこにAを入れるかを決めていけばよさそう。
  • それで無理なら "" を返す
  • 全 N, K について検証してから submit (心の平静が訪れた)
  • Accepted
class AB {
	public:
	void check(string s, int N, int K) {
		assert(N==s.size());
		REP(i, N) RANGE(j, i+1, N) if(s[i]=='A'&&s[j]=='B') K--;
		assert(K==0);
	}
	string createString(int N, int K) {
		REP(b, N+1) {
			int k = K;
			int a = N-b;
			map<int, int> bn;
			REP(i, a) {
				int take = min(k, b);
				bn[take]++;
				k-=take;
			}
			if(k==0) {
				string s;
				int ob=0;
				FOR(e, bn) {
					while(ob<e->first) {
						s+="B";
						ob++;
					}
					REP(j, e->second) s+="A";
				}
				assert(N==s.size());
				reverse(ALL(s));
				check(s, N, K);
				return s;
			}
		}
		return "";
	}
};
コメント
 |