Codeforces #71 Div1

と思ったらkyuridenamidaになってた。

開始前 いつものようにCFのサイトにそのコンテスト用の記事が出来る。

読む。

→「Today I(ir5) and rng_58 are the authors of Codeforces Beta Round #71.」

→日本人やん！！！！！！！１

→最近英語読めてなかったので嬉しいなって。

00:00 A読む

→ゲーム・・・Nimったりするの？(前回Div2のCがゲームだったので脳内がざわつく)

→ん？シミュレーションするだけ？

→実装しようとする。簡単すぎるからコーナーケースによるWA地獄を警戒する。

→適当に実装。あれ、これ取り方複数あるよね。どうするんだろう。

→ああ、Cielの時とHanakoの時でどう取るのか決まってるのか。

00:09 A passed pretest.

通った・・・。WAしなくて本当に良かった・・・。

不安なので{0,0}ケースどうするの？とかどうでもいいClarを投げて落ち着く。

2分後くらいに返事が返ってくる。"Hanako"らしいので、安心してLockする。

少しだけルームの人で怪しいのを探すが、さすがに見つからず。

00:13 B読む

うーん・・・よく分からない。。

→悩む。

→図を見る。理解する。

→なるほど、「その座標までにある障害物の数だけズレる」+「一次元で考える」か。

→二分探索は面倒くさい・・・。O(t log k)→O(t * k)になるだけだ。しなくても間に合う。

→実装する。障害物の数カウント回りにバグが無いか考える。

→思いつかないのでとりあえず全部long longにして提出。

00:24 B Wrong answer on pretest 4

ちょ・・・。何があったし。

→まさかのWAに不安になる。

→あー、障害物の座標が全部クエリ座標より小さい時ダメやん・・・。

→修正して、他にバグ無いか考えるけど思いつかないので提出。

00:26 B passed pretest.(1WA)

通って良かったああああ。もう大丈夫そうなので、ロックする。

→Hackしようかなーと思いつつも提出者1人しかいないし、正しい解法っぽい。

→Cを少しだけ読むけどよく分からない。

→AのHackをがんばろうとするけど見つからず。

→辛いぞサム。

00:30 C本格的に読む。

むむむむ・・・・よく分からない。

→分かったかも。

なんか100万文字以下の長い文S覚えたい。

でも覚えたくない嫌いな単語がいくつかある。(単語は10個以下で、それぞれ10文字以下)

その単語が含まれないようにSから連続した出来るだけ長い文字列S'を取り出したい。

って問題ぽい。

→実装がパッと浮かばない。文字列探索系苦手。DP?悩む。

00:55

→むううう・・・分からない！

→と思ったらPCがフリーズして動かなくなる。

→物故割れたあわわわわわわわわわわ

→電源を切る。

01:00

電源入れても未だに起動しない・・・。死んでそうな怪しいHDDとか外すけどダメ。

→Macbookとか持ってくる。

→突然Cを解くための鍵的なものを思いつく。

→長さの最大は10なので、確定(?)してる中で直前10文字からだけ比較すればよいし、尺取法だ！

→PC復旧に本気出す。

01:10 PCやっと起動

時間置いてやったらなぜか起動してテンション上がる。

→実装開始だ！！

→実装できたけどバグりまくっている・・・。

→デバグがんばる。自前のテストとか試しまくる。

→よし！全部通る！提出や！

01:27 提出するためCodeforcesを開く

また画面が真っ白になってフリーズする。顔面ブルーレイ。

→また電源切ったけど再び起動しないよ・・・。

→涙が出そうになりながら1分くらい放置して電源ボタンを押す。

→今度は起動してくれる。テンション上がる。

01:33 C passed pretest.

通ったあああああああああ。

→もういいや。いつフリーズするか分からないしそもそもD提出者少なすぎ、Hackがんばろう。

→B、intだと算術オーバーフローしねえかな。

→40000^2 = 16億　なのでしません。ちくしょう値設定！

→A、愚直にやるとTLEしないかな？

→ちくしょう！x,y共に100万以下だからしない！

→むり。

02:00 お　わ　り

結局誰もHack出来ず終了。順位はこの時点で200位台と可もなく不可もなくな感じ。

Div2は30位台で、落ちないことだけ祈ってました。

System test

ooo-- , A,B,C全部通る。

Cをみんなが落としている。何があったというんだ。

Result

[A]482(00:09)

[B]846(00:26)

[C]942(01:33)

2270 Pts.

全体で142位,Div2で16位(←何があった。)

Rate:1515→1705(+190)

うれしい、Div1はレート変わりまくるから良い。最近Div2は厳しすぎます。

感想

• 実装が相変わらず遅すぎる。
• 日本人writer楽しかった。
• id:JAPLJがACRushとタイの5位とかでやばすぎた。
• chronotableさんが悲惨な事故(System testに通るコードがHackされる)によりCを落としていた。
• AからCだけの難易度で言えば、前回のDiv2より簡単だった。(前回が明らかに高すぎた)

ソースコード

最高に汚い。

A

英文を正確に読み取る能力が求められました。

int main(){
	int n,m;
	bool turn = 0;
	cin >> n >> m;
	while(1){
		if(turn == 0){
			if(n>=2 && m >= 2){
				n -= 2;
				m -= 2;
			}else if(n >= 1 && m >= 12){
				n -= 1;
				m -= 12;
			}else if(m >= 22){
				m -= 22;
			}else{
				break;
			}
		}else{
			if(m >= 22){
				m -= 22;
			}else if(n >= 1 && m >= 12){
				n -= 1;
				m -= 12;
			}else if(n>=2 && m >= 2){
				n -= 2;
				m -= 2;
			}else{
				break;
			}
		}
		turn = !turn;
	}
	cout << (turn ? "Ciel" : "Hanako") << endl;
}

B

1回のクエリでO(k)なので全体でO(t * k)。

与えられた座標の前にいくつ障害物あるかは二分探索を用いるとO(log k)に出来るけどしませんでした。

int main(){
	int w,h,k,t;
	string table[] = {"Carrots","Kiwis","Grapes"};
	cin >> h >> w >> k >> t;
	vector<ll> data;
	rep(i,k){
		ll a,b;
		cin >> a >> b;
		a--,b--;
		data.push_back(w * a + b);
	}
	sort(data.begin(),data.end());
	rep(yy,t){
		ll a,b;
		cin >> a >> b;
		a--,b--;
		ll x = w * a + b;
		if(binary_search(all(data),x))cout << "Waste" << endl;
		else{
			rep(i,data.size()){
				if(x < data[i]){
					cout << table[(x-i) % 3] << endl;
					goto end;
				}
			}
			cout << table[(x-data.size())%3] << endl;
			end:;
			
		}	
	}
}

C

前処理も尺取法の部分も大体、O(s.length() * n * [単語の長さ] )くらいです。

int dp[10][100000]={0};
int main(){
	ios_base::sync_with_stdio(false);
	string S;
	vector<string> data;
	cin >> S;
	int L = S.size();

	int n;
	cin >> n;
	rep(i,n){
		string t;
		cin >> t;
		data.push_back(t);
	}
	
	// dpと書いているけどdpではなく、Sに単語iが含まれているなら、そのマッチングしはじめる先頭の位置だけメモっている(?)。
	rep(i,data.size()){
		rep(j,L-(int)data[i].size()+1){
			bool f = true;
			rep(k,data[i].size()){
				if(S[j+k] != data[i][k]){f = false;break;}
			}
			if(f) dp[i][j] = true;
		}
	}
	
	int l = 0 , r = 0 , ans = 0 , ans2 = 0;
	
	//尺取法っぽいこと
	while(l < L && r < L){
		if(l <= r){
		
			// 今lとrで持っている範囲がvalidなものかを判定(与えられた嫌いな単語を含んでいないかどうか)
			bool f = true;
			rep(i,data.size()){
				rep(j,data[i].size()){
					if(r-j >= l && (r-j)+data[i].length()-1 <= r && dp[i][r-j] == true){
						f = false;
					}
				}
			}
			
			if(f){
				if(r-l+1 > ans){
					ans = r-l+1;
					ans2 = l;
				}
				r++;
			}else l++;
			
		}else{
			r++;
		}
	}
	cout << ans << " " << ans2 << endl;
}