kojingharangの日記

Facebook hacker cup qualification B. Balanced Smileys

22:35 |

• [a-z: ()] からなる文字列が与えられる。":)" と ":(" はそれ単体で１文字ともみなせる。カッコの対応が合う解釈があるかどうかを YES NO で答える問題。
• |文字列|≦100

• スタックとか使うのか？いやなんかいろいろ反例があって failed system test になりそうなので大変きな臭い。大変きな臭い。
• 手堅く区間DPでやろう
• 問題文から以下の定義になる

BalancedParentheses ::=
	  Empty
	| [a-z: ]
	| :)
	| :(
	| ( BalancedParentheses )
	| BalancedParentheses BalancedParentheses

• ので、始点 S 終点 E で表される長さ L の部分文字列 s が与えられた時、それが BalancedParenthesis かどうかを定義通りに求める。
• これをすべての S, E に対して行う。ただし L が小さい順にやる。

• Accepted

int main() {
	int T;
	cin>>T;
	cin.ignore();
	REP(ttt, T) {
		string s;
		getline(cin, s);
		
		int N=s.size();
		VVI dp(N, VI(N+1));
		REP(S, N) dp[S][0]=1;
		
		RANGE(L, 1, N+1) {
			REP(S, N) {
				int E=S+L-1;
				if(E>=N) continue;
				
//				cout<<s.substr(S, L)<<endl;
				
//				cout<<S<<" "<<L<<endl;
				if(L==0) dp[S][L]=1;
				if(L==1 && (s[S]==' ' || s[S]==':' || ('a'<=s[S] && s[S]<='z'))) dp[S][L]=1;
				if(L==2 && (s.substr(S, L)==":)" || s.substr(S, L)==":(")) dp[S][L]=1;
				if(L-2>=0 && s[S]=='(' && dp[S+1][L-2] && s[E]==')') dp[S][L]=1;
				if(L-2>=0) {
					RANGE(l, 1, L) if(dp[S][l] && dp[S+l][L-l]) dp[S][L]=1;
//					RANGE(l, 1, L) assert(0<=S && S<N && S+l<N && 0<L-l && L-l<=N);
				}
			}
		}
		
		cout<<"Case #"<<ttt+1<<": "<<(dp[0][N]?"YES":"NO")<<endl;
//		break;
	}
	return 0;
}

ツイートする

Facebook hacker cup qualification C. Find the Min

22:35 |

• m[0] = a, m[i] = ( b * m[i-1] + c ) % r (0＜i＜k), m[i] = m[i-k]からm[i-1]までに含まれない0以上の数(k≦i) のとき、m[n-1] を求める問題。
• 1≦k≦10^5, k＜n≦10^9, 0≦a,b,c≦10^9, 1≦r≦10^9

• うゲェ

• 小さいのから埋めてくのでm[k]からm[2k]は0〜kが重複なくふくまれる
• その後、m[2k+1] を求めるにあたって直前の k 個は 0〜kが重複なく含まれるとこから m[k] が抜けたものなので、そこに含まれないのは m[k] となり、
• 結局 m[2k+1]==m[k] になるというふうにして以下繰り返すので、m[i] の値としては k+1 周期になる。ある程度進んだあとに (n-1-i)%(k+1)==0なる i で打ち切る。
• ということで、ある程度m[i]の値を求める部分を工夫して速くすればいい
• 「m[i-(k-1)]からm[i]までに現れる数字→その個数」という配列を用意して１こ進める度に更新してく
• 次の数字はO(k)で探す

• accepted

• 気づかなかったけど O(k^2) なので実は危なかったのでは

int main() {
	int T;
	cin>>T;
	REP(ttt, T) {
		ll N,K,A,B,C,R;
		cin>>N>>K>>A>>B>>C>>R;
		
		VI w(K);
		w[0] = A;
		RANGE(i, 1, K) {
			w[i] = (B * w[i - 1] + C) % R;
		}
		VI ww(K+2); // [0, K+2)
		REP(j, K) if(w[j]<ww.size()) ww[w[j]]++;
		
		ll ans = -1;
		RANGE(i, K, N) {
			ll nxt = -1;
			REP(j, ww.size()) {
				if(ww[j]==0) {
					nxt = j;
					break;
				}
			}
			assert(nxt!=-1);
			
			int rm = w[i%K];
			if(rm<ww.size()) ww[rm]--;
			
			int add = nxt;
			if(add<ww.size()) ww[add]++;
			
			w[i%K] = nxt;
			
//			if((N-1-i)%(K+1)==0) {
//				cout<<i<<" "<<nxt<<endl;
//			}
			ans = nxt;
			if(5*K<N && (N-1-i)%(K+1)==0) break;
		}
		
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
//		break;
	}
	return 0;
}

ツイートする