Codeforces Round#4 beta (div2 only)

Codeforces 参加記録

参加してきた。
今回も４問セット。

A

ある数n（≦100）が2つの偶数の和で表せるならYES、そうでないならNOを出力せよ。


偶数+偶数=偶数だから偶数なら表せるのかな？あ、でもn=2の時だけは例外。
一応n=100だし全探索のほうが間違いがないから全探索で書こう。


→Presentation Error→え？あ、デバッグコード（複数ケース入力用）消してないorz→AC

B

queueが大分混んでてロスったなあ……などと思いつつ問題文を読む。


d日後の試験までにsumTime時間勉強したい。
i日目に勉強できる量はminTime[i]以上maxTime[i]以下である。
このときsumTime時間勉強できるならYESと、その次の行に毎日の勉強時間をスペースで区切って、そうでないならNOを出力せよ。


グリーディでOKだよね。→AC

C

ユーザID登録システムを作りたい。n個の名前の入力が与えられる。
それまでに同じ名前が登録されていなかったらOKを、登録されていたらその名前の後に数字（1から始めて初めて重複がなくなる番号）をつけたものを出力せよ。


えーと？名前の最後の文字が数字だったらちょっと面倒か？
setに使った名前を入れておいて、番号がなかったらOKを出力、
今の名前が見つかったら、番号を足していってsetに含まれていないとこまで行ったら名前+その数字を出力でおｋだな。


送信。queueが全然処理されてない。仕方ないのでDを読む。

D

問題文の意味が全然理解できない。
15分くらい読み返してようやくああ、マトリョーシカみたいなものを作るんだと把握。
こんな問題Aizu Online Judgeで解いたことあったなあ。DPでおｋ。


書く→送る→例によって全然処理されてない


あれ、CがWrong Answer出てる？
あ、使った名前setに登録してない……修正してResubmit.


残り1時間弱あったがqueueが全然処理されないので諦めてゲームをはじめる。

結果

CがTime Limit Exceeded,DはWrong Answerだったorz
レートは更に下降。


queueが混んでたことで、問題を正確に読む能力の欠如が凄くわかりやすい形で出てくれた。ほんと勉強になります。
もっともっと頑張ろう……

後日

翌日解き直してみたところCは問題文に「名前は小文字のアルファベットのみ」という条件がorz


あ……はい……普通にmapで数えろってことね……


Dは封筒の入れ子はおろか、「カードすら封筒に全く入れられない」という場合がテストケースにあった模様。
そこでWAになっている。問題文にｶｲﾃﾅｲﾖ……←書いてあんだろうが！死ねよ！

int dp[6000],parent[6000];

void run()
{
	int n,w,h;
	cin>>n>>w>>h;
	
	vector<vi> env;
	int m=0;
	rep(i,n)
	{
		vi v(3);
		cin>>v[0]>>v[1];v[2]=i+1;
		
		if(v[0]<=w||v[1]<=h)continue;
		m++;
		env.pb(v);
	}
	
	if(env.empty())
	{
		cout<<0<<endl;
		return;
	}
	sort(all(env));
	
	rep(i,m)dp[i]=0,parent[i]=-1;
	rep(i,m)
	{
		int mx=0,mxi=-1;
		rep(j,i)if(env[i][0]>env[j][0]&&env[i][1]>env[j][1])
		if(mx<dp[j])
		{
			mx=dp[j];
			mxi=j;
		}
		dp[i]=mx+1,parent[i]=mxi;
	}
	
	vi ans;
	int ansi=max_element(dp,dp+m)-dp;
	for(int p=ansi;p!=-1;p=parent[p])
		ans.pb(env[p][2]);
	reverse(all(ans));
	
	cout<<ans.size()<<endl;
	rep(i,ans.size())
	{
		cout<<ans[i];
		if(i==ans.size()-1)cout<<endl;
		else cout<<" ";
	}
}

(Dのソース。ヘッダ等省略)