Code Festival 2014 上海
Welcome to code festival 2014 上海(オープンコンテスト) - code festival 2014 上海(オープンコンテスト) | AtCoder
正解したのは1問。 2問目はTLEで、解けたサンプルは1つ。
Aはいいとして、Bは正攻法で書くのが精一杯だけど、このコードだと10^6
で時間制限を超えてしまう。しかし、最大数は10^18
(quintillion)。
正解した人の回答を見てみると、Binary searchを使ってる。そりゃ早いわ、ってのは分かるけれど、なぜBinary searchなのか、が分からない。このへんを理解しときたい。
- A - Lock
#include <iostream> #include <vector> #include <map> #include <algorithm> #include <utility> #include <math.h> using namespace std; int n; int digits[6]={0}; int direct[6]={0}; // 0:increment, 1:decrement int stopcount; int cnt=0; void pr(){ for(int j=n-1;j>=0;j--){ cout<<digits[j]; } cout<<endl; } void dial(int index){ while(1){ if(index>0) dial(index-1); if(direct[index]==0){ digits[index]++; }else{ digits[index]--; } pr(); cnt++; if(cnt==stopcount) break; if(direct[index]==0){ if(digits[index]==9){ if(index>0) dial(index-1); direct[index]=1; break; } }else{ if(digits[index]==0){ if(index>0) dial(index-1); direct[index]=0; break; } } } } int main(){ cin>>n; stopcount=pow(10,n); cout<<stopcount-1<<endl; pr(); cnt++; dial(n-1); return 0; }
- B - n-th Points
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <algorithm> #include <utility> #include <math.h> using namespace std; struct relation { bool operator() (const pair<int,int> p, const pair<int,int> q) const { if(abs(p.first)+abs(p.second)!=abs(q.first)+abs(q.second)) return !(abs(p.first)+abs(p.second)<abs(q.first)+abs(q.second)); else if(p.first!=q.first) return !(p.first<q.first); else return !(p.second<q.second); } }; priority_queue <pair<int,int>,vector<pair<int,int> >,relation> pq; set<pair<int,int> > sp; int main(){ int T; cin>>T; deque<int> Q; int q; for(int i=0;i<T;i++){ cin>>q; Q.push_back(q); } pair<int,int> x; x.first=0; x.second=0; pq.push(x); int nth; nth=Q.front(); Q.pop_front(); int cnt=1; while(1){ if(cnt==nth){ cout<<pq.top().first<<" "<<pq.top().second<<endl; if(Q.empty()){ break; }else{ nth=Q.front(); Q.pop_front(); } } x=pq.top(); pq.pop(); sp.erase(pair<int,int>(x.first,x.second)); set<pair<int,int> >::iterator iti; if(abs(x.first)+abs(x.second)<abs(x.first+1)+abs(x.second)){ iti=sp.find(pair<int,int>(x.first+1,x.second)); if(iti==sp.end()){ pq.push(pair<int,int>(x.first+1,x.second)); sp.insert(pair<int,int>(x.first+1,x.second)); } } if(abs(x.first)+abs(x.second)<abs(x.first-1)+abs(x.second)){ iti=sp.find(pair<int,int>(x.first-1,x.second)); if(iti==sp.end()){ pq.push(pair<int,int>(x.first-1,x.second)); sp.insert(pair<int,int>(x.first-1,x.second)); } } if(abs(x.first)+abs(x.second)<abs(x.first)+abs(x.second+1)){ iti=sp.find(pair<int,int>(x.first,x.second+1)); if(iti==sp.end()){ pq.push(pair<int,int>(x.first,x.second+1)); sp.insert(pair<int,int>(x.first,x.second+1)); } } if(abs(x.first)+abs(x.second)<abs(x.first)+abs(x.second-1)){ iti=sp.find(pair<int,int>(x.first,x.second-1)); if(iti==sp.end()){ pq.push(pair<int,int>(x.first,x.second-1)); sp.insert(pair<int,int>(x.first,x.second-1)); } } cnt++; } return 0; }