SRM diary(Sigmar)

• 250:208.13, 500:Opened, score:208.13, rank:217, rating:2035(+6)
• 250がすぐ解けていい感じだったが500で少しハマり勿体無い終わり方だった

SRM508 Div1 250 DivideAndShift

SRM508, Div1 | 23:17 |

Problem Statement

コーディングフェーズ

これは・・・DivideとShiftの操作は可換だ。ピンと来た

これが分かったら解けたも同然だな

エラトステネスの篩で素数を生成しておいて、再帰的にNを素数で割っていく

各Nの最小手数をメモ化しておけば計算量は問題ない（Nが決まればMが決まるため、状態数は100万程度しかない）

書いた

サンプル合った

提出

多少実装と可換の確認に時間を食ったがそこそこ早めに解けた

ソースコード

vector <bool> cpn(int n) {
	vector <bool> vn(max(2, n+1), true);

	vn[0]=vn[1]=false;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) vn[j]=false;
	}
	
	return vn;
}

vector <bool> v;
int memo[1000010];

class DivideAndShift {
public:
	int calc(int N, int M) {
		if(memo[N]>=0) return memo[N];
		int res=min(M, N-M);
		for(int i=1; i*i<=N; i++) {
			if(N%i!=0) continue;
			if(i!=1 && v[i]) res=min(res, calc(N/i, M%(N/i))+1);
			if(v[N/i]) res=min(res, calc(i, M%i)+1);
		}
		memo[N]=res;
		return res;
	}

	int getLeast(int N, int M) {
		int res;
		v.clear();
		v=cpn(1000000);
		memset(memo, -1, sizeof(memo));

		res=calc(N, M-1);
		return res;
	}
};

SRM508 Div1 500 YetAnotherORProblem

SRM508, Div1 | 23:17 |

Problem Statement

コーディングフェーズ

すぐに分かるのは、各ビットにつき1が1つ以下でなければORとADDが一緒にならない

1つずつ要素を加えていくDPをすると10^18のメモリが必要

うむ、全然分からん

どう考えても要素数が10しかないことを利用するんだろうが・・・

1桁ずつDPとかできるのかな・・・

各要素の最大値が決められているというのが扱いにくい

最大ってどうしたらいいんだ・・・

（何か色々迷走、終了10分前くらいに解法を思いつく）

上位の桁から順番に、全要素のビットを確定していけばいいのでは

例えば、10100という5桁の2進数があったとする

最初の桁を0にすると、下の4ビットは最大値1111で任意の数字を選択できる

最初の桁を1にすると、下の4ビットは最大値0100でそのまま残る

0100という4桁の2進数があったとする

最初の桁は0しか選べず、下の3ビットは最大値100でそのまま残る

このルールさえ分かれば、後はDP可能だ

各要素につき、任意のビットが選択可能になっているかを記憶すれば良い

各桁につき、1になるのは最大1つなので、せいぜい11分岐、次のビットマスクの生成コストが10であるから、

計算量は約60*2^10*11*10=6600000くらいと全然余裕

ここまで分かった時点で残り5分

コーディングは大したことないので何とかなるか？

頑張って書く

合わない

終了

くっ・・・

ソースコード

微修正で答え合った

const int MOD=1000000009;
int memo[62][1<<10];

class YetAnotherORProblem {
public:
	int rec(vector <ll> &R, int d, int mask) {
		if(d<0) return 1;
		if(memo[d][mask]>=0) return memo[d][mask];

		ll res=0;
		int nmask=mask;
		for(int j=0; j<(int)R.size(); j++) {
			if(R[j]&(1LL<<d)) nmask|=(1<<j);
		}
		res=(res+rec(R, d-1, nmask))%MOD;

		for(int i=0; i<(int)R.size(); i++) {
			if(!(mask&(1<<i)) && !(R[i]&(1LL<<d))) continue;
			int nmask=mask;
			for(int j=0; j<(int)R.size(); j++) {
				if(i==j) continue;
				if(R[j]&(1LL<<d)) nmask|=(1<<j);
			}
			res=(res+rec(R, d-1, nmask))%MOD;
		}

		memo[d][mask]=res;
		return res;
	}

	int countSequences(vector<long long> R) {
		ll res;

		memset(memo, -1, sizeof(memo));
		res=rec(R, 61, 0);
		return res;
	}
};