Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-07-14SRM512 Div1

SRM512 Div1 250 MysteriousRestaurant

| 15:03 | SRM512 Div1 250 MysteriousRestaurant - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM512 Div1 250 MysteriousRestaurant - SRM diary(Sigmar) SRM512 Div1 250 MysteriousRestaurant - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

何というかイテレーションするだけ

問題勘違いしてて時間かかってしまった

この時点でかなり終わっていたが更にチャレンジされてしまった

isupper関数を書くところでislower関数を書いていた

その上変な2分探索してる人を間違ってると勘違いしてミスチャレンジ

ダメな日はどうにもならん・・・


ソースコード

class MysteriousRestaurant {
public:
	int calc(char c) {
		if(isdigit(c)) return c-'0';
		if(isupper(c)) return c-'A'+10;
		return c-'a'+36;
	}

	int maxDays(vector <string> prices, int budget) {
		int res=0;

		int n=prices.size(), m=prices[0].size();

		for(int d=1; d<=n; d++) {
			int mincost[7];
			memset(mincost, 60, sizeof(mincost));
			for(int i=0; i<7; i++) {
				if(i>=n) continue;
				for(int k=0; k<m; k++) {
					int sum=0;
					for(int j=0; j*7+i<d; j++) {
						sum+=calc(prices[j*7+i][k]);
					}
					mincost[i]=min(mincost[i], sum);
				}
			}
			int cost=0;
			for(int i=0; i<7; i++) if(i<d) cost+=mincost[i];
			if(cost<=budget) res=max(res, d);
		}

		return res;
	}
};

SRM512 Div1 500 SubFibonacci

| 15:03 | SRM512 Div1 500 SubFibonacci - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM512 Div1 500 SubFibonacci - SRM diary(Sigmar) SRM512 Div1 500 SubFibonacci - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

任意の2つの数を選択して、その2つがあるフィボナッチに含まれるかは、そのフィボナッチ上で何要素離れたペアなのかを決めてやれば2分探索で判定可能だと思ったがすごく書くのが面倒そうなので他の方法を考えていたが結局他になさそうなので書いたが時間内にバグが取れなかった。


ソースコード

class SubFibonacci {
public:
	int maxElements(vector <int> S) {
		int res=4;
		int n=S.size();
		if(n<=4) return n;

		int memo[52][52];
		for(int i=0; i<52; i++) for(int j=0; j<52; j++) memo[i][j]=2;

		sort(S.begin(), S.end());
		for(int q=0; q<n-1; q++) {
			for(int t=q+2; t<=n; t++) {
				for(int b=1; b<40; b++) {
					int lo=1, hi=S[t-1]+1, mid=(hi+lo)/2;
					int v1=S[q], v2=mid;
					while(1) {
						mid=(hi+lo)/2;
						v1=S[q]; v2=mid;
						for(int i=0; i<b-1; i++) {
							swap(v1, v2);
							v2+=v1;
							if(v2>S[t-1]) break;
						}
						if(hi-lo<=1) break;
						if(v2<=S[t-1]) lo=mid;
						else hi=mid;
					}
					if(v2==S[t-1]) {
						int idx=q+1, cnt=1;
						v1=S[q]; v2=mid;
						for(int i=0; i<b; i++) {
							while(idx<n) {
								if(S[idx]<v2) idx++;
								else if(S[idx]==v2) {cnt++; idx++; break; }
								else break;
							}
							memo[q][idx]=max(memo[q][idx], cnt);
							swap(v1, v2);
							v2+=v1;
							if(v2>S[t-1]) break;
						}
					}
				}
			}
		}

		for(int i=0; i<=n-4; i++) for(int j=i+2; j<=n-2; j++) for(int k=j; k<=n-2; k++) for(int l=k+2; l<=n; l++) {
			res=max(memo[i][j]+memo[k][l], res);
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110714