Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

2017-02-12

SRM 708 Div1 500 PalindromicSubseq

13:01 |  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記 のブックマークコメント

  • 久しぶりの参加。
  • 長さ 1≦N≦3000 の文字列 s が与えられる。
  • X[i] = "s[i] を含む s の部分列のうちそれが回文になるものの個数 mod 10^9+7" とする
  • i in [0, N) に対して (i+1)*X[i] の XOR を求めよ。
  • ひょ〜
  • サンプルを見て初めて問題の意味が分かる
  • SRM 中に出たアイデアや考察
    • 回文ということは中央に軸があるので軸の位置を全部試す感じでいけないか?
    • 軸の左右にどちらもある文字しか使われない
    • L, R より外で回文のとき、内側は何通り?
  • さっぱり
  • おわり
  • あとで
  • 上位陣のをいくつか見る
  • s[i] を必ず採用する時、部分列が回文になるなら s[i] の反対側に対応する同じ文字があるはずである。(s[i] が中央なら s[i] 自身)
  • なるほど

  • s[i] が決まればそれに対応する文字の位置は N 種類
  • s[i], 対応する文字を左から L, R とすると ? ? ? L * * * R ? ? ? という形で表せる
  • 内側(*)だけで回文になる部分列の個数と外側(?)だけで回文になる部分列の個数を N^2 DP で求めておけば
  • L, R が決まったときの組み合わせ総数は 内側回文個数 * 外側回文個数 O(1) で求まる
  • X[i] を計算するときは L, R の組み合わせは N 通りなので X[i] は O(N) で求まる
  • 全体 O(N^2)
  • 内側 : dp1[i][j] ... [i, j] 内の部分列かつ回文の個数
  • 外側 : dp2[i][j] ... [0, i), (j, N) 内の部分列かつ回文の個数
  • として書いてみたが内外共に半開区間の方がいろいろすっきりするのかもしれない。
  • DP2つとそれを組み合わせる処理を正確に書かないといけないので難しい.....
  • Accepted in practice
class PalindromicSubseq {
	public:
	int solve(string s) {
		ll N = s.size();
		// dp1[i][j] ... [i, j] 内での回文の個数
		vector<vector<modll>> dp1(N, vector<modll>(N));
		// dp2[i][j] ... [0, i), (j, N) 内での回文の個数
		vector<vector<modll>> dp2(N, vector<modll>(N));
		RANGE(L, 0, N+1) REP(i, N-L+1) {
			int j = i+L-1;
			if(L==0) {
				if(0<=j && i<N) dp1[i][j] = 1; // empty
			} else {
				modll v = 0;
				// s[i] を採用しない場合 (s[j]は採用するしないどちらも含む)
				if(i+1<N) v += dp1[i+1][j];
				// s[j] を採用しない場合 (s[i]は採用するしないどちらも含む)
				if(0<=j-1) v += dp1[i][j-1];
				// s[i], s[j] 両方採用しない場合が 2 回数えられている分を減らす
				if(0<=j-1 && i+1<N) v -= dp1[i+1][j-1];
				if(s[i]==s[j]) {
					// s[i], s[j] を採用できる。採用するとその内側の組み合わせ総数だけ増える
					if(0<=j-1 && i+1<N) v += dp1[i+1][j-1];
				}
				dp1[i][j] = v;
			}
		}
		for(int L=N;L>=1;L--) REP(i, N-L+1) {
			int j = i+L-1;
			if(L==N) {
				dp2[i][j] = 1; // empty
			} else {
				modll v = 0;
				// 同様
				if(0<=i-1) v += dp2[i-1][j];
				if(j+1<N) v += dp2[i][j+1];
				if(0<=i-1 && j+1<N) {
					v -= dp2[i-1][j+1];
					if(s[i-1]==s[j+1]) {
						// s[i-1], s[j+1] を採用できる。採用するとその外側の組み合わせ総数だけ増える
						v += dp2[i-1][j+1];
					}
				}
				dp2[i][j] = v;
			}
		}
		ll ans = 0;
		REP(i, N) {
			modll X = 0;
			REP(j, N) {
				if(s[i]==s[j]) {
					ll I=i, J=j;
					if(I>J) swap(I, J);
					// ここでは I, J がどちらも採用され I, J が回文にて対応関係にある。
					// 内側は [I+1, J-1] 内の回文の個数
					// 外側は [0, I), (J, N) 内の回文の個数
					// これらの積が "I, J がどちらも採用され回文にて I, J が対応関係にある" 場合の組み合わせ総数。
					X += (I+1<=J-1 ? dp1[I+1][J-1] : modll(1)) * dp2[I][J];
				}
			}
			ans ^= modll(i+1LL)*X;
		}
		return ans;
	}
};

2015-10-14

SRM 671 Div1 300 BearCries

03:16 |  SRM 671 Div1 300 BearCries - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 671 Div1 300 BearCries - kojingharangの日記  SRM 671 Div1 300 BearCries - kojingharangの日記 のブックマークコメント

  • なんか久しぶりの参加な気がする。
  • ;__; な顔文字(_は1コ以上)が、1コの顔文字内では順番が保持されたまま何セットか混ざった200文字以内の文字列が与えられる。valid な顔文字に分割する方法は何通りあるか? (mod 10^9+7で)
  • 考察考察
  • ;の個数は偶数じゃないとだめ
  • 両端は;じゃないとだめ
  • 各 _ の両端に来る ; という観点ではどうか? -> 単純な掛け算にならなさそう
  • 最大200文字→3でわって最大66コの顔文字しかない
  • ; までできてる ;_までできてる ;_;までできてる数を別々な状態として持つDPは?
  • -> 新規に _ が現れた場合、今までの ; が ;_ になったのか ;_ が ;_ になったのか一意にきまらない (※後で→元状態から複数の状態に遷移できるので一意に決まらなくてもいいし)
  • わからんし全探索を書く
  • 最初の文字は; である。対応する右の;を決め、その間の _ から全 bit 組み合わせで全通り取る。ただし 1 コ以上。
  • 採用した顔文字を消した後の文字列を再帰的に count で計算する。
  • これは動いた。...が、そこから発展がない...
  • いろんなパティーンの解を印字してぢっと眺むる。
  • おわり
  • あとで
  • Tourist の見ると3次元DP。だが添字の意味が分からず。ほぉ〜??
  • [i][;][;_] なる TL が。
  • ; が来たら新規 ; を作るか ;_ に ; を足して1コ完成させるかすることができる。(; に ; は足せない)
  • _ が来たら ; を ;_+ にするか ;_+ を ;_+ にすることができる。(新規 _ は作れない)
  • で最終的に途中の顔文字がない状態 [N][0][0] が答え
  • 分かってしまえば分かるがどうして分からなかったか分からない
  • どんな指標で状態を同一視するか、状態ごとにどんな演算をするか(これとこれを足しちゃっていいのか??とか)、MECEになってるか、あたりの思考がクリアにできてない感じがする。
  • 今回だと、その指標だと状態から状態への演算がうまくいかん →実はうまくいく みたいな
  • 具体的には ; が来た時 新規 ; と ;_+ → ;_; を別々に加算しちゃってるけど何かこう二重にカウントしちゃってる気がする→だめだ あたり。
  • Accepted in practice
// [i][j][k] ... M[I], I in [0, i] の範囲で, ;で終わってる顔文字が j コ, ;_+ な顔文字が k コあるような状態の個数
modll dp[202][202][202];
class BearCries {
	public:
	int count(string M) {
		CLEAR(dp, 0);
		int N=M.size();
		dp[0][0][0]=1;
		REP(i, N) REP(j, N) REP(k, N) {
			auto cur = dp[i][j][k];
			if(M[i]==';') {
				dp[i+1][j+1][k] += cur; // 新規 ;
				if(k-1>=0) dp[i+1][j][k-1] += cur*modll(k); // ;_+ -> ;_+; (k コある)
			} else {
				dp[i+1][j][k] += cur*modll(k); // ;_+ -> ;_+ (k コある)
				if(j-1>=0) dp[i+1][j-1][k+1] += cur*modll(j); // ; -> ;_+ (j コある)
			}
		}
		return dp[N][0][0];
	}
};

2015-06-05

SRM 660 Div1 250 Coversta

10:36 |  SRM 660 Div1 250 Coversta - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 660 Div1 250 Coversta - kojingharangの日記  SRM 660 Div1 250 Coversta - kojingharangの日記 のブックマークコメント

  • N*M のグリッドがあり、各マスに 0-9 の数字が書いてある。Pos[ ] も与えられ、あるマス p に駅を置くと p+P (P in Pos[ ]) なマスがカバーされる。
  • 異なる場所に2駅置いたとき、2駅がカバーするマスに書いてある数字の合計の最大値を求めよ。
  • 2≦N,M≦100, 1≦K=|Pos[]|≦10, -(N-1)≦Pos.x≦N-1, -(M-1)≦Pos.y≦M-1
  • カバー範囲が重なった時の処理がポイントっぽいぞ
  • naiveにやると置き方全てに対して Pos[] のとこを塗って確かめるので N^2 M^2 K -> 10^9 程度 -> むり
  • カバー範囲の重なり方は最大で K^2 個なことに気づく
  • なので「カバー範囲が重なるように2駅置いた時にカバーするマスのパターン」を最大10*10個持っておいて、
  • (1)カバー範囲が重なる2点を置いたときの最大値(N^2 M^2 K)と
  • (2)カバー範囲が重ならない2点を置いたときの最大値(事前にマス→カバー範囲の合計値をNMKで計算しておき重複かどうかをmapで覚えておくとN^2M^2logK)
  • の最大値が答え
  • (1)では、重なり方すべてK^2について最初の点から見た2点目の相対座標と最大K*2点(最初のカバー範囲∪ちょっとずらした範囲)のパターンを覚えておく
  • (2)では2点目の相対座標が(1)で計算した相対座標セットに含まれない=2点のカバー範囲が重ならない、という感じでチェックすればいい。
  • ていうことで N^2M^2logK なので良さそうではあるが、...
  • これで250か, 書いてピッタリ答えが合うとは思えない...
  • IN_RANGE(Value, Min, Max) マクロ大活躍の巻き
  • なぜかサンプルが合った → 3x3 で10ケースくらい手動テストしてOKそうなので 95pt くらいで提出
  • Accepted
  • おー通るのかよ
  • (あとで)K^2+α個で打ち切る NMK^2 解もあるのか。(そっちはなぜそれでいいか腑に落ちてない)
struct Pos {
	int x, y;
	bool operator<(const Pos v) const {
		return x*1000+y < v.x*1000+v.y;
	}
	bool operator==(const Pos v) const {
		return x==v.x && y==v.y;
	}
};
std::ostream& operator<<(std::ostream& os, const Pos& v) {
	os << "("<<v.x<<", "<<v.y<<") ";
	return os;
}

struct Pat {
	Pos ref;
	vector<Pos> pos;
};

class Coversta {
	public:
	int place(vector <string> a, vector <int> X, vector <int> Y) {
		int W=a.size(), H=a[0].size();
		int N=X.size();
		VVI one(W, VI(H));
		vector<Pat> pat;
		map<PII, int> ng;
		REP(x, W) REP(y, H) REP(i, N) {
			if(IN_RANGE(x+X[i], 0, W) && IN_RANGE(y+Y[i], 0, H)) {
				one[x][y]+=a[x+X[i]][y+Y[i]]-'0';
			}
		}
		REP(i, N) REP(j, N) if(i!=j) {
			// i-j
			int dx = X[i]-X[j];
			int dy = Y[i]-Y[j];
			auto key = MP(dx, dy);
			if(ng.count(key)) continue;
			if(dx==0 && dy==0) continue;
			ng[key] = 1;
			vector<Pos> v;
			REP(k, N) v.PB(Pos{X[k], Y[k]});
			REP(k, N) v.PB(Pos{X[k]+dx, Y[k]+dy});
			sort(ALL(v));
			v.erase(unique(ALL(v)), v.end());
			pat.PB({Pos{dx, dy}, v});
		}
		REP(i, pat.size()) {
//			cout<<pat[i].ref<<" -> "<<pat[i].pos<<endl;
//			cout<<pat[i].ref.x<<" "<<pat[i].ref.y<<endl;
		}
		ll ans = 0;
		REP(pi, pat.size()) {
			auto& p = pat[pi];
			REP(x0, W) REP(y0, H) {
				int xx = x0+p.ref.x;
				int yy = y0+p.ref.y;
				if(IN_RANGE(xx, 0, W) && IN_RANGE(yy, 0, H)) {
					ll lans = 0;
					REP(i, p.pos.size()) {
						int ex = x0 + p.pos[i].x;
						int ey = y0 + p.pos[i].y;
						if(IN_RANGE(ex, 0, W) && IN_RANGE(ey, 0, H)) {
							lans += a[ex][ey]-'0';
						}
					}
					ans = max(ans, lans);
				}
			}
		}
//		cout<<"one "<<one<<endl;
		REP(x0, W) REP(y0, H) REP(x1, W) REP(y1, H) if(!(x0==x1 && y0==y1)) {
			int dx = x0-x1;
			int dy = y0-y1;
			PII k = MP(dx, dy);
			if(!ng.count(k)) {
//				cout<<x0<<" "<<y0<<" "<<x1<<" "<<y1<<" -> "<<one[x0][y0]+one[x1][y1]<<endl;
				ans = max(ans, one[x0][y0]+one[x1][y1]);
			}
		}
		return ans;
	}
};

2015-05-13

SRM 659 Div1 250 ApplesAndOrangesEasy

23:19 |  SRM 659 Div1 250 ApplesAndOrangesEasy - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 659 Div1 250 ApplesAndOrangesEasy - kojingharangの日記  SRM 659 Div1 250 ApplesAndOrangesEasy - kojingharangの日記 のブックマークコメント

  • GarthがN個のりんごかオレンジをある順序で食べた。そのうちいくつかのリンゴに関しては食べた番目が与えられる。
  • 連続する K 個の中で K/2 以下のりんごしか食べてない場合、りんごの最大個数を求めよ。
  • 2≦K≦N≦2000
  • dp? いや最後の K 個のパターンをキーにするにしては K が大きすぎる
  • 左から置けるとこに貪欲に置いてだめな理由もなさそうだ
  • おけるところをどうやって覚えておくか...
  • 直近 K 個の和を計算しておいて、それを配ってmaxを取っておいたものが K/2 より小さければ置けそうだ
  • めっちゃはまる
  • 終了間際 あれこれN^3だだめだ
  • (あとで)
  • 冷静に考えると置けるかの判定は K 個の sum を見て良くて、置いた時の sum の更新も K 回、全体で O(N^2) にすればよかったのだ
  • 置けるかチェック O(1) 更新 O(N^2) にしてしまっていた。
  • それか BIT を使って置けるかの判定にO(NlogN)、更新にO(logN)でもいい。
  • うむー全然だめだ。
  • accepted in practice
class ApplesAndOrangesEasy {
	public:
	int maximumApples(int N, int K, vector <int> info) {
		VI w(N), sum(N); // sum of [i-K+1, i]
		REP(i, info.size()) w[info[i]-1]=1;
		REP(i, N) RANGE(j, max(0, i-K+1), i+1) sum[i]+=w[j];
		ll ans=info.size();
		REP(i, N) if(!w[i]) {
			bool ok=true;
			RANGE(j, i, min(N, i+K)) if(sum[j]>=K/2) ok=false;
			if(!ok) continue;
			ans++;
			RANGE(j, i, min(N, i+K)) sum[j]++;
		}
		return ans;
	}
};

2015-05-05

Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった)

18:27 |  Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった) - kojingharangの日記 を含むブックマーク はてなブックマーク -  Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった) - kojingharangの日記  Google code jam 2015 Round1B C. Hiking Deer (Update: largeもやった) - kojingharangの日記 のブックマークコメント

  • シカとヒトN人が単位円上を1方向に歩く。シカのスタート時のヒトの初期位置と周期(定速で周る)が与えられる。
  • シカは任意の正の速度で移動できるとき、シカが1周するまでにすれ違うヒトの最少人数を求めよ。
  • 周期≦10^9 +α
  • Small1: N≦2 Small2: N≦10 Large: N≦500000
  • Small1 だけ。
  • 各ヒトに対して、シカがすれ違わずにゴールできる時刻の範囲が決まる。
  • 具体的には、シカのスタート後、そのヒトがシカのスタート地点を1回通過する時刻〜2回通過する時刻まで。
  • ヒト2人に対するその範囲の共通部分があれば 0 人にできる。共通部分がなければ最低 1 人とすれ違う必要がある。
  • Small2 以降は謎。時刻を決め打ちして云々的な?
  • Small1: Accepted
int main() {
	int test_cases;
	cin>>test_cases;
	ll N, D, H, M;
	string s;
	REP(ttt, test_cases) {
		cin>>N;
		vector<PII> w;
		REP(i, N) {
			cin>>D>>H>>M;
			REP(j, H) w.PB(MP(M+j, D));
		}
		sort(ALL(w));
		ll ft = w[0].first * (360 + 360-w[0].second);
		ll st = w[1].first * (360-w[1].second);
		ll ans = st>=ft ? 1 : 0;
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

(追記)

  • Large も基本的にヒト毎にすれ違い回数は独立に足せることを利用する。
  • 各ヒトについてすれ違い回数が 0, 1, 2, ... になるような時刻の区間が定まるので、それらをソートしておいて、すれ違い回数が変化するとこで変化させていく。
  • ...書いたが WA がとれないので SnapDragon さんのを動かしたりするぢっと見たりする
  • そうだ -1, +1 おわり ではなく -1, +1, +1, ... とどんどん増えていくのだ
  • まとめると
  • すれ違い回数の初期値は t=0 でゴールするときなので全員分
  • まだ考慮していない変化データとその時刻を priority_queue で管理して、変化分を足し込んでいく。
  • 見たら次周のために +1 なデータを push
  • すれ違い回数はいずれ単調増加になるので、人数を超えたあたりで適当に終了。念のため人数*2にしとく
  • はまりどころ
  • push の前で top を見てた
  • -1 が人数分出るまでループを回すと -1 が長い周期になっててループが10^9回くらいになる可能性があるのですれ違い回数で打ち切る必要がある
  • Small1, Small2, Large: Accepted in practice
int main() {
	int test_cases;
	cin>>test_cases;
	ll N, D, H, M;
	string s;
	REP(ttt, test_cases) {
		cin>>N;
		priority_queue<pair<ll, pair<ll, ll>>> q;
		ll all = 0;
		REP(i, N) {
			cin>>D>>H>>M;
			REP(j, H) q.push(MP(-(M+j)*(360-D), MP(-1, (M+j)*360)));
			all+=H;
		}

		ll ans = 1LL<<60;
		ll cur=all;
		while(q.size() && cur < all*2) {
			ll t = -q.top().first;
			ll dn = q.top().second.first;
			ll dur = q.top().second.second;
			q.pop();
			cur+=dn;
			q.push(MP(-(t+dur), MP(1, dur)));
			if(t != -q.top().first) {
				ans = min(ans, cur);
			}
		}
		ans = min(ans, cur);
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}