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

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

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

昔書いたコードがあるのだがあまりにデータ構造に頼ったあれなコードだったので
もう少しましなコードに直してみた。
このコードならバスラインを表現するdataの形が変わってもきちんと動く。
それにしてももっと短い人たちはどんな風にコードを書いてるのかな。



#include<stdio.h>
#include<vector>
void search(int s,int e){
      int data[]={9,8,7,6,5 ,4,3,2,1,0, 1,2,3,4,5 ,9,8,7,6};
      std::vector<int> sp,ep;
      for(int i=0;i<19;i++){
            if(s==data[i]){
                  sp.push_back(i);
            }
            if(e==data[i]){
                  ep.push_back(i);
            }
      }
      int p1,p2,len=100,d;
      for(int i=0;i<sp.size();i++){
            for(int j=0;j<ep.size();j++){
                  d=sp[i]-ep[j];
                  if(d>0&&d<len){
                        p1=sp[i];
                        p2=ep[j];
                        len=d;
                  }
            }
      }
      for(int i=p1;i>p2;i--){
            printf("%d ",data[i]);
      }
      printf("%d\n",data[p2]);
}

int main(){
      int n,s,e;
      scanf("%d",&n);
      while(n--){
            scanf("%d %d",&s,&e);
            search(s,e);
      }
}

日常への愚痴

このブログでの個人的な記述は全部ここに集積。

スーパーの店内を回遊魚のように周遊して何か食べ物を買ったり。
日本中にあふれかえってる本が吹きだまってできたような、うらびれた小さな町の本屋を訪れたり。
地域の健康屋さんを自認する小さな薬局で売れてない健康飲料を買ったり。
デパートで土讃もの市を見たり。
アマゾンで手に入りにくい希少本を買ったり。

こういうことをしても私は単なる消費者という記号であって、こういうことは人生ではないな。
人生を生きている気がしない。


ネットでは。
フランス政府のセクト（カルト）教団対策がいかに間違ってるか宗教団体の人が主張している。
彼らの主張が事実に立脚するならいいのだが、フランス政府が行ってないことに基づいた妄想も大量に含まれている。
私はそれではフランス政府の活動がどのようなものか公平に議論できるよう中立的な観点から資料を提供しましょう。
といってＷｉｋｉソースにＭｉｖｉｌｕｄｅｓの年次報告書（セクト対策の有識者会議）の日本語訳を掲載した。

が宗教団体の人海戦術の前には大海の一滴。
翻訳代もないのでごく一部しか翻訳できてない。
などいろいろ困っている。



さて宗教団体側の妄想でひとつ例を挙げてみる。
例えば創価学会は、創価学会はフランス政府からカルト指定を受けたが、フランス政府は自分たちのカルト指定がずさんだったことを認めその指定を解除したと主張してます。

どこが妄想なのかというと、フランス政府はカルト指定など行ってない点。

フランス政府が行ったのは行政の実務上、悪質な活動が確認された団体を色々資料にまとめてセクト対策に生かしているのですが。

この記載をセクト指定だと創価学会員が勘違いしているわけです。

単なる実務上の記載であり、指定でもなんでもありません。
指定ではないからその解除も存在するはずがなく、ただ単に悪質な活動があったから、その悪質な範囲に対し行政として対処しているだけというのがフランス政府のカルト対策の実態です。

フランスでも一つだけカルト指定と言えるものがあります。
２００１年に制定された反セクト法というものがあり

この法律は活動内容が悪質で組織犯罪が多発しそれが改まりそうにない団体に対し、裁判を通じてその団体のフランス国内での５年間の活動禁止を裁判で争えるようにする法律です。

この法律の適用が唯一のカルト指定なのですが、
よほど悪質でよほど犯罪体質でない限り適用されません。

創価学会のカルト指定が解除されたという主張を認めるなら、この法律が適用されるほど自分たちは悪辣だったと主張していることになるのですが、彼らはこれに気付いてないようです。

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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0139
Ｃ++には標準では正規表現がないので、今回はＪａｖａで記述。
Ｊａｖａは全く分かってないので他人のソースをそのままマルコピ。
正規表現の勉強になった。


import java.util.*;
import java.util.regex.*;

class Main{

public static Pattern
a= Pattern.compile(">\'(=+)#\\1~"),
b= Pattern.compile(">\\^(Q=)+~~");
static final Scanner stdin=new Scanner(System.in);
//javaの手習い　手習いなので今回は他人のをマルコピー
//マッチ結果のグループ化や後方参照という概念などかなり正規表現の勉強になった
public static void main(String[] args){
int n=stdin.nextInt();
for(int i=0;i<n;i++){
solve(stdin.next());
}
}
public static void solve(String str){
if(a.matcher(str).matches() ){
System.out.println("A");
}else if(b.matcher(str).matches()){
System.out.println("B");
}else{
System.out.println("NA");
}
}
}

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

ＧＲＬ＿３＿Ａのコードを９割流用して１０分で解けた。
前の問題の解放を我流であみだすのに３日かかったことを考えるとあっという間であった。

お祈りは済ませたか？
コードのチェックは。
部屋の隅で胸をドキドキさせながらジャッジデータを通ることを祈る心の準備は？

ＯＫだ。
というわけで一発で通りました。
問題的には3Ａとほとんど同じでした。




#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 cutOKs[LIMIT];
std::set<std::pair<int,int> > ans;


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

      std::stack<std::pair<int,int> > sta;
      std::pair<int,int> pp,pp2,pp3;
      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))){
                              if(cutOKs[s]==true){
                                    pp3.first=std::min(s,roots[s]);
                                    pp3.second=std::max(s,roots[s]);
                                    ans.insert(pp3);
                              }
                        }
                  }
                 
                  //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;
                        cutOKs[s]=true;
                  }else{
                        int t=countNos[s];
                        memo.erase(t);
                        memo[countNo]=s;
                  }
                  countNos[s]=countNo;
                 
                  e1=G[s][pp.second];
                  pp.second++;
                  sta.push(pp);
                  if(roots[s]!=e1.t && lens[e1.t]<=lens[s]){
                        cutOKs[s]=false;
                  }
                 
                  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);
                  }
            }
      }
      std::set<std::pair<int,int> >::iterator it;
      for(it=ans.begin();it!=ans.end();it++){
            printf("%d %d\n",(*it).first,(*it).second);
      }
}

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

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

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

会津大学オンラインジャッジ 問ＡＬＤＳ1＿1Ｄ

Getting Started - Maximum Profit

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

儲かることしか考えない人間心理の盲点を突いた問題です。
r日目以降に売ることを考えた場合、r日目以降の最大値とr-1日目までの最小値を角突き合わせればよいだけです。
というわけでr日目までの最小値をminsに保存してあとは逆向きにr+1日目以降の最大値と差額を計算します。
儲からない場合があるのがこの問題の盲点です。


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

const int LIMIT=200001;
int Rs[LIMIT],mins[LIMIT];

int main(){
int n,ans,vMin;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&Rs[i]);
if(i==0){
vMin=Rs[0];
}else{
vMin=std::min(Rs[i],vMin);
}
mins[i]=vMin;
}
int vMax=Rs[n-1];
ans=Rs[n-1]-mins[n-2];
for(int i=n-2;i>=0;i--){
ans=std::max(ans,vMax-mins[i]);
vMax=std::max(Rs[i],vMax);
}
printf("%d\n",ans);
}

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

Sum of 4 Integers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008
ｎが与えられるのでa+b+c+dで何通りの方法でｎが作れるか答える問題。
0<=a,b,c,d<=9


解法
Ｊａｖａといふものを一つ初めて見よふと思ひておもむろにエクリープスなるものをダウソロードし右も左もわからぬまま気の赴くままにＡＯＪの問題などをといてみゆ。

計算量は19*19+10*10となかりしけるが、Ｊａｖａ言語事体の重さの前には全く意味がないといふことに気付く。


C++で書き直してみたら計算量27*4回になった。
ちなみにこの問題数式で書き表してもよいが数式を具体的に計算する計算量はもう少し小さくなるはず。
多分。


import java.util.Scanner;

class Main{
static final Scanner stdin=new Scanner(System.in);
//javaの手習い

public static void main(String[] args){
int[] memo=new int[37];
int[] memo2=new int[37];
for(int i=0;i<37;i++){
memo[i]=0;
memo2[i]=0;
}
for(int a=0;a<10;a++)
for(int b=0;b<10;b++)
memo[a+b]++;
for(int u1=0;u1<=18;u1++){
for(int u2=0;u2<=18;u2++){
memo2[u1+u2]+=memo[u1]*memo[u2];
}
}

while(stdin.hasNext()){
int n=stdin.nextInt();
if(n<0||n>36){
System.out.println(0);
}else{
System.out.println(memo2[n]);
}
}
}
}



ｃ++版

#include<stdio.h>

int main(){
int dp[37]={1,0},n,a;
for(int i=0;i<4;i++){
int sum=0,p=0,old=0;
for(int s=18;s>=-8;s--){
if(s>=9){
sum+=dp[s];
}else{
sum=sum-old+(s>=0?dp[s]:0);
}
old= s>9?0:dp[s+9];
dp[s+9]=sum;
p=(p+1)%10;
}
}
while(scanf("%d",&n)!=EOF){
if(n>36||n<0)a=0;
else a=dp[n>18?36-n:n];
printf("%d\n",a);
}
}

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

Track and Field Competition

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

スポーツのタイム記録から上位者を選ぶ問題。

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

std::map<double,int> third;
std::map<double,int>::iterator it;
void calc(){
    std::map<double,int> tops;
    int no;
    double time;
    for(int i=0;i<8;i++){
        scanf("%d %lf",&no,&time);
        tops[time]=no;
    }
    it=tops.begin();
    for(int i=0;i<2;i++){
        printf("%d %.2lf\n",(*it).second,(*it).first);
        it++;
    }
    third[(*it).first]=(*it).second;
    it++;
    third[(*it).first]=(*it).second;
}
int main(){
    calc();
    calc();
    calc();
    it=third.begin();
    for(int i=0;i<2;i++){
        printf("%d %.2lf\n",(*it).second,(*it).first);
        it++;
    }
}

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

Middle-Square Method

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

平方採中法のプログラムを作成する問題。

書くだけ。

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

int main(){
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
printf("Case %d:\n",i);
for(int j=0;j<10;j++){
x=((x*x)/100)%10000;
printf("%d\n",x);
}
}
}

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

Frequency Distribution of Height

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

身長別で集計する問題。
境界が整数値なので整数になおして集計するだけです。



#include<stdio.h>

int main(){
int n,count[6]={0},h;
double h1;
scanf("%d",&n);
while(n--){
scanf("%lf",&h1);
h=((int)h1-160)/5;
if(h<0)h=0;
if(h>5)h=5;
count[h]++;
}
for(int i=0;i<6;i++){
printf("%d:",i+1);
while(count[i]--)printf("*");
printf("\n");
}
}

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

Clock Short Hand and Long Hand

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0135
時計の針を題材にした問題。
昔書いたコードが自分基準ではエレガントすぎてこれ以上のコードを思いつかない状態。
単位角度を半分で計算することで綺麗な処理になっている。

昔書いたコード。
一分回ると時針が０．５度回るので単位角度を半分にしている。

#include<stdio.h>
#include<stdlib.h>
int main(){
    int n,s,t,r;
    scanf("%d",&n);
    while(n--){
        scanf("%d:%d",&s,&t);
        r=abs(s*60-t*11);
        r=r>360?720-r:ｒ;
        printf("%s\n",r<60?"alert":r<180?"warning":"safe");
    }
}

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

Exit Survey

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

集計して平均を出すだけの問題。

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

int main(){
long long int n,sum=0,a;
std::cin>>n;
for(int i=0;i<n;i++){
std::cin>>a;
sum+=a;
}
std::cout<<sum/n<<"\n";
}

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

Rotation of a Pattern

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

解法
基本情報技術者でおなじみの画像を９０度回転することを題材にした問題です
そのまま書くだけ。

#include<stdio.h>
#include<string.h>
void round(char a[8][9],int r){
    char b[8][9];
    for(int i=0;i<64;i++){
        b[i%8][7-i/8]=a[i/8][i%8];
        b[i/8][8]='\0';
    }
    memcpy(a,b,72);
    printf("%d\n",r);
    for(int i=0;i<8;i++){
        printf("%s\n",a[i]);
    }
}
int main(){
    char a[8][9];
    for(int i=0;i<8;i++)scanf("%s",a[i]);
    round(a,90);
    round(a,180);
    round(a,270);
}

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

Doctor's Strange Particles

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0131
博士の奇妙なライツアウトを題材にした問題。



ビット演算に置き換えて解。
一行目の押し方が決まれば残りの行は全自動で決まります。
というわけで一つのデータセットに対し１０２４通りを調べるだけです。
多分一番コードが長い人は行列演算を使って探索空間を狭めてるのだと思います。
このコードの成績、コードの短さ2/154位。
平凡な結果です。
ショートコードを狙ったわけではないのでまあこんなものです。

私の場合、コードや処理を簡潔にした結果として短くなっているだけです。
コードの簡潔さと難読化の境界線上に到達したらそれ以上コードを短くしません。


#include<stdio.h>


void calc(){
      int board[10],e,push[10],a,r,b,up,oldUp;
      int mask=(1<<10)-1;
      for(int i=0;i<10;i++){
            e=1;
            r=0;
            for(int j=0;j<10;j++){
                  scanf("%d",&a);
                  r+=e*a;
                  e=e<<1;
            }
            board[i]=r;
      }
      for(int p=0;p<=mask;p++){
            up=p;
            oldUp=0;
            bool hit=false;
            for(int k=0;k<10;k++){
                  push[k]=up;
                  a=up;
                  up=(board[k]^(oldUp)^(up<<1)^(up)^(up>>1))&mask;
                  oldUp=a;
                  if(k==9&&up==0){
                        hit=true;
                        break;
                  }
            }
            if(hit==true)break;
      }
      for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                  printf("%d%s",push[i]%2,j==9?"\n":" ");
                  push[i]/=2;
            }
      }
}


int main(){
      int n;
      scanf("%d",&n);
      while(n--){
            calc();
      }
}

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

Ｔｒａｉｎ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0130
電車の車掌を題材にした問題。


とりあえずどこかわからないので。
配列の真ん中からスタートして左右を埋めていくだけです。
コードの短さ９/200位、発想も順位も平凡。


#include<stdio.h>
void commit(){
      char ws[60]={0},p=30,c,d;
      while(scanf("%c%c",&c,&d)){
            ws[p]=c;
            if(d=='\n')break;
            scanf("%c",&c);
            p+=c=='>'?1:-1;
      }
      for(int i=0;i<60;i++){
            if(ws[i]!=0)printf("%c",ws[i]);
      }
      printf("\n");
}

int main(){
      int n;
      char c;
      scanf("%d%c",&n,&c);
      while(n--){
            commit();
      }
}

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

Hide-and-Seek Supporting System
かくれんぼを題材にした問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0129


特にショートコードを狙ったわけではないがコード短さ１５/168位。
まあまあの結果だと思う、この問題では昔この問題を解いたときに書いたコードを抜けた気がする。
この問題でもpldwさんがコードの短さで突出している。
彼（彼女？）はいったいどんな人物なのだろう。


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

int main(){
    int n,m;
   
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        double wallXs[101],wallYs[101],wallRs[101],px,py,ex,ey,lenP,lenE,r;
        double pDx,pDy,eDx,eDy,peDx,peDy,n1,n2,len3,peLen;
        for(int i=0;i<n;i++){
            scanf("%lf %lf %lf",&wallXs[i],&wallYs[i],&wallRs[i]);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%lf %lf %lf %lf",&px,&py,&ex,&ey);
            bool danger=true;
            for(int j=0;j<n;j++){
                pDx=wallXs[j]-px;
                pDy=wallYs[j]-py;
                eDx=wallXs[j]-ex;
                eDy=wallYs[j]-ey;
                lenP=hypot(pDx,pDy);
                lenE=hypot(eDx,eDy);
                r=wallRs[j];
               //自分と相手が円の内と外の関係
                if((lenP<r&&lenE>r)||(lenP>r&&lenE<r)){
                    danger=false;
                    break;
                }
                //同じ円内にいる
                if(lenP<r&&lenE<r){
                    continue;
                }
                //円から線分へおろした垂線と重なる直線。これからなる半開平面の両側に自分と相手がいるかチェック
                peDx=ex-px;
                peDy=ey-py;
                peLen=hypot(peDx,peDy);
                n1=peDx*pDx+peDy*pDy;
                n2=peDx*eDx+peDy*eDy;
                if((n1<0&&n2>0)||(n1>0&&n2<0)){
                    len3=fabs((pDx*peDy-pDy*peDx)/peLen);
                    //両側にいたので線分と円の距離が条件を満たすか調べる
                    if(len3<=r){
                        danger=false;
                        break;
                    }
                }
            }
            printf("%s\n",danger?"Danger":"Safe");
        }
    }
}

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

Abacus
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0128
そろばんを題材にした問題。

この問題そろばんを９０度回して、全部*で埋めている状態から*を削ってそろばんの一つの列（９０度まわしてるから行だけど）を生成すると考えると綺麗に解けます。
というか昔の自分はそうやって解いたようです。


うーんＡＯＪの問題を復習中なのですが昔の自分のコードに勝てる気がしない。
Ｐｒｏｌｏｇ言語のやりすぎでなんでも列挙する方向だけから考えるという悪い癖がついたな。
昔の自分のほうがアプローチが柔軟だ。



昔のコード。
#include<stdio.h>
#include<string.h>
void change(int num,char* re){
    //*をけずって一列を作る処理
    strcpy(re,"**=*****");
    re[-(num/5-1)]=' ';
    re[num%5+3]=' ';
}
int main(){
    char ans[5][9];
    int n,c=0;
    while(scanf("%d",&n)!=EOF){
        printf("%s",c==0?"":"\n");
        c++;
        for(int i=4;i>=0;i--){
            change(n%10,ans[i]);
            n/=10;
        }
        //縦と横を元に戻して表示
        for(int i=0;i<8;i++){
            for(int j=0;j<5;j++)printf("%c",ans[j][i]);
            printf("\n");
        }
    }
}

会津大学オンラインジャッジ 問127 Pocket Pager Input

ポケベルを題材にした問題。
今の若者にポケベルは通用するのだろうか？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0127

ＡＯＪの問題を復習中でこの問題もその一つなのですが。
昔自分が書いたコードのほうが賢かったので賢いほうを掲載。
なるほど文字数が合わなければ途中で処理に失敗してるわけか。
昔の自分賢いな、感心。
今の自分頭悪いな。


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

char memo[6][6]={"abcde","fghij","klmno","pqrst","uvwxy","z.?! "};

int main(){
    char mes[201],ans[101];
    int p,len,t1,t2;
    while(scanf("%s",mes)!=EOF){
        len=strlen(mes);
        p=0;
        if(len%2==0){
            while(p<len){
                t1=mes[p];
                t2=mes[p+1];
                if(t1<'1' || '6'<t1 || t2<'1' || '5'<t2){
                    break;
                }else{
                    ans[p/2]=memo[t1-'1'][t2-'1'];
                    p+=2;
                }
            }
        }
        ans[len/2]='\0';
        printf("%s\n",p>=len?ans:"NA");
    }
}

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

Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0126
数独で間違った回答の間違ってる部分にチェックをつける問題。


行、列　３*３で数えて２つ以上重なってるものに*をつけるだけです。
結構エレガントに書けた気はするがショートコーダーから見たらきっとこのコードは長い。
７００バイト１２位、特にショートコードを狙ったわけでもないのでまあまあの順位に思えるが。
１位は２６４バイトなので２位以下か１位かという区別しか意味がない。



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

void check(){
      int rows[9][10],cols[9][10],cell33[3][3][10];
      int board[9][9],num;
      memset(cell33,0,sizeof(cell33));
      memset(rows,0,sizeof(rows));
      memset(cols,0,sizeof(cols));
   
      for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                  scanf("%d",&num);
                  rows[i][num]++;
                  cols[j][num]++;
                  cell33[i/3][j/3][num]++;
                  board[i][j]=num;
            }
      }
      for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                  int num=board[i][j];
                  if(rows[i][num]>1||cols[j][num]>1||cell33[i/3][j/3][num]>1){
                        printf("*%d",num);
                  }else{
                        printf(" %d",num);
                  }
            }
            printf("\n");
      }
}

int main(){
      int n;
      scanf("%d",&n);
      for(int i=0;i<n;i++){
            check();
            if(i+1<n)printf("\n");
      }
}

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

Day Count
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0125
２つの日付の間の日数をこたえる問題。


ネット上に転がっていた日数計算公式をそのまま採用。
http://ufcpp.net/study/algorithm/o_days.html



#include<stdio.h>
int calcDays(int y,int m,int d){
if(m<=2){
--y;
m+=12;
}
int dy=365*(y-1);
int c=y/100;
int dl=(y>>2)-c+(c>>2);
int dm=(m*979-1033)>>5;
return dy+dl+dm+d-1;
}

int main(){
int y,m,d,y1,m1,d1;
while(scanf("%d %d %d %d %d %d",&y,&m,&d,&y1,&m1,&d1)!=EOF){
if(y1==-1)break;
printf("%d\n",calcDays(y1,m1,d1)-calcDays(y,m,d));
}
}

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

League Match Score Sheet

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0124
サッカー試合のスコアを計算する問題。


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

struct S{
std::string name;
int score,no;
bool operator<(const S& s)const{
if(score!=s.score)return score<s.score;
return no>s.no;
}
};

void rank(int n){
S s;
int v,loss,b;
std::priority_queue<S> pq;
for(int i=0;i<n;i++){
std::cin>>s.name>>v>>loss>>b;
s.no=i;
s.score=v*3+b;
pq.push(s);
}
while(pq.empty()==false){
s=pq.top();
pq.pop();
std::cout<<s.name<<","<<s.score<<"\n";
}

}

int main(){
int n,c=0;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
if(c>0)printf("\n");
rank(n);
c++;
}
}

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

Speed Skating Badge Test

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0123
スピードスケートのランク付けを行う問題。
500ｍでＡＡランクなら1000ｍでＡＡＡをとっても意味がない。
これを利用して1000m判定のｒ２の検証を減らします。
こういう簡単な判定では意味がありませんが重たい判定ではこういう小手先のテクニックもすこしは役に立つかもしれません。
まあその前にバイナリサーチを導入するとは思いますが。


#include<stdio.h>

int main(){
char kekka[8][4]={
"AAA",
"AA",
"A",
"B",
"C",
"D",
"E",
"NA"};
double M500[8] ={35.5,37.5,40,43,50,55,70};
double M1000[8]={71,77,83,89,105,116,148};
double t500,t1000;
while(scanf("%lf %lf",&t500,&t1000)!=EOF){
int r1=7,r2=7;
for(int i=0;i<7;i++){
if(t500<M500[i]){
r1=i;
break;
}
}
for(int i=r1;i<7;i++){
if(t1000<M1000[i]){
r2=i;
break;
}
}
printf("%s\n",kekka[r2]);
}
}

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

Summer of Phyonkichi
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122

カエルのぴょんきちが夏を乗り切れるかをこたえる問題。
動的計画法で十分です。



#include<stdio.h>
#include<set>
#include<stdlib.h>

struct S{
int x,y;
bool operator<(const S& s)const{
if(x!=s.x)return x<s.x;
return y<s.y;
}
};

void search(int x,int y){
S s1;
s1.x=x;
s1.y=y;
std::set<S> sets[2];
sets[0].insert(s1);
int n;
scanf("%d",&n);
int dx[]={ 2, 2, 2, 1, 1, 0, 0,-1,-1,-2,-2,-2};
int dy[]={ 1, 0,-1, 2,-2, 2,-2, 2,-2, 1, 0,-1};
int sx,sy,now,next;
for(int i=0;i<n;i++){
scanf("%d %d",&sx,&sy);
now =i%2;
next=(i+1)%2;
for(std::set<S>::iterator it=sets[now].begin();it!=sets[now].end();it++){
s1=(*it);
for(int j=0;j<12;j++){
s1.x+=dx[j];
s1.y+=dy[j];
if(0<=s1.x||s1.x<=9||0<=s1.y||s1.y<=9){
if(abs(sx-s1.x)<=1&&abs(sy-s1.y)<=1){
sets[next].insert(s1);
}
}
s1.x-=dx[j];
s1.y-=dy[j];
}
}
sets[now].clear();
}
printf("%s\n",sets[next].empty()==false?"OK":"NA");
}

int main(){
int x,y;
while(scanf("%d %d",&x,&y)!=EOF){
if(x==0&&y==0)break;
search(x,y);
}
}

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

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

セブンパズルを題材にした問題。



平凡な問題なので平凡なコードで平凡な順位。

平凡な問題と考え
平凡なコードで理解をし
平凡なコードの手順を考え
平凡なコードを実装し
平凡なコードを提出し
平凡な結果を期待し
平凡な順位に落ち着く。
私こそミスター平凡。


完全ハッシュ関数を実装すればもう少し早くはなるとおもいます。



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

struct S{
int zeroP,count;
int board[8];
bool operator<(const S& s)const{
for(int i=0;i<8;i++){
if(board[i]!=s.board[i])return board[i]<s.board[i];
}
return false;
}
};

int main(){
int moves[8][3]={{0,1,4},
{0,2,5},
{1,6,3},
{2,7,3},
{0,5,4},
{1,4,6},
{2,5,7},
{3,6,7}};
S s,s2;
s.zeroP=0;
s.count=0;
for(int i=0;i<8;i++){
s.board[i]=i;
}
std::map<S,int> memo;
std::queue<S> qu;
qu.push(s);
while(qu.empty()==false){
s=qu.front();
qu.pop();
if(memo.find(s)!=memo.end())continue;
memo[s]=s.count;
s.count++;

for(int i=0;i<3;i++){
s2=s;
s2.zeroP=moves[s.zeroP][i];
if(s.zeroP==s2.zeroP)continue;
std::swap(s2.board[s.zeroP],s2.board[s2.zeroP]);
if(memo.find(s2)!=memo.end())continue;
qu.push(s2);
}
}
while(1){
if(scanf("%d",&s.board[0])==EOF)break;
for(int i=1;i<8;i++){
scanf("%d",&s.board[i]);
}
printf("%d\n",memo[s]);
}
}

プロジェクトオイラー 失敗作 問258

プロジェクトオイラー問258を解くコードを書こうとして失敗しました。


解法
数字列を2000個ごとで一行として、その行から次の行を求める漸化式を考えます。
漸化式を立てると一行先を求める漸化式の係数から2行先を求める漸化式の係数が。
2行先を求める漸化式の係数から4行先がと求まります。
以後同じ処理を繰り返すことで2倍2倍で増える先の行を求める漸化式が手に入ります。
がこれは10＾18をそのまま愚直に求めるのより単純計算200万倍速いだけで、ループ処理が入るのでさらに遅くなり、コードを実行したところ正しい答えが出るまで23時間もかかりました。
私の使ってるパソコンかＢＣＣ5.5どちらが悪いのかわかりませんがコンパイル結果のＭｏｄ演算が妙に遅いということを加味してもこれは恥ずべき結果です。




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


const int LIMITER=2000;
const __int64 MOD=20092010;

struct Vec{
__int64 es[LIMITER];
void add_and_mult(Vec& v,int t){
for(int i=0;i<LIMITER;i++){
es[i]=(es[i]+v.es[i]*t)%MOD;
}
}
void reset(){
memset(es,0,sizeof(es));
}
};

int main(){
std::vector<Vec> dp[2];
Vec v1,v2,v3;
__int64 row=pow(10,18);
row=row/LIMITER;
std::cout<<row<<"\n";
v1.reset();
for(int i=0;i<LIMITER;i++){
dp[1].push_back(v1);
}

for(int i=0;i+1<LIMITER;i++){
v1.reset();
v1.es[i]=v1.es[i+1]=1;
dp[0].push_back(v1);
}
v1.reset();
v1.es[0]=v1.es[1]=v1.es[LIMITER-1]=1;
dp[0].push_back(v1);

__int64 rowData[2][LIMITER];
for(int i=0;i<LIMITER;i++)rowData[0][i]=1;
__int64 add,ans=1;
int turn=0;
int point=0;
while(row>0){
std::cout<<"\n row="<<row<<" ";
if(row%2==1){
int now=point;
int next=(point+1)%2;
int now1=turn%2;
memset(rowData[next],0,sizeof(rowData[next]));
for(int i=0;i<LIMITER;i++){
for(int j=0;j<LIMITER;j++){
add=(rowData[now][j]*dp[now1][i].es[j])%MOD;
rowData[next][i]=(rowData[next][i]+add)%MOD;
}
}
std::cout<<" ans="<<rowData[next][0];
point=(point+1)%2;
ans=rowData[next][0];
}
int now=turn%2;
int next=(turn+1)%2;
for(int i=0;i<LIMITER;i++){
dp[next][i].reset();
for(int j=0;j<LIMITER;j++){
if(dp[now][i].es[j]==0)continue;
dp[next][i].add_and_mult(dp[now][j],dp[now][i].es[j]);
}
}
turn++;
row/=2;
}
std::cout<<"\n lastAns="<<ans;
}