Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-11-19SRM524 Div1

SRM524 Div1 250 MagicDiamonds

| 14:18 | SRM524 Div1 250 MagicDiamonds - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM524 Div1 250 MagicDiamonds - SRM diary(Sigmar) SRM524 Div1 250 MagicDiamonds - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは解が最大2なのではないか

合成数のときは明らかに1で、素数のときは、1とn-1に分けるとn-1が偶数だから確実に2でいける

n==1とn==2だけ怪しいので特別扱いしとけばいいだろう(←n==3の考慮漏れ)

できた

提出。243点くらい

みんな245超えてる。提出早い・・・


終わり際に赤い人が何人か再提出しているのを見てコーナーケースが不安になる

コーナーケースがあるとしてもn==3くらいしか思いつかないが・・・

ってn==3って答え3じゃないか。終わった・・

再提出


チャレンジも慎重になりすぎて全然できなかった


ソースコード

まあコーディングフェーズ中に間違いに気づけただけでも昔よりは成長したかな・・・

class MagicDiamonds {
public:
	long long minimalTransfer(long long n) {
		if(n==1) return 1;
		if(n==2) return 2;
		if(n==3) return 3;

		for(ll i=2; i*i<=n; i++) {
			if(n%i==0) return 1;
		}
		return 2;
	}
};

SRM524 Div1 500 LongestSequence

| 14:18 | SRM524 Div1 500 LongestSequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM524 Div1 500 LongestSequence - SRM diary(Sigmar) SRM524 Div1 500 LongestSequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

まず、直接的に求めるのは何となく難しそうなので、解を探索し実現可能かという判定問題に変換する

今回は解がXでOKならX-1も明らかにOK、XでNGならX+1も明らかにNGなので二分探索が利用できる


さてどうやって判定するのか。

解のシーケンスを配列aとして、条件からすると、a[i]+a[i+1]+...+a[i+C[k]-1]>0とかみたいな条件式がたくさんできる

このままだと変数が多すぎて条件が訳わからんので、何とか変数を減らす工夫を考える。


・・・

・・・


色々こねくり回したけど分からん。時間切れ。。。。


後で

よく考えれば、a[i]+a[i+1]+...っていかにも和を別の変数に置き換えれば?というヒントに見える

それってまさにこないだ解けなかったSRM520 Medium SRMIntermissionPhaseと同じアイデアだ

全然反省が見についてないことに愕然とする・・・


sum[i]=a[0]+a[1]+...+a[i-1]とする。

例えば、sum[0]=0, sum[1]=a[0], sum[2]=a[0]+a[1], sum[3]=a[0]+a[1]+a[2], ...

すると先ほどの条件式は、sum[i+C[k] ]-sum[i]>0といような条件式に置き換えることができる

変形するとsum[i+C[k] ]>sum[i]

これで条件式がとても単純になる

当然ながら、sum[i]<sum[j]かつsum[j]<sum[i]となると矛盾するため、解は存在しない

逆にそのような矛盾がなければ、必ず解が存在する。x軸が添え字、y軸がsum[i]のグラフにプロットしてみれば簡単にプロットできることが分かる。

sum[i+1]-sum[i]の値がまさにa[i]の値である。

ということは、結局推移律が成り立たないようなパターンが存在するかを判定する問題に変換できる。

これは、小なり記号を有向グラフのエッジに置き換えることでループ存在判定問題に置き換えることができる。

ここまでくればあとはやるだけ。。。


なお二分探索の上限値によって計算量が決まるので、上限値を定めることが必要になる。

ここでは無限大のパターンを除いて上限は2000を超えることはない。

無限大にならない条件は、Cに正と負の値が両方存在することである。

その場合に2000を超えるとすると、Cに含まれる任意の正の値をp、負の値をqとすると、r=| |p|-|q| |として、|p|>|q|のときr、|p|<|q|のとき-rをCに加えることが可能になる

例えば1000と-600があるとすると、任意の長さ400のシーケンスが正になる

これを再帰的に続けると、いつかrと-rの両方がCに含まれる状況が発生し、矛盾が生じる


念のため上限を10000にしても、計算量は50*10000*log(10000)<1000万程度である


また、このやり方でいくと、わざわざ場合分けをすることなく、二分探索で解が上限に張り付くパターンは解が無限大、すなわち-1になるのだという判定ができる。


ソースコード

int vis[10010];
int par[10010];

class LongestSequence {
public:
	vector <vector <int> > adj;

	bool loop(int v) {
		if(par[v]) return true;
		if(vis[v]) return false;
		par[v]=vis[v]=1;
		for(int i=0; i<(int)adj[v].size(); i++) {
			if(loop(adj[v][i])) return true;
		}
		par[v]=0;
		return false;
	}

	bool ok(vector <int> C, int len) {
		int n=C.size();
		adj.assign(10010, vector <int>());
		for(int i=0; i<n; i++) {
			for(int j=0; j+abs(C[i])<=len; j++) {
				if(C[i]>0) adj[j].push_back(j+C[i]);
				else adj[j-C[i]].push_back(j);
			}
		}
		memset(vis, 0, sizeof(vis));
		memset(par, 0, sizeof(par));
		for(int i=0; i<=len; i++) {
			if(vis[i]) continue;
			if(loop(i)) return false;
		}
		return true;
	}

	int maxLength(vector <int> C) {
		int res;

		int hi=10000, lo=0, mid;
		while(hi-lo>1) {
			mid=(hi+lo)/2;
			if(ok(C, mid)) lo=mid;
			else hi=mid;
		}
		if(lo>=9999) res=-1;
		else res=lo;
		return res;
	}
};

utmathutmath2011/11/19 21:26参考になりました!

SigmarSigmar2011/11/20 11:04コメントありがとうございます。
お役に立てたのであれば幸いです。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111119