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;
}