Hatena::Grouptopcoder

思考錯誤 - By evima

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

2013-12-23

SRM 601

00:24

長かった…


SRM 601 (Div. 1)

【Medium (500) - WinterAndSnowmen】

[概要] 整数N,Mが与えられる。集合{1,2,...,N}の部分集合Sと集合{1,2,...,M}の部分集合Tの組(S,T)であって、
次の条件をともに満たすものの個数をmod 107で求めよ。
・SとTは共通の要素を持たない
・(Sの全要素のxor sum) < (Tの全要素のxor sum)
- N,M <= 2000
  • ここ数回はコンテスト中にMediumから開いていた
    • Mediumから開くと、Mediumが終わった後で他の人のEasyのパフォーマンスを見てからEasyに臨める
      • みんな遅いときは焦らず確実に、みんなが速いときは急ぐ、ということができる
  • 本番中のメモ:

1/2

f:id:evima:20131224002157j:image

2/2

f:id:evima:20131224002156j:image

  • 考えたことはおおよそこのメモの内容に尽きる
    • 1~max(N,M)を1個ずつ処理していって「set1のxor sum」「set2のxor sum」を覚えておく普通のDPでも
      そこまで計算量が多すぎないので、これを改善する方針で
    • 10回ほど前のDiv1 MediumにもXorと数の大小に関する数え上げの問題(SRM591: XorCards)が出題されていて、
      そこでのポイントの1つが「どの桁で2つの数の大小が決まるか」を1つずつ試すことだった。今回も適用してみる
      • すると上の方の桁で大小がつくケースはそのまま「set1のxor sumの上の方」「set2のxor sumの上の方」を覚えることで
        十分速く求まってしまう。問題は下の方の桁で大小が決まるとき。なんとかして覚える情報を減らさなければならない
    • オチは単純で、「xorSum(set1)の上の方」「xorSum(set2)の上の方」を両方覚えるのはよく考えると無駄
      • 例えば上から8桁目で大小が決まるとき、「xorSum(set1)の最上位の桁が0で、xorSum(set2)の最上位の桁も0」という状態と
        「xorSum(set1)の最上位の桁が1で、xorSum(set2)の最上位の桁も1」という状態を区別する必要はあるか?ない。
        この2つの桁は最終的に等しくならなければならないが、逆にいえば同じでありさえすればよいので…
    • ということで「xorSum(set1)の上の方」「xorSum(set2)の上の方」の代わりに
      「(xorSum(set1)の上の方) xor (xorSum(set2)の上の方)」(xorが0なら2つの桁は等しく、1なら異なる)と
      「(xorSum(set1)の大小が決まる桁の値)」を覚えればよい
  • 解法が分かれば実装は平易
    • …なはずだが、Flying Table (dp[2][?][?]...の先頭の0と1をフリップしてメモリを節約する技)を使うのが久しぶりだったせいか
      「フリップ直後にテーブルを0に初期化するのを忘れる」という失敗のため、coutデバッグで10分ほど(?)ロス
      • そもそもメモリ制限が256MBになったのでFlying Table自体不要なのに!こういうのをなくさないと…
  • 51:04.075 → 212.10 / 500 (49位 / 正解55人, 全体767人)
  • xorの問題で「xorをとる」ことが決定的なポイントになる、という面白い問題だった
#define MOD 1000000007LL
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)

ll dp[2][1<<11][2][2];

#define modAdd(x,y) (x)+=(y); if((x)>=MOD)(x)-=MOD // 多少危なっかしいマクロだが変な使い方をしなければいいはず…

int WinterAndSnowmen::getNumber(int N, int M){
	ll ans = 0;
	int L = max(N, M);
	
	rep(d,11){ // 下からd桁目で大小が確定するとき
		//cerr << "d: " << d << endl;
		memset(dp,0,sizeof(dp));
		int cur = 0, pre = 1;
		int D = 11 - d; // 上部11-d桁だけが重要で、差がついた後の下部d桁はどうでもいい
		dp[cur][0][0][0] = 1;
		rep2(i, 1, L+1){ // 数を1つずつ処理
			swap(cur,pre);
			int upper = i >> d; // 上部11-d桁
			int upper0 = i >> d & 1; // …の一番下の桁
			
			rep(xorSum, 1<<D)rep(xorA0,2)rep(xorB0,2){
				dp[cur][xorSum][xorA0][xorB0] = 0; // これを忘れたせいでcoutデバッグ
			}
			
			rep(xorSum, 1<<D)rep(xorA0,2)rep(xorB0,2){ // 1ビット分余計
				modAdd(dp[cur][xorSum][xorA0][xorB0],dp[pre][xorSum][xorA0][xorB0]); // iをset1にもset2にも入れない
				if(i <= N){
					modAdd(dp[cur][xorSum^upper][xorA0^upper0][xorB0],dp[pre][xorSum][xorA0][xorB0]); // iをset1へ
				}
				if(i <= M){
					modAdd(dp[cur][xorSum^upper][xorA0][xorB0^upper0],dp[pre][xorSum][xorA0][xorB0]); // iをset2へ
				}
			}
			
			/*rep(xorSum, 1<<D)rep(xorA0,2)rep(xorB0,2){ // N = M = 3のケースでcoutデバッグ (1,2のときは問題が起きない…)
				if(dp[cur][xorSum][xorA0][xorB0])cerr << i << " " << xorSum << " " << xorA0 <<" " << xorB0 << ": " << dp[cur][xorSum][xorA0][xorB0] << endl;
			}*/
		}
		//cerr << d << ": " << dp[cur][1][0][1] << endl;
		ans += dp[cur][1][0][1]; // 上部の桁がd桁目以外一致して(xorSum:1)、d桁目はset1が0(xorA0:0)でset2が1(xorB0:1)ならOK
	}
	
	return ans%MOD;
}

【Easy (250) - WinterAndPresents】

[概要] N個のバッグがあり、i個目には互いに区別できないりんごapple[i]個とみかんorange[i]個が入っている。
次の操作の結果得られる「プレゼント」は何通りか。
1. 正整数Xを選ぶ。ここでどのバッグにも合計X個以上果物が入っていなければならない。
2. 各バッグから果物をX個取り出し、すべてのバッグから取り出した中身をまとめて「プレゼント」とする。
- 1 <= N <= 50, 0 <= apple[i], orange[i] <= 100
  • 本番中のメモ:

f:id:evima:20131224002155j:image

  • 手で解く、やったことをC++で書く、終わり。
  • 固定するべき変数「X」が問題文に堂々と出現するのでEasyの中でも特に易しい部類の問題だと思うが、
    難しめのMediumを解いた直後だからか問題の理解などに妙に時間がかかってしまった
    • Mediumから開いた目的は上述の通り「Easyの難易度を知った上で臨む」ことだが、最近は恐れるべきEasyが全然現れず、
      Easyから開く利点(元気な状態でEasyを開く→すぐ通す→調子に乗った状態でMediumを開ける)の方が大きそうなので、
      次回からはまたEasyから開くことにする
  • 7:14.592 → 235.07 / 250 (52位 / 正解590人, 全体767人)
    • Mediumよりこっちの方が点が高くて悲しい…
#define INF 1070000000LL
#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())

long long WinterAndPresents::getNumber(vector<int> apple, vector<int> orange){
	int n=sz(apple);
	vector<int> total;
	rep(i,n){
		total.pb(apple[i] + orange[i]);
	}
	int smallest = INF;
	rep(i,n){
		smallest = min(smallest, total[i]);
	}
	ll ans=0;
	rep2(num,1,smallest+1){
		int mi = 0, ma = 0; // apple
		rep(i,n){
			if(num <= orange[i]){
				mi += 0;
			}
			else{
				mi += num - orange[i];
			}
			
			if(num <= apple[i]){
				ma += num;
			}
			else{
				ma += apple[i];
			}
		}
		ans += ma - mi + 1;
	}
	return ans;
}

【Hard (950) - WinterAndShopping】

  • 一応開いておくが、残り時間が15分しかない上部屋の誰も提出する気配がないので無視

【Challenge Phase~】

  • 部屋内の自分以外の提出数: Easy17, Medium1, Hard0
  • 時間ギリギリに提出された2つのEasy(青)を見る。1つは明らかにおかしそう
    • nで割り算していたりして、何を計算しているのか全く分からない
  • …が、"<="を"<"と取り違えて簡単なケース({0},{998283})でチャレンジして失敗し、
    手元で同じことをするコードを書き始めたところでとられた
    • 用意しておいた大きなケースでよかったのに…差し引き-75点
  • もう一つ、なぜか1億回coutするEasy(黄色)が別の人に落とされる
  • -25点を挽回できず終了
  • 部屋の残ったコードはすべてシステムテストを通過
  • 部屋の様子
    • Easyはサンプルが強くほとんど不正解者がいない(全体で18人)。そのうちの2人も部屋にいたのにもったいない…
  • とはいえ正解率7%のMediumが通ったのでまあよし
  • 48位 / 767, 2368 → 2404 (+36)
    • 1年間2399のままだった最高レートをついに更新
  • 日本12位。上には明らかに格上の人しかいなくて、下にも格上の人がいる

f:id:evima:20131224002154p:image

    • これを見るともう上がる気がしないが、見なければまだまだ明らかに上げられるはずなので頑張ります

To be continued.

ゲスト



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