GCJ 2013 Qual
http://snuke.hatenablog.com/entry/2013/04/14/164938
ここにsnuke神さんが解説書いてくれています。
C
制約をうまく使って解を全列挙して、クエリが来るたび二分探索をすることを考えます
(制約とは、すべての桁の(数字)^2の総和<=9を意味します)
以下はPracticeで通したコードです。
//(include略) typedef long long LL; typedef pair<int,int> PII; #define MP make_pair #define REP(i,n) for(int i=0;i<(int)n;i++) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) #define ALL(c) (c).begin(),(c).end() vector<string> data; void trans(string s) { int n = s.size(); string k = ""; for(int i=0; i<106-n; i++) k+="0"; data.push_back(k+s); } string two(string s) { string ret; int n = s.size(); for(int i=0; i<2*n-1; i++) { ret += "0"; } for(int i=0; i<n; i++) if(s[i]!='0') { for(int j=0; j<n; j++) { ret[i+j] += (s[i]-'0') * (s[j]-'0'); if(ret[i+j]-'0'>=10) cout<<"hogehoge"<<endl; } } return ret; } void saiki(string t, string s, int sum, int length) { if(s.size()+t.size()>=52) return; if(sum>=10) return; if(t[0]!='0') trans(two(t+s)); saiki("0"+t, s+"0", sum, length+1 ); saiki("1"+t, s+"1", sum+2, length+1); } void init() { { string t=""; string s ="2"; trans("9"); // trans("484"); saiki(t,s,4,1); s = "1"; saiki(t,s,1,1); saiki(s,s,2,1); s="0"; saiki(t,s,0,1); saiki(s,s,0,1); } { string s = "2"; string t = ""; for(int i=0; i<26; i++) { trans(two("2"+t+"0"+t+"2")); trans(two("2"+t+"1"+t+"2")); trans(two("2"+t+t+"2")); t+="0"; } } sort(ALL(data)); } int solve() { string s,t; cin>>s>>t; while(s.size()<=105) s = "0"+s; while(t.size()<=105) t = "0"+t; int ans =upper_bound(ALL(data),t) - upper_bound(ALL(data),s); if(binary_search(ALL(data), s)) ans++; return ans; } int main() { init(); /* for(int i=0; i<80; i++) { cout<<data[i]<<endl; } */ int t; cin>>t; REP(i,t) { int ans = solve(); cout<<"Case #"<<i+1<<": "<<ans<<endl; } return 0; }
D
snukeさんみたいに何の操作をするのが最善かは特に考えませんでした。
ですが方針は同じです。操作を一つ行なってその手の先に解がなければその操作を行わず、解があれば一歩進んでその中で考えます。
解の有無判定は以下のような考えをしました。
とりあえず、「解なし」<=>「ある開けていない箱の鍵をどうやっても手に入れられない」と考えます。
自分が鍵を持っていたらその番号には到達可能です。
次に、ある箱を開ける鍵がKEYAiでその箱にKEYBijが入っているとすればKEYAi->KEYBijに辺を張ってります。
これで到達不可能な鍵があれば解なしだ、というかんじでやりました。
(証明してないのであんま詳しいことは言えない…)
あと、明らかにダメなケース(鍵が足りない)は事前に除きました
REPとforが混じってます
//(include略) typedef long long LL; typedef pair<int,int> PII; #define MP make_pair #define REP(i,n) for(int i=0;i<(int)n;i++) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) #define ALL(c) (c).begin(),(c).end() const int MAXKEY = 210; const int MAXCHEST = 210; bool usedMain[MAXCHEST]; vector<int> solve() { int K,N; cin>>K>>N; int calcKeys[MAXKEY]; int keys[MAXKEY]; REP(i,MAXKEY) { keys[i] = 0; calcKeys[i]= 0; } REP(i,K) { int p; cin>>p; p--; keys[p]++; calcKeys[p]++; } vector<vector<int> > chest; vector<int> openKey; for(int i=0; i<N; i++) { int p,q; cin>>p>>q; vector<int>tmp; p--; calcKeys[p]--; openKey.push_back(p); for(int j=0; j<q; j++) { int r; cin>>r; r--; tmp.push_back(r); calcKeys[r]++; } chest.push_back(tmp); } vector<int> noSolution; for(int i=0; i<MAXKEY; i++) if(calcKeys[i]<0) return noSolution; vector<int> ans; REP(i,MAXCHEST) usedMain[i] = false; REP(turn,N) { bool update = false;; REP(chestNum, N) if(!usedMain[chestNum]) if(keys[openKey[chestNum]]>0){ usedMain[chestNum] = true; keys[openKey[chestNum]]--; for(int i=0; i<chest[chestNum].size(); i++) { keys[chest[chestNum][i]]++; } bool ok = true; { bool usedQueue[MAXCHEST]; bool usedKeys[MAXKEY]; queue<int> qu; vector<int> graph[MAXKEY]; REP(i,MAXKEY) { usedKeys[i] = false; usedQueue[i] = false; } REP(i,N) if(!usedMain[i]) { // cout<<"node"<<i<<endl; int s = openKey[i]; usedKeys[s] = true; REP(j,chest[i].size()) { int t = chest[i][j]; graph[s].push_back(t); // cout<<"edge"<<s<<" "<<t<<endl; } } REP(i,MAXKEY) if(keys[i]>0) { qu.push(i); usedQueue[i] = true; } while(!qu.empty()) { int cur = qu.front(); qu.pop(); // cout<<"cur"<<cur<<endl; // usedQueue[cur] = true; for(int i=0; i<graph[cur].size(); i++) { int next = graph[cur][i]; if(!usedQueue[next]) { qu.push(next); usedQueue[next] = true; } } } /* REP(i,N) cout<<turn<<" "<<i<<" "<<usedQueue[i]<<endl; REP(i,3) cout<<keys[i]<<endl; REP(i,3) cout<<usedQueue[i]<<" "<<usedKeys[i]<<endl; */ REP(i,MAXKEY) if(!usedQueue[i] && usedKeys[i] ) ok = false; } if(!ok) { usedMain[chestNum] = false; keys[openKey[chestNum]]++; for(int i=0; i<chest[chestNum].size(); i++) { keys[chest[chestNum][i]]--; } } else { update = true; ans.push_back(chestNum+1); break; } } if(!update) return noSolution; } return ans; } int main() { int t; cin>>t; REP(i,t) { vector<int> ans = solve(); if(ans.empty()) cout<<"Case #"<<i+1<<": IMPOSSIBLE"<<endl; else { cout<<"Case #"<<i+1<<":"; REP(x, ans.size()) cout<<" "<<ans[x]; cout<<endl; } } return 0; }