Hatena::Grouptopcoder

思考錯誤 - By evima

プログラミングコンテスト参戦記。本番中のメモを公開します
過去のコンテストへの出題一覧 / TopCoder / Codeforces / Twitter

2013-10-25

SRM 595

23:21

きちんと反省する必要を感じたので、今後Div1コンテストはできる限り記事にします。


SRM 595 (Div. 1)

【Easy (250) - LittleElephantAndIntervalsDiv1】

[概要] ボールがM個一列に並んでいる。最初はすべて白である。
ペア(L[i],R[i])がN個与えられ、N回操作を行う。
i回目の操作では、"黒""白"かを選び、L[i]からR[i]番目までのボールを選んだ色に変える。
何通りの最終結果を得られるか。
- M <= 1000, N <= 50
  • さすがにやるだけでは…
    • 答え:2^(最終結果に影響を及ぼす操作の数)
  • 最近結構神経を使うEasyが多い気がするけど、これは"トゲ"がなさすぎる
  • なんか罠にひっかかってないか?
    • サンプル通った…まあたまにはこのくらい簡単な問題も出るよね
  • 3:48.556 → 245.60 / 250 (16位 / 正解310人, 全体410人)

本番での提出コード:

#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define sz(x) ((int)(x).size())

int col[1010];

long long LittleElephantAndIntervalsDiv1::getNumber(int M, vector<int> L, vector<int> R){
	fill(col,col+M,-1);
	int n=sz(L);
	rep(i,n){
		L[i]--;R[i]--; // SRMで 1-indexed とかやめてください…
		rep2(j,L[i],R[i]+1){
			col[j]=i;
		}
	}
	set<int> S;
	rep(i,M){
		if(col[i]!=-1){
			S.insert(col[i]);
		}
	}
	return 1LL << sz(S); // 最大の難関。1 << sz(S) と書くとマイナス245点
}

【Medium (500) - LittleElephantAndRGB】

[概要] 'R','G','B'からなるN文字の文字列Sと、整数minGreenが与えられる。
S[a..b] + S[c..d] が部分文字列として"GGG...G"('G'がminGreen個)を持つような、
整数の組(a,b,c,d)の個数を求めよ。ただしa<=b, b<c, c<=dとする。
- N, minGreen <= 2500
  • 本番中のメモ:

1/2 (上部はEasy)

f:id:evima:20131025225704j:image

2/2

f:id:evima:20131025225703j:image

  • 「S[a..b] + S[c..d] にGがm回連続で現れる」とは、次のうちどれか1つ以上が成り立つこと
    • 条件A: S[a..b]にGがm回連続で現れる
    • 条件B: S[c..d]にGがm回連続で現れる
    • 条件C: S[a..b]の終わりの部分と、S[c..d]の始めの部分をつなげるとGがm回連続で現れる
  • ここまではよかったが…
  • 次に「#(AorBorC) = #(A)+#(B)+#(C)-#(AandB)-#(BandC)-#(CandA)+#(AandBandC)」と
    7つの問題に分解するという奇行に走って大量のタイムロス
    • 7個の小問題はかなり性質が異なり、1つ解ければ全て解けるというものではない。
      なんでこんな方法で解こうと思ったんだろう…
  • 単純に「(a,b)のペアはO(n^2)個だから、
    事前計算を頑張って各(a,b)に対応する(c,d)の数をO(1)で求める」などとすればいい
    • (a,b)を固定すれば、条件Aが満たされるかどうかは(c,d)によらず確定するので、
      残り2つの条件をみればよく、分解しても7つではなく3つで済む
  • 58:39.546 → 199.18 / 500 (52位 / 正解60人, 全体410人)

本番での提出コード:

#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define sz(x) ((int)(x).size())

int n,a[2510],m; // m: minGreen
int right1[2510][2510]; // 左端がi以降にある、ファーストコンボがj以上の区間の数
int right2[2510]; // 左端がi以降にある、マックスコンボがm以上の区間の数
int right3[2510][2510]; // 上2つの条件を両方満たす区間の数
// 合計48MB程度 / 64MB(実質52MB?)

void init(){ // (c,d)の値を(0,0),(0,1),...,(n-1,n-1)の順にすべてチェックし、right1,2,3を埋める
	rep(i,n){ // [c,d] の c
		int firstG=0; // 「ファーストコンボ」
		int maxG=0; // 「マックスコンボ」
		int curG=0; // 現在の「コンボ」
		int fail=0; // 一度でもG以外が現れたらファーストコンボ終了
		rep2(j,i,n){ // [c,d] の d
			if(a[j]==1){ // G
				curG++;
				maxG=max(maxG,curG);
				if(!fail){
					firstG=curG;
				}
			}
			else{ // G以外
				fail=1;
				curG=0;
			}
			// 条件を満たしていればカウント(後で"○○以上"の値に変換する)
			right1[i][firstG]++;
			if(maxG>=m){
				right2[i]++;
				right3[i][firstG]++;
			}
		}
	}
	// iについて"折りたたみ"、「左端がiであるような~」を「左端がi以降であるような~」に変換
	rep(j,n){
		for(int i=n-1;i>=0;i--){
			right1[i][j] += right1[i+1][j];
			right3[i][j] += right3[i+1][j];
		}
	}
	for(int i=n-1;i>=0;i--){
		right2[i] += right2[i+1];
	}
	// jについて"折りたたみ"、「ファーストコンボがjであるような~」を「ファーストコンボがj以上であるような~」に変換
	rep(i,n){
		for(int j=n-1;j>=0;j--){
			right1[i][j] += right1[i][j+1];
			right3[i][j] += right3[i][j+1];
		}
	}
	//rep(i,n)rep(j,n)cout<<i<<" "<<j<<" "<<right[i][j]<<endl;
}

long long LittleElephantAndRGB::getNumber(vector<string> list, int G){
	m=G;
	string str="";
	rep(i,sz(list))str += list[i];
	n=sz(str);
	rep(i,n)a[i] = str[i] == 'G'; // Gを1、他を0に
	
	memset(right1,0,sizeof(right1));
	memset(right2,0,sizeof(right2));
	memset(right3,0,sizeof(right3));
	init();
	
	ll ans=0;
	// (a,b)の値を(0,0),(0,1),...,(n-1,n-1)の順にすべて試す
	rep(i,n){ // [a,b] の a
		int firstG=0; // ここからinitのコピー
		int maxG=0;
		int curG=0;
		int fail=0;
		rep2(j,i,n){ // [a,b] の b
			if(a[j]==1){
				curG++;
				maxG=max(maxG,curG);
				if(!fail){
					firstG=curG;
				}
			}
			else{
				fail=1;
				curG=0;
			} // ここまでコピー
			
			if(maxG >= m){ // 左でmコンボ成立
				ans += (n-1-j) * (n-1-j+1) / 2; // 右はjより右のn-1-j個から選べば何でもいい
			}
			else{ // 左でmコンボ不成立
				ans += right1[j+1][m-curG]; // 右のファーストコンボがm-(左のラストコンボ)以上
				ans += right2[j+1]; // 右のマックスコンボがm以上
				ans -= right3[j+1][m-curG]; // 両方満たすもののダブルカウントを除く
			}
		}
	}
	
	return ans;
}

【Hard (900) - Constellation】

[概要] 平面上にN点がある。この平面を一度だけ観察する。
各点の座標と、それが見える確率が与えられる。見える点の凸包の面積の期待値を求めよ。
- N <= 50, -100 <= 各x,y座標 <= 100, 各確率: 0/10001000/1000
  • 普段のHardより簡単そうだが残り10分では何もできない…

【Challenge Phase~】

  • 部屋内の自分以外の提出数: Easy15, Medium6, Hard1
  • Easyをレートが低い順に見ていく
    • long longを使い忘れていてもサンプルは通ってしまうが、誰一人として忘れていない
  • けっこう名前を見かけるltaravilseさん(アルゼンチン)がC++vectorの範囲外参照をしている
    • が、他の人のチャレンジに耐えている
  • 唯一Blue.Maryさん(中国、ターゲット経験者)がDPをしているが、どうせ合っているだろう
  • 何もせず終了
  • チャットでの会話:
    • ltaravilseさん「(Adminに向けて)落ちるEasyが1個もない :(」
    • mystic_tcさん(Admin)「システスト後もそのままだと思いますか? ;)」
  • …がなんとltaravilseさんのEasyは通り、落ちたのはBlue.MaryさんのEasyだった
  • 部屋の様子
  • 自分の結果: 45位/410, 2370→2380 (+10)
    • 微妙…あと50点で31位で、それなら(小)勝利
  • Blue.MaryさんのEasy、一見正しそうだがよく考えると…
    • 例えばM=3で1~3を塗った後2~2を塗る場合に8が返ってくる
    • 青か黄色の人だったら疑ってたんだけどな…まあ仕方ないか

教訓: 全探索できるところまで全探索

To be continued.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/evima/20131025