std::setでデータ同士の間に順位付けができないと無視されてしまう件
#include <stdio.h> #include <set> using namespace std; struct Data{ int a,b; }; Data makeD(int aa,int bb){ Data d; d.a=aa,d.b=bb; return d; } bool operator < (const Data &d,const Data &e){ return d.a<e.a; } int main(){ set<Data> se; se.insert(makeD(0,1)); se.insert(makeD(0,2)); printf("se.size()==%d\n",se.size()); for(set<Data>::iterator it=se.begin();it!=se.end();it++) printf("a=%d b=%d\n",(*it).a,(*it).b); return 0; }
を実行すると
se.size()==1
a=0 b=1
となってしまう。
これはsetが(0,1)と(0,2)の違いを分からないからである。
se.size()==2
a=0 b=1
a=0 b=2
このようにするには
bool operator < (const Data &d,const Data &e){ if(d.a==e.a) //<= return d.b<e.b; //<= return d.a<e.a; }
こんな風に書き換えると良い。
HaskellでBrainfuckの処理系を実装する
課題
'.' ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
IOモナドを使いたくない(使えない）のでマシン状態の中にディスプレイを作って処理した。
',' 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
複雑になりそうだったので実装しなかった。
-- Brainfuck.hs import Data.Char main = do cs <- getContents putStrLn $ runBrainfuck cs runBrainfuck p = display $ runOneStep $ Machine p 0 [0,0..] 0 "" runOneStep (Machine a b c d e) = if (length a) == b then Machine a b c d e else runOneStep $ incrementProgramPointer func where func = case (a!!b) of '>' -> incrementPointer (Machine a b c d e) '<' -> decrementPointer (Machine a b c d e) '+' -> incrementMemory (Machine a b c d e) '-' -> decrementMemory (Machine a b c d e) '.' -> putCharToDisplay (Machine a b c d e) ']' -> jumpEnd (Machine a b c d e) '[' -> jumpStart (Machine a b c d e) otherwise -> (Machine a b c d e) incrementProgramPointer (Machine a b c d e) = Machine a (b+1) c d e data Machine = Machine { program::String,programPointer::Int,memory::[Int],memoryPointer::Int,display::String } deriving Show incrementPointer (Machine a b c d e) = Machine a b c (d+1) e decrementPointer (Machine a b c d e) = Machine a b c (d-1) e putCharToDisplay (Machine a b c d e) = Machine a b c d (e++[chr (c!!d)]) incrementMemory (Machine a b c d e) = Machine a b (changeMemory c 0 d (+ 1))d e decrementMemory (Machine a b c d e) = Machine a b (changeMemory c 0 d (subtract 1))d e jumpStart (Machine a b c d e) = if (c!!d)==0 then Machine a (func 0 b) c d e else Machine a b c d e where func depth pos = case (a!!pos) of '[' -> func (depth+1) (pos+1) ']' -> if depth==1 then pos else func (depth-1) (pos+1) otherwise -> func depth (pos+1) jumpEnd (Machine a b c d e) = if(c!!d)==0 then Machine a b c d e else Machine a (func 0 b) c d e where func depth pos = case (a!!pos) of '[' -> if depth==1 then pos else func (depth-1) (pos-1) ']' -> func (depth+1) (pos-1) otherwise -> func depth (pos-1) changeMemory [] i k f = [] changeMemory (x:mem) i k f = if i==k then f x:mem else x:changeMemory mem (i+1) k f
情報オリンピックの過去問の入出力をチェックするのに便利だったコマンド
nkf -Lu -overwrite TEST.txt
とやるとファイル中のCRLFが全てLFになって便利だった。
Factorial: 階乗
解法
- nを素因数分解して
- p1^e1*p2^e2*p3^e3*......pr^erとなったとき、 m1!%p1^e1==0,m2!%p2^e2,m3!%p3^e3,.....となる
- 最小のm1,m2,m3...を求めて
- m1,m2,m3....の中で最も大きな値が答え
#include <stdio.h> #include <vector> #include <map> using namespace std; typedef long long LL; vector<pair<LL,int> > primeFactor(LL num){ //first->prime,second->pow{ if(num==1){ vector<pair<LL,int> > r; r.push_back(make_pair(1,1)); return r; } else{ vector<pair<LL,int> > r; for(LL i=2;i*i<=num;i++){ if(num%i==0){ int p=0; while(num%i==0) num/=i,p++; r.push_back(make_pair(i,p)); } } if(num!=1) r.push_back(make_pair(num,1)); return r; } } int main(){ LL n; scanf("%lld",&n); vector<pair<LL,int> > ps=primeFactor(n); LL res=0; for(int i=0;i<(int)ps.size();i++){ LL a=0,b=ps[i].second; while(0<b){ a+=ps[i].first; for(LL t=ps[i].first;a%t==0;t*=ps[i].first) b--; } res=max(res,a); } printf("%lld\n",res); return 0; }
AOJ 1203
- 問題文要約
記号を含む文字列が与えられるので、記号を除いて小文字を大文字に変換した後その文字列が含む回文を列挙せよ。ただしcXcとなる回文が存在した場合Xを出力してはならない。
- 解法
dp[i][j]=(i文字目からj文字目までが回文となっているかどうか) でDPする。
#include <string> #include <iostream> #include <set> #include <string.h> using namespace std; int dp[1030][1030]; int main(){ string s; while(getline(cin,s)){ string in; for(int i=0;i<(int)s.size();i++) if('A'<=s[i]&&s[i]<='Z') in+=s[i]; else if('a'<=s[i]&&s[i]<='z') in+=s[i]-'a'+'A'; int n=in.size(); memset(dp,0,sizeof(dp)); set<string> ans,ng; for(int i=0;i<n;i++) dp[i][i]=1,dp[i][i+1]=1; for(int l=2;l<=n;l++) for(int i=0;i+l<=n;i++) if(dp[i+1][i+1+l-2]==1&&in[i]==in[i+l-1]){ dp[i+1][i+l-2]=0; ng.insert(in.substr(i+1,l-2)); dp[i][i+l]=1; ans.insert(in.substr(i,l)); } for(set<string>::iterator it=ans.begin();it!=ans.end();it++) if(3<=(*it).size()&&ng.find(*it)==ng.end()) cout<<*it<<" "; cout<<endl; } return 0; }
AOJ 1204
- 解法
最後のnクロックの状態と次にpipelineに入れられる仕事の番号を使って拡張ダイクストラをする。int dist[21][1<<20]とかやるとMLEするのでsetを使う。
//AOJ1204 #include <stdio.h> #include <vector> #include <string> #include <string.h> #include <queue> #include <map> #include <set> #define INF (1<<20) #define W 10 using namespace std; struct State{ int time,next,line; }; State makeS(int t,int nn,int l){ State s; s.time=t,s.next=nn,s.line=l; return s; } bool operator < (const State &s,const State &t){ return s.time>t.time; } int n; int used[5]; char as[5][30]; int pi[30]; int check(int line){ memset(used,0,sizeof(used)); for(int i=n-1;0<=i;i--) if(line&(1<<i)) used[pi[n-1-i]]++; for(int i=0;i<5;i++) if(1<used[i]) return 0; return 1; } int main(){ while(1){ scanf("%d",&n); if(n==0) break; for(int i=0;i<5;i++)scanf("%s",as[i]); for(int i=0;i<n;i++)for(int j=0;j<5;j++)if(as[j][i]=='X')pi[i]=j; int ans; priority_queue<State> que; set<pair<int,int> > se; que.push(makeS(0,0,0)); se.insert(make_pair(0,0)); while(!que.empty()){ State s=que.top();que.pop(); if(s.next==10&&s.line==1){ans=s.time;break;} int l=s.line>>1,ok=check(l); if(!ok) continue; if(s.next==W){ if(se.find(make_pair(W,l))==se.end()){ se.insert(make_pair(W,l)); que.push(makeS(s.time+1,W,l)); } }else{ int ll=l|(1<<(n-1)); if(check(ll)){ if(se.find(make_pair(s.next+1,ll))==se.end()){ se.insert(make_pair(s.next+1,ll)); que.push(makeS(s.time+1,s.next+1,ll)); } } if(se.find(make_pair(s.next,l))==se.end()){ se.insert(make_pair(s.next,l)); que.push(makeS(s.time+1,s.next,l)); } } } printf("%d\n",ans); } }
