プロジェクトオイラー問217 Balanced Numbers

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20217
４７桁までのバランスのとれた整数全ての合計を3^15で割った余りでこたえる問題。
バランスのとれた数とは数字を真ん中で左右に区切って左と右別々に各桁の和をとった時、両側の合計が同じになる数のことである。
奇数桁の場合真ん中は無視してもよいようだ。


たぶん数式で求めるのだと思いますが私は数学の知識が乏しいので動的計画法で解きました。
意外と考えるパターンや桁あふれが多く結構苦労しました。
パズルゲームみたいで解いてて楽しい問題でした。


#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>

const int T=47;
const int LIMIT=T*9+10;
__int64 dp[T][LIMIT],permDP[T][LIMIT];



int main(){
      __int64 ans=45,temp,m=10,mR=1;
      __int64 MOD=pow(3,15);
      memset(dp,0,sizeof(dp));
      memset(permDP,0,sizeof(permDP));
      for(int i=1;i<10;i++){
            dp[0][i]=i;
            dp[T-1][i]=i;
            permDP[0][i]=1;
            permDP[T-1][i]=1;
      }
      for(int i=2;i<=T;i++){
            int p=i/2-1;
            int revP=T-p-1;
            if(i%2==1){
                  m=(m*10)%MOD;
                  mR=(mR*10)%MOD;
                  permDP[0][0]=1;
                  for(int j=0;j<10;j++){
                        for(int k=0;k+j<LIMIT;k++){
                              dp[p+1][k+j]=    (dp[p+1][k+j]    +dp[p][k]      +j*mR*permDP[p][k])%MOD;
                              dp[revP-1][k+j]= (dp[revP-1][k+j] +dp[revP][k]*10+j*permDP[revP][k])%MOD;
                              permDP[p+1][k+j]=(permDP[p+1][k+j]+permDP[p][k])%MOD;
                              permDP[revP-1][k+j]=(permDP[revP-1][k+j]+permDP[revP][k])%MOD;
                        }    
                  }
            }
            __int64 d=ans;
            __int64 test;
            for(int j=0;j<LIMIT;j++){
                  //if(permDP[p][j]==0||permDP[revP][j]==0)continue;
                  test=((i%2==0?0:permDP[p][j]*permDP[revP][j])%MOD*mR*45)%MOD;
                  temp=((dp[p][j]*permDP[revP][j])%MOD*(i%2==1?10:1)+(dp[revP][j]*m)%MOD*permDP[p][j]*(i%2==1?10:1)+test)%MOD;
                  ans=(ans+temp)%MOD;
            }
            std::cout<<"T="<<i<<" "<<ans<<" d"<<ans-d<<"\n";
      }
      std::cout<<"ans="<<ans<<"\n";
}

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

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

古物発掘 マリオカートＤＳ

昔懐かしのゲームを今日また発掘して遊ぶ。

子供にとって携帯ゲームを遊ぶとき一番悲しいことは電池切れだろう
友達と集まってる時一人電池切れだと悲しいものがあると思う。

だからかわからないがマリオカートは電池の持ちがいい。

色々なところで省エネテクニックが使われているような気はする。

例えば立体物はかなり板で置き換えられている。

ユーザの操作するカートのほうを向く板。。
ユーザの操作するカートのほうを向く周期的な表示を繰り返す板
固定された単なる板。
固定された周期的な表示を繰り返す板
ユーザーの操作するカートのほうを向く動く板。
の5種類で上手にマップ内の立体物が平面物で置き換えられている。

例えば
マリオサーキットの火を吐くぱっくんフラワーの幹は板に書かれた絵で。
頭部だけが立体物になっている。
幹も安易に３Ｄモデルにしそうなところこういう細かいところで電池を節約してんだろうなと感心したり。

キラーシップの小型キラー砲台はカートのほうを向く板であって立体物ではない。

ワルイージピンボールの巨大ボールは単なるカートのほうを向く動く板だ。

板の向こうがすけない技術は私にはマジックに見える。
当たり判定や視界判定の処理はちょっとどうなってるか想像がつかない。

誰もが気付くことだけど立体物のポリゴン数はどこをみても最小だ。
巨大キラーは誰が見ても６角柱に６角錐をつけたものだしトンネルはカクカクしている。
コーナーもカクカクしているのにそのカクカクがなぜか視界的に気持ち良いという不思議さ。

遠くの立体物はよく見ると単なる絵だったりする。

一時代を築いたゲームはやっぱり。
電池切れのような子供がどこを喜ぶかを大事にしてるのだろうと思う。

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

Elementary data structures - Areas on the Cross-Section Diagram

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

地形データから水たまりの面積を算出する。
単なるパズルに見せかけて　数学理論を裏側に控えているだろう問題。


右か左で高さが決まるから左右から攻めていくだけです。
￥で水たまりに入る。
/で外に出る
右きから左へ見るときは￥と/を反転してから見る。


#include<stdio.h>
#include<vector>
#include<string.h>

const int LIMIT=20001;
const int out=-1;
const int in=1;
char str[LIMIT];
int inOut[LIMIT]={0};


void setInOut(int sp,int dx){
      int len =strlen(str);
      char c;
      bool isIn=false;
      int outHight,nowHight=0,sum,inP;
     
      std::vector<int> anss;

      for(int i=sp;i>=0&&i<len;i+=dx){
            c=str[i];
            //printf("(%c %d)",c,nowHight);
            if(isIn==true){
                  if(c=='\\'){
                        sum+=outHight-nowHight+1;
                        nowHight--;
                  }else if(c=='/'){
                        nowHight++;
                        sum+=outHight-nowHight;
                  }else if(c=='_'){
                        sum+=outHight-nowHight;
                  }
                  if(nowHight==outHight){
                        //printf("%d ",sum);
                        if(dx==1){
                              inOut[inP]=std::max(sum,inOut[inP]);
                        }else{
                              inOut[i]=std::max(sum,inOut[i]);
                        }
                        isIn=false;
                  }
            }else{
                  if(c=='\\'){
                        //printf("\n<in>");
                        inP=i;
                        isIn=true;
                        sum=1;
                        outHight=nowHight;
                        nowHight--;
                  }else if(c=='/'){
                        nowHight++;
                  }
            }
      }
}
void changeSTR(int len){
      for(int i=0;i<len;i++){
            if(str[i]=='\\')str[i]='/';
            else if(str[i]=='/')str[i]='\\';
      }
}

int main(){
      scanf("%s",str);
      int len=strlen(str);
      setInOut(0,1);
      changeSTR(len);
      //printf("\n\n");
      setInOut(len-1,-1);
      std::vector<int> anss;
      int all=0;
      for(int i=0;i<len;i++){
            if(inOut[i]>0)anss.push_back(inOut[i]);
            all+=inOut[i];
      }
      printf("%d\n%d",all,anss.size());
      for(int i=0;i<anss.size();i++){
            printf(" %d",anss[i]);
      }
      printf("\n");
}

会津大学オンラインジャッジ 問 Tree - Diameter of a Tree

Tree - Diameter of a Tree

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A
グラフ理論における木の直径をこたえる問題。


解法
一点を根元と定めて木を探索します。
深さ優先探索で木を旅する旅人を考えます。
枝先まで旅をします。
枝先にぶち当たったら戻りますが戻るとき距離を数えて、枝先からここまでの距離を分岐ごとに点に記録しておきます。
この分岐の先で一番遠かった枝先までの距離は何々だとします。

ある点の枝先を全部調べ終えたら帰るとき、枝先で一番距離が遠かったものをその道の最も長い距離だと根元側の点に記録します。
これを繰り返してスタート地点まで戻ってくれば答えです。

途中の点で二つの枝先の距離合計が最も遠くなる点を計算する場合を忘れないようにします。

私のコードは試行錯誤の後が残ってるので少し無駄な処理が入っていますが答えには影響しません。
一応コード実行速度で一位に並びました。
こういう綺麗な問題は解いてて楽しいですが、順位差をつけにくいのが欠点ですね。



#include<stdio.h>
#include<vector>
#include<map>
#include<stack>
struct E{
      int t,w,old;
      bool first;
};
const int LIMIT=100001;
std::vector<E> G[LIMIT];
int ans=0;

int sumMax[LIMIT]={0},sumSecond[LIMIT]={0},nowMax[LIMIT]={0};
void setSumMax(int p,int w){
      if(sumMax[p]<=w){
            sumSecond[p]=sumMax[p];
            sumMax[p]=w;
      }else if(sumSecond[p]<=w){
            sumSecond[p]=w;
      }
}


void calc(){
      std::stack<E> sta;
   
      E e1,e2;
      e1.t=0;
      e1.old=-1;
      e1.w=0;
      e1.first=true;
      sta.push(e1);
      int ans=0,c=0;
      while(sta.empty()==false){
            e1=sta.top();
            sta.pop();
            int p=e1.t;
            if(e1.first==true){
                  e1.first=false;
                  sta.push(e1);
            }else{
                  int resultMax=sumMax[p]+e1.w;
                  setSumMax(p,nowMax[p]);
                  ans=std::max(ans,sumMax[p]+sumSecond[p]);
                  setSumMax(e1.old,resultMax);
                  continue;
            }
         
            std::vector<E>::iterator vIt,vItEnd;
            vItEnd=G[p].end();
            for(vIt=G[p].begin();vIt!=vItEnd;vIt++){
                  e2=(*vIt);
                  e2.first=true;
                  if(e2.t==e1.old)continue;
                  sta.push(e2);
                  nowMax[e2.t]=nowMax[e1.t]+e2.w;
            }
      }
      printf("%d\n",ans);
}

int main(){
      int n,s,t,w;
      E e1,e2;
      scanf("%d",&n);
   
      for(int i=1;i<n;i++){
            scanf("%d %d %d",&s,&t,&e1.w);
            e1.t=t;
            e1.old=s;
            G[s].push_back(e1);
            e1.t=s;
            e1.old=t;
            G[t].push_back(e1);
      }
      calc();
}