VK Cup 2012 Qualification Round 1

A.Next Round
問題文読めてないけど、通ってた。
k番目の値以上で且つ0じゃないものの個数を出力する。数字が減っていくが、無視して普通に数えても良い。

int n,k,t,p[51],res;

int main(){
	cin>>n>>k;
	for(int i = 0; i < n; i++){
		cin>>p[i];
		if(i == k-1) t = p[i];
	}
	if(!t)t++;
	for(int i = 0; i < n; i++){
		if(p[i]>=t) res++;
		else break;
	}
	cout<<res<<endl;
	
	return 0;
}

B.Taxi
適当に訳すと、
1，2，3，4人のグループがあって、グループを合成してもいいけど、分解してはいけない。このとき、4人乗りのタクシーが何台以上あれば、全部のグループをタクシーに乗せられるか
という問題。

Ⅰ.3人と1人を組み合わせる
Ⅱ.2人同士で組み合わせる
Ⅲ.2人と1人で組み合わせる
Ⅳ.1人同士で組み合わせる

とすれば、解ける。

int n,p[4],res;

int main(){
    cin>>n;
    for(int i = 0; i < n; i++){
        int a;
        cin>>a;
        p[a-1]++;
    }
    p[0] = max(p[0]-p[2],0);
    if(p[1]%2) p[0] = max(p[0]-2,0);
    p[1] = (p[1]+1)/2;
    p[0] = (p[0]+3)/4;
    
    for(int i = 0; i < 4; i++){
        res += p[i];
    }
    cout<<res<<endl;
    
    return 0;
}

C.Cd and pwd commands
文字列を追加したり、削除する問題。ターミナルとかコマンドプロンプトとかCygwinに触ったことがあれば、問題はすぐ分かる。

"pwd"が来たら、ただ表示するだけ。
"cd"が来た時、
最初が"/"の場合：ルートディレクトリに戻ってから、スラッシュ無しの場合の処理をする。
最初が"/"ではない場合：".."でなければ、そこに移動する(文字列を記憶しておく)、".."であれば、親ディレクトリに移動する(最後に記憶した文字列を削除する)

int Q;
string cmd;
vector<string> current;

int main(){
	current.push_back("");
	cin>>Q;
	while(Q){
		cin>>cmd;
		if(cmd[0] == 'p'){//pwdの場合
			int len = current.size();
			for(int i = 0; i < len; i++){
				cout<<current[i]<<'/';
			}
			cout<<endl;
		}else{
			cin>>cmd;
			if(cmd[0] == '/'){//最初にスラッシュが来る場合
				current.clear();
				current.push_back("");
				cmd.erase(cmd.begin());
			}
			int len = cmd.size(),pos = 0;
			while(pos<len){
				string s;
				while(cmd[pos]!='/'&&pos<len)s+=cmd[pos++];
				if(s[0]=='.' && s.size()==2 && s[1]=='.'){
					current.pop_back();
				}else{
					current.push_back(s);
				}
				pos++;
			}
		}
		Q--;
	}
	return 0;
}

D.Ice Sculptures
多角形作って、頂点にある数字の和が最大になるものを求める。
nの約数を全て求めて、全探索してます。1だけ特別扱いしてますが、しなくても少し遅くなるだけです。

int s[1000][20000],res;//nの約数の個数は最大で80個なので、s[80][20000]でも通る
int n;
vector<int> p;

int main(){
	cin>>n;
	for(int i = 2; i <= n/3; i++){
		if(!(n%i))p.push_back(i);
	}
	int len = p.size();
	
	for(int i = 1; i <= n; i++){
		int a;
		cin>>a;
		res+=a;
		for(int j = 0; j < len; j++){
			s[j][i%p[j]]+=a;
		}
	}
	for(int i = 0; i < len; i++){
		for(int j = 0; j < p[i]; j++){
			res = max(res,s[i][j]);
		}
	}
	cout<<res<<endl;
	
	return 0;
}

E.Phone Talks
電話がn回かかってきて、k回無視する。最初の日に、(連続して)電話が掛かってきていない時間の最大値を求める。

DPらしいですが、コード見てもよく分かりませんでした。いつか解きたい…
追記:問題文を誤読していたようでした。電話が終わる時間を記録していけば普通に解けます。

500 + 0 + 1000 + 1400 + 0
1777th

Qualification Round 2で何とかがんばります