kojingharangの日記

SRM 650 Div1 250 TaroFillingAStringDiv1

20:01 |

• A,Bからなる長さ N の文字列を、隣接する２文字が同じような組の数が最小となるように作りたい。
• ただし、Pos[i] 番目の文字は Value[i] (0≦i＜M)でないといけない。何通り作れるか? mod 10^9+7で。
• 1≦N≦10^9, 0≦M≦50

• A_A なら ABA にするしかない。
• A_B なら AAB か ABB のどちらか。
• A__B なら ABAB しかない。
• A__A なら ABAA か AABA かな (あとで: 正しくは ABBA も含めた3通り)
• 端は常に１通り (__A は ABA)

• というわけで、全 X___(_がkコ)___Y について、X==Y かつ kが奇数なら 1 通り、そうでないときは 2 通り、X!=Yだったりkが偶数だったりしたら反転、でいいかな
• sampleより大幅に少ない場合がある
• A__A の場合は3通りか。
• 隣り合う文字が同じになる開始位置が k+1 コあるということか。
• 各 ___ について、(X==Y) ^ kが奇数 ? k+1 : 1
• →提出

• おお N は結局使わないのか
• Accepted

• sampleに救われたが本来そうであってはいけない ...けど結果オーライ

class TaroFillingAStringDiv1 {
	public:
	int getNumber(int N, vector <int> P, string S) {
		int M=P.size();
		vector<PII> w(P.size());
		REP(i, M) w[i] = MP(P[i], (ll)S[i]);
		sort(ALL(w));
		modll ans = 1;
		// # of cands in start and end interval is 1
		RANGE(i, 1, M) {
			ll gap = w[i].first - w[i-1].first - 1;
			int odd = gap & 1;
			int same = w[i].second==w[i-1].second;
			ll v = same ^ odd ? gap+1 : 1;
			if(gap) ans *= v;
		}
		return ans;
	}
};

ツイートする