COCI CONTEST #5

1時からSRMなので、20分遅れくらいで１時間半もないくらい適当に参加。英語が読みやすい。

Križaljka 50/50

問題文 : 単語A,Bが与えられるので、クロスワード作りなさい。

感想 : はい。細かい制約(何を優先するとか)全く読まずに投げたので落ちそうでしたが50点ありました。

解法(反転)：素直に実装する

Eko 80/80

問題文 : 10^6個くらい木があってそれぞれに長さがある。ある高さ(整数)で木を一括ｽﾊﾟｰﾝ！するとまあ上の部分だけ切れる。切った合計がある値以上にしたいけど、出来るだけ木を無駄に切りたくない。条件を満たす範囲で残った木の高さを最大にするときどの高さで切れば良いか。

感想 : これも適当にサンプル合うように書いただけなのになんか満点ありましたね。

解法(反転)：高さについて二分探索する。

DNA 80/100

問題文 : AとBからなる長さ10^6以下の文字列があります。次の２通りの操作が許されています→｛先頭から任意のｋ文字を一括して反転させる,ある任意の1文字を反転させる}。それぞれにかかるコストは１です。全てをＡだけの文字列にする場合のコストは最小でいくらか出力しなさい。

感想 : 思考フェイズが2~3分くらいだったので80点でした。悪くない。多分最初に全部反転させる場合のこと考えてないのかなぁ。分からん。とりあえず思いついた良さそうな方法を全て試して最小値とる戦略が良いかも。

解法(反転,部分点) : 戦略は出来るだけ先頭から連続している同じ文字を反転させまくる。とりあえずＢの最小個数を数えてＲ１とでもしとく。{AABAA}とか孤立してるやつBならA,AならBに反転したり前処理した上でAとB入れ替わってる数数えとく。最後がAなら(その数)-1,最後の文字がBなら(その数)そのままをR2とし、さっき数えたやつをそれに足す。min(R1,R2)を出力。unique()使うと連続したやつが消せて楽だった。

Razbibriga 120/120

問題文 : よくわかりませんが文字で正方形作るらしい。なんでサンプル１が２なのかも分からん。

感想 : 意味が分からなかったですがとりあえずサンプル通るプログラム投げたら満点でした。

解法(反転) : なぜ通るのかよくわからん。先頭の文字と後ろの文字で[26][26]の配列にメモった上で角の頂点を26^4で決めて数え上げ。被らないように、既にその組使ってたら1引いてやるとかしてうまくやる。64bitに収まるって保証されてるらしい。

Blokovi 0/140

問題文 : もう読みたくなかったので捨てました。なので分かりません。

感想 : 何をするのか分かりませんでした。

解法(反転,0点解法) : サンプル埋め込み。あとは1.0を出力するプログラムを書いて部分点を狙おうとしたらさすがに許されなかった。

Popločavanje 130/160

問題文: 長さ30万以下の文字列Sが与えられて、5000個の長さ5000以下のパターンが与えられる。文字列Ｓはパターンと完全に一致している部分をそのパターンで覆うことができて、どのパターンも何回でも使える。被ってても良い。そんなかんじに頑張ったときにいくつのタイルが結局覆われないか。

感想 : 適当な自明解法でここまで点数取れたのでいいです。

解法(反転) : 多分ahoとか使うとO(300000+5000^2)くらいになって良いんだろうナァと思いつつO(5000*300000)のロリハ採用、2ケースくらいTLEで駄目だった。通りそうな気がしたので。ロリハである位置から伸びるパターンで最大の長さを記録して、あとは一次元いもす(ただの端に+1,-1する累積和)して終わり。

ソースコード

1
char t[40][40] = {};

int main(){
	ios_base::sync_with_stdio(false);
	string x,y;
	cin >> x >> y;
	int H = y.size();
	int W = x.size();
	rep(i,40)rep(j,40) t[i][j] = '.';
	for(int i = 0 ; i < W ; i++){
		for(int j = 0 ; j < H ; j++){
			if(x[i] == y[j]){
				for(int w = 0 ; w < H ; w++)
					t[w][i] = y[w];
				for(int w = 0 ; w < W ; w++)
					t[j][w] = x[w];
				goto exit;
			}
		}
	}
	exit:;
	for(int i = 0 ; i < H ; i++){
		for(int j = 0 ; j < W ; j++)
			cout << t[i][j];
		cout << endl;
	}
}
2
long long v[1000000];
long long n,m;

long long f(long long a){
	long long ans = 0;
	for(int i = 0 ; i < n ; i++)
		ans += max(0ll,v[i]-a);
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i = 0 ; i < n ; i++) scanf("%lld",v+i);
	long long l = 0 , r = 2000000000;
	while(l!=r){
		long long mid = (l+r+1) / 2;
		//cout << mid << " " << f(mid) << endl;
		if( f(mid) >= m ) l = mid;
		else 			  r = mid-1;
	}
	cout << l << endl;
	
}
3

部分点なのでクソ

int main(){
	ios_base::sync_with_stdio(false);
	int du; cin >> du;
	string l;
	cin >> l;
	int R1 = count(l.begin(),l.end(),'B') , R2 = 0;
	for(int i = 1 ; i+1 < l.size() ; i++){
		if(l[i-1] != l[i] && l[i] != l[i+1]){
			l[i] = l[i-1];
			R2++;
		}
	}
	l.erase(unique(l.begin(),l.end()),l.end());
	R2 += l.size();
	if(l[l.size()-1] == 'A') R2--;
	cout << min(R1,R2) << endl;
}

4

どうしてこれで満点なんですか(正論)

int v[26][26];
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		string s;
		cin >> s;
		v[s[0]-'A'][s[s.size()-1]-'A']++;
	}
	long long ans = 0;
	for(int i = 0 ; i < 26 ; i++){
		for(int j = 0 ; j < 26 ; j++){
			
			for(int k = 0 ; k < 26 ; k++){
				for(int l = 0 ; l < 26 ; l++){
					long long RI = v[i][j];
					long long DW = v[j][k] - (i==j&&j==k);
					long long LE = v[l][k] - (i==l&&j==k) - (j==l&&k==k);
					long long UP = v[i][l] - (i==i&&j==l) - (j==i&&k==l) - (l==i&&l==k);
					ans += RI * DW * LE * UP;
				}
			}
		}
	}
	cout << ans << endl;
	
}
5

なし

6

定数改善してりゃ満点取れたかナァ。(追記:stringをchar*にしたら満点取れた)

int x[300010] = {};
int sum[300010] = {};
int main(){
	ios_base::sync_with_stdio(false);
	int n,m;
	cin >> n;
	string s;
	cin >> s;
	cin >> m;
	for(int i = 0 ; i < m ; i++){
		string t;
		cin >> t;
		ull pattern = 0;
		for(int j = 0 ; j < t.size() ; j++) pattern = pattern * 8999 + t[j];
		ull cur = 0 , pow = 1;
		for(int j = 0 ; j < t.size() ; j++) pow *= 8999;
		for(int j = 0 ; j < t.size() ; j++) cur = cur * 8999 + s[j];
		if(cur == pattern) x[0] = max(x[0],(int)t.size());
		for(int j = 0 ; j+t.size() < n ; j++){
			cur = cur * 8999 + s[j+t.size()];
			cur -= pow * s[j];
			if(cur == pattern) x[j+1] = max(x[j+1],(int)t.size());
		}
	}
	for(int i = 0 ; i < n ; i++){
		sum[i] += 1;
		sum[i+x[i]] -= 1;
	}
	int current = 0;
	int ans = 0;
	for(int i = 0 ; i < n ; i++){
		current += sum[i];
		if(current == 0) ans++;
	}
	cout << ans << endl;
}

全体感想

前回と比べると英語も問題もだいぶ易しかったのでは。