Hatena::Grouptopcoder

思考錯誤 - By evima

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

2013-11-02

SRM 596

22:13

数学以外の何物でもない…


SRM 596 (Div. 1)

【Easy (250) - IncrementAndDoubling】

[概要] 長さNの数列aがある。はじめすべての項は0である。
次の2種類の操作を、任意の順序で何度でも行える。
操作1: 項を1つ選んで1を足す。
操作2: 全ての項を2倍する。
長さNの数列desiredArray(以下d)が与えられる。aをdと一致させるために最小で何回の操作が必要か。
- N <= 50, 0 <= d[i] <= 1000
  • 本番中のメモ:

f:id:evima:20131102030819j:image

  • 他の人のパフォーマンスを見る限り前回のEasy以上の易しい問題だったようだが、失敗した…
    • 簡単な解法: 2進表記で考える。最大のd[i]の立っている一番左のビットがiビット目だったとすると、
      操作2をi回行い、その合間の適当なタイミングで操作1を(d[i]の立っているビットの数の合計)回行えばよい
      • d[i]が全部0だったらもちろん0回
      • チャレンジフェーズでさらに分かりやすい考え方に出会う。後述
  • これに気づかず次のようなことをした
    • dp[val][D]:「操作2をD回まで行えるとき、一つの項で0からvalを得るために必要な操作1の回数」を埋める
    • 操作2の回数を0~10(log2(1000))の範囲で全て試して最小の結果を選ぶ
  • コードを書き始めるとき「これは最近のEasyにしては難しめな気が…」と思いながらDivision Summaryを見たら、
    既に130人以上提出していて信じられなかった
  • 10:06.506 → 223.10 / 250 (351位 / 正解654人, 全体727人)
    • たいした点差は付かないがさすがにこれはちょっと…

本番での提出コード:

#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 dp[1010][12];
int f(int val,int D){ // メモ付き再帰
	int& res=dp[val][D];
	if(res!=-1)return res;
	if(val == 0)return res=0; // 0は0手で得られる
	res = f(val-1,D)+1; // 最後の操作が操作1のとき
	if(D>=1 && val%2==0){ // 最後の操作が操作2のとき
		res = min(res, f(val/2,D-1));
	}
	return res;
}

int IncrementAndDoubling::getMin(vector<int> a){
	int n=sz(a);
	memset(dp,-1,sizeof(dp));
	rep(i,1001)rep(j,11)f(i,j); // 不要だが害はない
	int ans=INF;
	rep(i,11){ // 操作2の回数を0~10の範囲で全て試す
		int res=i;
		rep(j,n){
			res += f(a[j],i);
		}
		ans=min(ans,res);
	}
	return ans;
}

【Medium (500) - BitwiseAnd】

[概要] 次の性質1,2をともに満たす非負整数の集合Sをcoolと呼ぶ。
性質1: Sの任意の異なる要素a,bについて、(a&b)>0
性質2: Sの任意の異なる要素a,b,cについて、(a&b&c)=0
(&はビットごとのand)
整数Nと、要素数N以下の整数の集合subsetが与えられる。
要素数がNで、subsetの要素を全て含み、全要素が1以上2^60-1以下のcoolな集合のうち、
(要素を昇順に並べたとき)辞書順最小のものを求めよ。存在しないならそう指摘せよ。
- 3 <= N <= 50, 0 <= |subset| <= N, 1 <= subset[i] <= 2^60-1
  • 本番中のメモ:

1/2

f:id:evima:20131102080613j:image

2/2

f:id:evima:20131102081452j:image

  • とりあえずサンプルの値を2進表記して様子を見る
  • 一見性質1の方が単純そうだが、実は性質2の方が扱いやすい
    • 性質1: (a&b)>0 <=> 「任意のa,bに対し、あるiが存在し、i番目のビットは両方1」
    • 性質2: (a&b&c)=0 <=> 「任意のa,b,cに対し、任意のiについて、i番目のビットは"全部1"ではない」
      =>「任意のiについて、i番目のビットが1であるような要素は高々2個」
  • これに気づいたら、あとは各位ごとに既存要素の"1"が何個出現するか数え、
    0個か1個か2個かで分類して「適当に」やればよい
    • 0個の位置にはあと2つ"1"を置けるので、任意の2つの新要素a,bに対し(a&b)>0とさせるために使う
      • これが足りないとアウト
    • 1個の位置にはあと1つ"1"を置けるので、任意の既存要素aと新要素bに対し(a&b)>0とさせるために使う
      • これも足りないとアウト
    • 2個の位置にはもう"1"を置けないので何にも使えない
    • 3個以上の位置があったら性質2に反してアウト
    • 他に、(a&b)=0となるような既存要素a,bがあっても性質1に反してアウト
      • 以上の4条件を満たせばセーフ
  • なにこの数学…
    • 「数学」が85%、「プログラミング」(最大の難関:"1LL<<何か"を"1<<何か"と書かない)が15%の問題
  • 44:48.956 → 226.58 / 500 (109位 / 正解194人, 全体727人)
  • 4分の1を越える正解率は「大抵Mediumは解けないけど今回は解けた」人が多かったことを意味するが…
    • こんなアドリブが要求される問題のどこがいつもよりとっつきやすいんだ…?
      • まあ解いた"後"では自明にしか見えないんですけどね
    • 僕が単に経験値でゴリ押ししているだけで、地頭の良さが向上していないことが分かって悲しくなった
#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())

typedef long long ll;
typedef vector<ll> vi;

const int D=60;
ll dig[55][66]; // dig[i][j]: subset[i]のjビット目(0or1)
int rest[66]; // iビット目に"1"が存在していい残りの数

vector<long long> BitwiseAnd::lexSmallest(vector<long long> sub, int n){
	vector<ll> res; // "解なし"用にしか使わなかった
	int m=sz(sub); // m: sub(subset)の要素数
	int K = n-m; // K: subに加えるべき要素数
	
	rep(i,m)rep2(j,i+1,m){ // subが性質1に反していたら解なし。性質2はあとで他の操作と同時に確認
		if((sub[i]&sub[j])==0){
			cout<<"FAIL and2"<<endl; // SRMの環境上こういう出力は問題なし
			return res;
		}
	}
	
	fill(rest,rest+D,2); // どの位にも"1"は高々2つまで
	rep(i,m){
		rep(j,D){
			dig[i][j] = sub[i] >> j & 1; // sub[i]のjビット目
			rest[j] -= dig[i][j]; // "1"だったらこの位の残り許容数をマイナス
		}
	}
	vi pos1[55],pos2; // pos1[i]: "1"が1つある位(あと1つ置ける)で、その"1"がsub[i]由来のもの(昇順)
	rep(i,D){ // pos2: "1"がない位(あと2つ置ける)(昇順)
		if(rest[i] < 0){ // "1"が3つ以上ある位があったらsubが性質2に反している。解なし
			cout<<"FAIL "<<i<<endl;
			return res;
		}
		if(rest[i]==1){ // あと1つ置ける
			rep(j,m){
				if(sub[j]>>i & 1){ // "1"がsub[j]由来なら
					pos1[j].pb(i); // pos1[j]へ
				}
			}
		}
		if(rest[i]==2){ // あと2つ置ける
			pos2.pb(i); // pos2へ
		}
	} // rest[i]==0 のもう"1"が1つも置けない位は無視
	
	// // テスト出力
	rep(i,m){
		cout<<"pos1 "<<i<<" : ";
		rep(j,sz(pos1[i])){
			cout<<pos1[i][j]<<" ";
		}
		cout<<endl;
	}
	rep(i,sz(pos2))cout<<pos2[i]<<" ";cout<<endl;
	//
	
	rep(i,m){
		if(sz(pos1[i]) < K){ // size(pos1[i])がK未満であるようなiがあったら解なし
			cout<<"FAIL pos1"<<endl; // 理由は後述
			return res;
		}
	}
	if(sz(pos2) < K*(K-1)/2){ // size(pos2[i])がK*(K-1)/2未満なら解なし
		cout<<"FAIL pos2"<<endl; // 理由は後述
		return res;
	}
	
	ll newval[55]={}; // subに付け加える値(昇順)
	rep(i,K){
		rep(j,m){ // 各sub[j]についてpos1[j]の小さい方からK箇所を使い、subの各要素aと
			newval[i] |= 1LL << pos1[j][i]; // newvalの各要素bに対して(a&b)>0を成立させる。
		} // size(pos1[i])がK未満であるようなiがあると、ここで位が足りなくなる
	}
	int cur=0;
	rep(i,K)rep2(j,i+1,K){ // pos2の小さい方からK*(K-1)/2箇所を使い、newvalの異なる2要素a,bに対して
		newval[i] |= 1LL << pos2[cur]; // (a&b)>0を成立させる。
		newval[j] |= 1LL << pos2[cur]; // このパターンで辞書順最小になることはサンプル4で示されている
		cur++; // (メモの最後)。size(pos2[i])がK*(K-1)/2未満だと、ここで位が足りなくなる
	}
	
	rep(i,K)cout<<newval[i]<<" ";cout<<endl;
	
	rep(i,K)sub.pb(newval[i]); // subにnewvalを入れる
	sort(sub.begin(),sub.end()); // 忘れずソート
	
	return sub;
}

  • Hardとか見てもムダ…
    • と思ったが同じ部屋のyeputonsさん(ロシア)が終了間際に提出したので見ておく

【Hard (1000) - SparseFactorial】

[概要] 整数nに対し、F(n)を (n - 0^2) * (n - 1^2) * (n - 2^2) * ... * (n - k^2)
(kは n - k^2 > 0 なる最大の整数) と定義する。
整数lo,hi,divisorが与えられる。divisorがF(n)の約数となるようなlo以上hi以下の整数nの個数を求めよ。
- 1 <= lo <= hi <= 10^12, 1 <= divisor <= 10^6


【Challenge Phase~】

  • 部屋内の自分以外の提出数: Easy15, Medium7, Hard1
  • Easyをレートが低い順に見ていく
  • ここでEasyのより簡単な考え方に遭遇
    • 全部0の状態からゴールを目指すのではなく、ゴールから全部0の状態を目指す
    • できる操作: 1. 1つの項から1引く 2. 全部2で割る(全部偶数のときのみ)
  • これなら、単に「奇数を操作1で全部偶数にして操作2」を繰り返すだけ!
    • そのまま実装しても速いし、ここから「一番左のビットの位置 + "1"の数の合計」も思いつきやすい
    • 次から、「スタートからゴールまで」と言われたら無条件で「ゴールからスタートまで」も考えるか…
  • 部屋のEasyがどれもこれも上の2つの方針のどちらかで、落ちそうなのが見つからない…
  • その間にMediumが5つ(/7)も落とされる(うち4つyeputonsさん)
    • えっサンプル強かったでしょ…?
  • もうEasyしかないので繰り返し見る
  • 僕と似たメモ付き再帰を書きかけて、結局上の式に落ち着いた人がいる
  • ん…?
    • よく見ると「一番左のビットの位置」の部分がおかしくて、{1}で1、{2}で2を返すのはいいが、
      {4}でも{8}でも{512}でも2を返しそうな人がいる!
  • yeputonsさんは少し前にこの解法を開いて閉じて別のコードを見ているので慎重に…
  • よしこれは絶対に落ちる、チャレンジ
    • Successful!
    • 暫定180位前後から90位前後まで浮上。大きな大きな+50点
      • でもこれサンプルの{16,16,16}でも落ちるはず…まあこういうこともあるか
  • 満足して終了
  • 部屋の残ったコードは全てシステムテストを通過
  • 部屋の様子
  • 成績: 66位/727, 2380→2391 (+11)
    • また微妙…遅いとはいえ一応2つ通して撃墜もして「+11」か
    • とはいえ撃墜なしなら115位だったし、今回は負けるはずのところを引き分けに持ち込んだということで…
  • なおyeputonsさんは3つ全部通した上に5撃墜1ミスで合計1240点、全体2位でターゲットに(2922→3003)
    • ターゲット目指すとかいってて499点の人は恥ずかしくないのかな
  • yeputonsさんのチャレンジの記録を見てみる
    • なんと4つともsubset={3,12},N=3のケース(3&12=0なので解なし)で{3,5,12}を返すコードだった
    • 十分強いサンプルだと思っていたが、4条件のうち1つを思い切り無視しても通っちゃうのか…
      条件を1つずつ外してサンプルがどうなるか確認するべきだった

教訓:

  • とりあえずスタートとゴールを逆にしてみる
  • コードを書き換えてサンプルの脆弱性をチェック、「たぶん強い」で済ませない

To be continued.

BrandieBrandie2016/05/03 10:50I think you hit a bulelsye there fellas!

LanetaLaneta2016/05/04 02:06I notice that mine can wake up prematurely and isn’t ready to be up yet. While we’ve never been successful at getting him back to sleep, simply leaving the room as is has helped a ton! He’ll usually just lay in bed semi awake and that has been enough to temper his <a href="http://qdebki.com">grhsuoinesc.</a> Thanks for adding this tip!