会津大学オンラインジャッジ 問

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A&lang=jp
平面上に散らばった１０万点から最も近い２地点を選ぶ問題。

ｘ、ｙ座標の順でソートして左から右へ平面走査をしていけばよいです。
素朴に実装したら何かメモリ使用量が大きくなりました。




#include<stdio.h>
#include<map>
#include<set>
#include<math.h>

struct P{
      double x,y;
      bool operator<(const P& p)const{
            return y<p.y;
      }
};

std::map<double ,std::set<double> > Ps;


int main(){
      P p;
      int n;
      double x,y;
      scanf("%d",&n);
      while(n--){
            scanf("%lf %lf",&x,&y);
            Ps[x].insert(y);
      }
      std::map<double ,std::set<double> >::iterator it;
      std::set<double>::iterator sItD,sItU;
      std::set<P> Left,Dells;
      std::set<P>::iterator pIt;
      double ans=1000000;
      for(it=Ps.begin();it!=Ps.end();){
            sItD=(*it).second.begin();
            sItU=sItD;
            sItU++;
            while(sItU!=(*it).second.end()){
                  double dy=fabs((*sItU)-(*sItD));
                  if(dy<ans)ans=dy;
                  sItU++;
                  sItD++;
            }
            sItD=(*it).second.begin();
            sItU=sItD;
            sItU++;
            double x=(*it).first;
            double dy,dx,dy2;
            Dells.clear();
            for(pIt=Left.begin();pIt!=Left.end();){
                  dy=fabs((*sItD)-(*pIt).y);
                  dx=fabs(x-(*pIt).x);
                  double len=hypot(dx,dy);
                  if(len<ans)ans=len;
                  if(dx>ans){
                        Dells.insert((*pIt));
                  }
                  if(sItU!=(*it).second.end()){
                        dy2=fabs((*sItU)-(*pIt).y);
                        if(dy2<dy){
                              sItD++;
                              sItU++;
                        }else{
                              pIt++;
                        }
                  }else{
                        pIt++;
                  }
            }
            for(pIt=Dells.begin();pIt!=Dells.end();pIt++){
                  Left.erase((*pIt));
            }
            for(sItD=(*it).second.begin();sItD!=(*it).second.end();sItD++){
                  p.x=x;
                  p.y=(*sItD);
                  Left.insert(p);
            }
            Ps.erase(x);
            it=Ps.begin();
      }
      printf("%0.7lf\n",ans);
}

AOJ Range Query - Range Sum Query

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
会津大学オンラインジャッジ問ＤＳＬ２Ｂ
データの変更と集計クエリに高速に答える問題。

もちろん、クエリごとに線形で集計していたら答えは出ない。
セグメント木で分割して集計したものをさらに集計するというひと手間が必要。

実は細部は直感で書いてるので理論面ではちょっと曖昧な部分があります。
色々なテストデータを用意して全部うまくいったからこれでいけるだろという感じで合格しました。


#include<stdio.h>
#include<map>
#include<algorithm>

const int LIMIT=262144;
const int FIRST=LIMIT/2;
int A[LIMIT];

void set(int p){
      if(p==0)return ;
      A[p]=0;
      set(p/2);
}


void dellAndSet(int p){
      if(p==0)return ;
      int a=0,b=0;
      if(p*2<LIMIT){
            a=A[p*2];
      }
      if(p*2+1<LIMIT){
            b=A[p*2+1];
      }
      A[p]=a+b;
      dellAndSet(p/2);
}

int sum(int x,int y,int p,int L,int R){
      if(x>y)return 0;
      int M=(L+R)/2;
      if(L==x){
            M=R;
            while(y<M){
                  p*=2;
                  M = (L+M)/2;
            }
            int a=A[p];
            int b;
            b=sum(M+1,y,1,0,FIRST-1);
            //printf("(%d %d %d)<%d %d %d %d %d>",a,b,p,L,M,R,x,y);
            return a+b;
      }
           
     
      if(M<x){
            return sum(x,y,p*2+1,M+1,R);
      }else if(x<=M){
            return sum(x,y,p*2,L,M);
      }

      return -10000;//おかしな処理の検出
}
int main(){
      int n,q,com,x,y;
      scanf("%d %d",&n,&q);
      for(int i=0;i<FIRST;i++){
            set(FIRST+i);
      }
     
      for(int i=0;i<q;i++){
            scanf("%d %d %d",&com,&x,&y);
            if(com==0){
                  A[x+FIRST]+=y;
                  dellAndSet((x+FIRST)/2);
            }else{
                  printf("%d\n",sum(x,y,1,0,FIRST-1));
            }
      }
}

Range Query - Range Minimum Query

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
データを更新しながらクエリに答える問題。


セグメント木で更新検索するだけです。
木の根元へ更新するとき、子のより小さい値を選びながら上へ更新していきます。
実行速度は一位タイですが皆僅差なので大差ありません。
set関数がかなり無駄というのは書き終えた後に気付きました。

#include<stdio.h>
#include<map>
#include<algorithm>

const int LIMIT=262144;
const int S=2147483647;
const int FIRST=LIMIT/2;
int A[LIMIT];

void set(int p){
      if(p==0)return ;
      A[p]=S;
      set(p/2);
}


void dellAndSet(int y,int p){
      if(p==0)return ;
      int a=S,b=S;
      if(p*2<LIMIT){
            a=A[p*2];
      }
      if(p*2+1<LIMIT){
            b=A[p*2+1];
      }
      int nowMin=std::min(std::min(y,a),b);
      A[p]=nowMin;
      dellAndSet(nowMin,p/2);
}

int search(int x,int y,int p,int L,int R){
     
      if( R<x|| y<L)return S;
      if(x<=L&&R<=y){
            return A[p];
      }else{
            int a=search(x,y,p*2  ,L,  (L+R)/2);
            int b=search(x,y,p*2+1,(L+R)/2+1,R);
            return a<b?a:b;
      }
}
int main(){
      int n,q,com,x,y;
      scanf("%d %d",&n,&q);
      for(int i=0;i<FIRST;i++){
            set(FIRST+i);
      }
     
      for(int i=0;i<q;i++){
            scanf("%d %d %d",&com,&x,&y);
            if(com==0){
                  dellAndSet(y,x+FIRST);
            }else{
                  printf("%d\n",search(x,y,1,0,FIRST-1));
            }
      }
}

会津大学オンラインジャッジ ＧＲＬ＿３＿Ａ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_A

Ｃonnected Components - Articulation Points
完全に自己流の解放で解決。

問題ページのヒントへのリンクに解法が載っているがそれはガン無視。
まずは全くの0から自分で考えた解法で解いてみた。
中学生レベルの教育も満足に受けてないしグラフ理論なんてわかんねというのでとにかく時間かかった。

コードの方針を決めるのに２時間。
一睡しながら夢の中で考え直し、そのあとは試行錯誤しながらコード実装をガリガリ６時間。
実質３日かかった。

コード実行時間0.03セコンド、正答者の中では実行速度最下位である。
残念。

そのうちヒントのほうの解法を実装しようと思う。


#include<stdio.h>
#include<queue>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<set>
#include<stack>


struct E{
    int t,len,old,no;
    bool alive;
    bool operator<(const E& e1)const{
        return len>e1.len;
    }
};

const int LIMIT=10*10000+1;
std::vector<E> G[LIMIT];
int lens[LIMIT];
int roots[LIMIT];

bool alivePoints[LIMIT];
int  loopCounts[LIMIT];
int size;


void D(){
    E e1,e2;
    int v,e,s,t;
    scanf("%d %d",&v,&e);
   
    for(int i=0;i<e;i++){
        scanf("%d %d",&s,&t);
        e1.alive=false;
        e1.len=0;
        e1.t=t;
        G[s].push_back(e1);
        e1.t=s;
        G[t].push_back(e1);
    }
    memset(lens,-1,sizeof(lens));
    e1.old=-1;
    e1.t=0;
    e1.len=0;
    e1.no=0;
    std::priority_queue<E> pq;
    pq.push(e1);
    std::vector<E>::iterator vIt,vItEnd;
    size=v;
    while(pq.empty()==false){
        e1=pq.top();
        pq.pop();
        if(lens[e1.t]!=-1&&lens[e1.t]<=e1.len){
            continue;
        }
        lens[e1.t]=e1.len;
       
        if(e1.old!=-1){
            //printf("(a t=%d old=%d no=%d)\n",e1.t,e1.old,e1.no);
            G[e1.old][e1.no].alive=true;
            roots[e1.t]=e1.old;
        }
       
        e1.len++;
        vItEnd=G[e1.t].end();
        int i=0;
        for(vIt=G[e1.t].begin();vIt!=vItEnd;vIt++){
            e2=(*vIt);
            e2.len=e1.len;
            e2.old=e1.t;
            e2.no=i;
            i++;
            if(e2.t==e1.old){
                //printf("(b old=%d t=%d no=%d)\n",e2.old, e2.t, e2.no);
                G[e2.old][e2.no].alive=true;
            }else{
                pq.push(e2);
            }
        }
    }
    //std::set<int>::iterator sIt;
    //for(int i=0;i<v;i++){
    //  printf("\n%d\n",i);
    //  for(sIt=pareMemo[i].begin();sIt!=pareMemo[i].end();sIt++){
    //      printf("<%d> ",(*sIt));
    //  }
    //}
}


std::map<int,int> memo;
int countNos[LIMIT];
int nowLoopAdds[LIMIT];
int dells[LIMIT];
bool ans[LIMIT];

bool lastPoint0Check(){
    //この関数はとても恥ずかしい
    if(size<3)return false;
    if(G[0].size()==1)return false;
    std::queue<int> qu;
    qu.push(1);
    memset(alivePoints,true,sizeof(alivePoints));
    alivePoints[0]=alivePoints[1]=false;
    std::vector<E>::iterator vIt,vItEnd;
    E e1;
    while(qu.empty()==false){
        int p=qu.front();
        qu.pop();
        vItEnd=G[p].end();
        for(vIt=G[p].begin();vIt!=vItEnd;vIt++){
            int p1=(*vIt).t;
            if(alivePoints[p1]==false)continue;
            alivePoints[p1]=false;
            qu.push(p1);
        }
    }
    for(int i=0;i<size;i++){
        if(alivePoints[i]==true)return true;
    }
    return false;
}

void search(){
    memset(alivePoints,true,sizeof(alivePoints));
    memset(loopCounts,0,sizeof(loopCounts));
    memset(ans,false,sizeof(ans));
    memset(nowLoopAdds,0,sizeof(nowLoopAdds));
    memset(dells,0,sizeof(dells));

    std::stack<std::pair<int,int> > sta;
    std::pair<int,int> pp,pp2;
    alivePoints[0]=false;
    pp.first=0;
    pp.second=0;
    sta.push(pp);
    std::vector<E>::iterator vIt,vItEnd;
    E e1;
    int countNo=0;
    while(sta.empty()==false){
        countNo++;
        pp=sta.top();
        sta.pop();
       
        int s=pp.first;
        int i=pp.second;
        //printf("%d ",s);
        alivePoints[s]=false;
        if(i==G[s].size()){
            int t=countNos[s];
            memo.erase(t);
            if(s!=0){
                loopCounts[roots[s]]+=loopCounts[s]+nowLoopAdds[s]-dells[s];
                if((loopCounts[s]==dells[s])&&((nowLoopAdds[s]+loopCounts[s]==0)||(dells[s]>0))){
                    ans[s]=true;
                    if(nowLoopAdds[s]==0){
                        ans[roots[s]]=true;
                    }
                }
            }
           
            //printf("\n<d=%d>\n",t);
            //std::map<int,int>::iterator sIt;
            //for(sIt=memo.begin();sIt!=memo.end();sIt++){
            //  printf("<%d %d>",(*sIt).first,(*sIt).second);
            //}
            //printf("\n");
        }else{
            if(i==0){
                memo[countNo]=s;
            }else{
                int t=countNos[s];
                memo.erase(t);
                memo[countNo]=s;
            }
            countNos[s]=countNo;
            //printf("(%d %d)",s,countNo);
           
            e1=G[s][pp.second];
            pp.second++;
            sta.push(pp);
            if(e1.alive==false&&alivePoints[e1.t]==true){
                nowLoopAdds[s]++;
            }
           
            if(alivePoints[e1.t]==false&&e1.alive==false){
                int dellP=(*(memo.upper_bound(countNos[e1.t]))).second;
                nowLoopAdds[s]++;
                //printf("\n<dell=%d t=%d s=%d>\n",dellP,e1.t,s);
                dells[dellP]+=2;
                continue;
            }
            if(alivePoints[e1.t]==false){
                continue;
            }
            if(e1.alive==true){
                pp2.first=e1.t;
                pp2.second=0;
                sta.push(pp2);
            }
        }
    }
   
    ans[0]=lastPoint0Check();
    for(int i=0;i<size;i++){
        if(ans[i]==true&&G[i].size()>1){
            printf("%d\n",i);
        }
        //printf("(i=%d count=%d dell=%d %d)\n",i,loopCounts[i],dells[i],roots[i]);
    }
}

int main(){
    D();
    search();
}