プロジェクトオイラー問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種類で上手にマップ内の立体物が平面物で置き換えられている。

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

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

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

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

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

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

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