kojingharangの日記

TCO 2012 Round1B

22:55 |

xx- +-0 (Rank 1???) 1244->1153

夜更かししたのに０で残念。

ツイートする

250 FoxAndKgram

22:55 |

• 全部使うと勘違い
• 再提出
• kの最大値101なのに60からデクリメントスタート→と思ったけどrowがk個以上できないといけないから最大値は50でいいんですね
• rowがちょうどk個できると勘違い

↓修正版(test pass in practice room)

class FoxAndKgram {
	public:
	int maxK(vector <int> len) {
		int N=len.size();
		for(int k=50;k>=0;k--) {
			VI used(N);
			int ok=1;
			int L=0;
			//cout<<k<<endl;
			REP(i, N) {
				if(used[i]) continue;
				if(len[i]==k) {used[i]=1;L++;continue;}
				REP(j, N) {
					if(used[j]||i==j) continue;
					if(len[i]+len[j]+1==k) {used[i]=used[j]=1;L++;break;}
				}
			}
			ok &= L>=k;
			//cout<<ok<<endl;
			if(ok) return k;
		}
		return 0;
	}
};

ツイートする

500 FoxAndDoraemon

22:55 |

• i番目以降のtaskを処理する最短時間というDPでやろうとしてうまくいかないことに気づく
• 範囲にしないといかん
• 連鎖行列積の問題みたく [begin, end) を使った最短時間をメモ化。
• が！一箇所 max が min になってて WA
• 最初全部 max にしててあれ最短だから min だ、あでもサブツリーの時間は長い方だ...とかいってるうちに直し漏れが生じた模様
• (´Д｀)
• (2個と3個の場合の処理いらないし)

↓修正版(test pass in practice room)

vector <int> WC;
int SC;
int N;
map<PII, int> memo;
class FoxAndDoraemon {
	public:
	// [i0, i1)
	int f(int i0, int i1) {
		PII key=MP(i0, i1);
		if(memo.count(key)) return memo[key];
		int rest = i1-i0;
		if(rest<=0) return memo[key] = 0;
		if(rest==1) return memo[key] = WC[i0];
		if(rest==2) return memo[key] = SC+max(WC[i0], WC[i0+1]);
		if(rest==3) return memo[key] = SC+max(WC[i0], SC+max/*min*/(WC[i0+1], WC[i0+2]));
		// >=4
		int ans = 1000000;
		for(int i=1;i<rest;i++) {
			int c = SC+max(f(i0, i0+i), f(i0+i, i1));
			ans = min(ans, c);
		}
		return memo[key] = ans;
	}
	int minTime(vector <int> _WC, int _SC) {
		sort(ALLR(_WC));
		WC=_WC;
		SC=_SC;
		memo.clear();
		N=WC.size();
		int ans = f(0, N);
		return ans;
	}
};

ツイートする