AOJ2644 - Longest Match
ratingを上げるために新しい問題を解こうと思ったら、ちょうど練習したかったsuffix arrayの問題がありました。例外処理(文字列が存在しない場合)が難しく、とりあえず思いつく限りの条件を列挙したのでコードは汚いです。
問題：
Longest Match | Aizu Online Judge
問題概要：
文字列Sとm個のクエリが与えられる。それぞれのクエリについて文字列xと文字列yが与えられ、xで始まりyで終わるSの部分文字列の長さの最大値を求める。
解法：
suffix arrayとsegment treeを用いました。
コード：
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> #define mp make_pair #define pb push_back #define INF 100000005 #define rep(i,n) for(int i = 0;i < n;i++) using namespace std; int sa[200005],rk[200005],tmp[200005]; string S,T; int kk; int len; int sg[2][1<<19];//[0]が最小値、[1]が最大値を保持 bool compare_sa(int i,int j){ if(rk[i]!=rk[j]){ return rk[i]<rk[j]; }else{ int ri = (i+kk<len)?rk[i+kk]:-1; int rj = (j+kk<len)?rk[j+kk]:-1; return ri<rj; } } void construct_sa(){ len=(int)S.length(); rep(i,len+1){ sa[i]=i; rk[i]=(i<len)?S[i]:-1; } for(kk=1;kk<=len;kk*=2){ sort(sa,sa+len+1,compare_sa); tmp[sa[0]]=0; for(int i = 1;i<=len;i++){ tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0); } rep(i,len+1){ rk[i]=tmp[i]; } } } void update(bool f,int p,int x){//sg[f]のp番目にxを挿入 p+=(1<<18)-1; sg[f][p]=x; while(p>0){ p=(p-1)/2; sg[f][p]=(f?max(sg[f][p],x):min(sg[f][p],x)); } } int query(bool f,int a,int b,int k,int l,int r){ if(r<=a||b<=l)return f?-INF:INF; if(a<=l&&r<=b)return sg[f][k]; else{ int mid = (l+r)/2; int vl=query(f,a,b,k*2+1,l,mid); int vr=query(f,a,b,k*2+2,mid,r); int ret=(f?max(vl,vr):min(vl,vr)); return ret; } } int query(bool f,int a,int b){ return query(f,a,b,0,0,(1<<18)); } int search(string t){ int a=0,b=len+1; while(b-a>1){ int c=(a+b)/2; if(S.compare(sa[c],T.length(),T)<0)a=c; else b=c; } return b; } int main(){ cin>>S; rep(i,1<<19){ sg[0][i]=INF; sg[1][i]=-INF; } construct_sa(); rep(i,len+1){ update(0,i,sa[i]); update(1,i,sa[i]); } int testcase; cin>>testcase; while(testcase--){ int checkl; bool flag = 1; int ansl,ansr; int right,left; cin>>T; checkl=(int)T.length(); left = search(T); T[T.length()-1]+=1; right=search(T); if(left==right)flag=0; ansl=query(0,left,right); cin>>T; left = search(T); T[T.length()-1]+=1; right=search(T); if(left==right)flag=0; ansr=query(1,left,right)+(int)T.length(); if(ansl>len||ansl>=ansr)flag=0; if(ansr-ansl<checkl)flag=0; if(flag){ cout<<ansr-ansl<<endl; }else{ cout<<0<<endl; } } }
AOJ1196 - Bridge Removal
簡単な問題ではありますが、久しぶりに書いてみます。
問題概要：
大きさnの木について、自分のいる頂点から出ている辺を取り除く操作と、辺上を頂点から頂点へ移動する操作にそれぞれその辺のコストの分の時間が掛かる。好きな頂点から操作を開始するとき、すべて
の辺を取り除くのに掛かる最短時間を求めよ。
解法：
はじめの木をG、Gから葉を除いた木をG'と書くと、一度しか通らない経路はG'の直径となります。
よって求める時間は
Gの全コスト+G'の全コスト*2-G'の直径
です。
木の直径の求め方は
木の直径を求めるアルゴリズムの証明 - あんまり見ないでください
を参照しました。
コード：
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> #define mp make_pair #define pb push_back #define INF 100000005 #define rep(i,n) for(int i = 0;i < n;i++) using namespace std; typedef pair<int,int> PI; int n; bool erased[805]; vector<PI> G[805]; int dist[805]; void dfs(int s){ rep(i,G[s].size()){ int to=G[s][i].first; if(!erased[to]&&dist[to]>=INF){ dist[to]=G[s][i].second+dist[s]; dfs(to); } } } int main(){ while(1){ int temp; int t[805],ans=0; cin>>n; if(!n){ break; } rep(i,n){ erased[i]=false; G[i].clear(); } rep(i,n-1){ cin>>t[i]; t[i]--; } rep(i,n-1){ cin>>temp; ans+=temp*3; G[i+1].pb(mp(t[i],temp)); G[t[i]].pb(mp(i+1,temp)); } int start = 0; rep(i,n){ if(G[i].size()==1){ ans-=G[i][0].second*2; erased[i]=1; if(i==start){ start++; } } } fill(dist,dist+n,INF); dist[start]=0; dfs(start); rep(i,n){ if(!erased[i]&&dist[i]>dist[start])start=i; } fill(dist,dist+n,INF); dist[start]=0; dfs(start); int hoge = 0; rep(i,n){ if(!erased[i]){ hoge = max(hoge,dist[i]); } } ans -= hoge; cout<<ans<<endl; } return 0; }
ICPC国内予選 - Problem F
ICPC国内予選にKiraKiraJKというチーム名で参加しました。kitayutaがA~C、enkがE、私がDを解いて結果は5完でした。
F、Gはコンテスト中は方針すら立ちませんでしたが、Fはあるさいころの状態から最終状態への移動が可能であるかをO(1)で判定する関数を見つけたら出来ると教えてもらったので書いてみました。
サンプルデータでは通りました。
ICPC国内予選問題↓
http://icpc.iisf.or.jp/2014-waseda/domestic/problems/
//ICPC2014-pre Problem F #include <iostream> #include <cstdio> #define rep(i,n) for(int i =0 ;i<n;i++) using namespace std; /* 0 1 2 3 5 4 */ void acpy(int to[],int from[]){//配列コピー rep(i,6){ to[i]=from[i]; } } void moveS(int arg[]){//南に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[4]+1; arg[1]=temp[0]; arg[2]=temp[2]; arg[3]=temp[1]; arg[4]=temp[3]; arg[5]=temp[5]; } void moveN(int arg[]){//北に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[1]+1; arg[1]=temp[3]; arg[2]=temp[2]; arg[3]=temp[4]; arg[4]=temp[0]; arg[5]=temp[5]; } void moveE(int arg[]){//東に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[5]+1; arg[1]=temp[1]; arg[2]=temp[0]; arg[3]=temp[2]; arg[4]=temp[4]; arg[5]=temp[3]; } void moveW(int arg[]){//西に int temp[6]; rep(i,6){ temp[i]=arg[i]; } arg[0]=temp[2]+1; arg[1]=temp[1]; arg[2]=temp[3]; arg[3]=temp[5]; arg[4]=temp[4]; arg[5]=temp[0]; } bool check(int t[],int arg[]){//判定 int per[6]={0,1,2,3,4,5}; int tnow[6]; bool ans = 0; rep(i,720){ int flag = 1; rep(j,6){ tnow[j]=t[per[j]]-arg[j]; if(tnow[j]<0){ flag = 0; break;} } if(flag != 0) { int now = tnow[0]+tnow[3]; int ne1 = tnow[1]+tnow[4]; int ne2 = tnow[2]+tnow[5]; if(now<=ne1+ne2&&ne1-1 <=now+ne2&&ne2-1 <=now+ne1) //判定してる ans = 1; } if(ans == 1) break; next_permutation(per,per+6); } return ans; } int main(){ int now[6]; int prev[6]; char s[40000]; int t[6]; int sum; int p,q; int fs[6]={0,1,2,3,4,5}; while(1){ sum = 0; rep(i,6){ scanf("%d",t+i); sum += t[i]; } if(sum==0){ break; } scanf("%d %d",&p,&q); bool flag = 1; rep(i,6){ prev[i]=0; } int hoge = 1; rep(sz,sum){ acpy(now,prev); moveE(now); if(check(t,now)){ acpy(prev,now); s[sz]='E'; continue; } acpy(now,prev); moveN(now); if(check(t,now)){ acpy(prev,now); s[sz]='N'; continue; } acpy(now,prev); moveS(now); if(check(t,now)){ acpy(prev,now); s[sz]='S'; continue; } acpy(now,prev); moveW(now); if(check(t,now)){ acpy(prev,now); s[sz]='W'; continue; } hoge = 0; break; } if(hoge == 0){ printf("impossible\n"); }else{ for(int i = p-1;i < q;i++){ printf("%c",s[i]); } printf("\n"); } } }
ほそながいところ
今学期受講している実践的プログラミングという講座で紹介されていた「ほそながいところ」という全探索という問題なのですが、方針は立ったものの実装の仕方が全く解らず、semiexpさんのソースコードをカンニングしながら書きました。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2427
馬車の出発時間としては
「前の馬車が出発してから一分後」である場合と、「他の馬車と、少し広いところかゴールで出会う」が許されています。その全ての組み合わせを試してみる、という方法なのですが実装が全然解りませんでした。
計算量は、O(n^2*m*n!*m^n)程度かと思います。この場合はm≦5,n≦5なので通ったんですかね。
#include <iostream> #include <vector> #include <algorithm> #define rep(i,n) for(int i = 0;i < n;i++) using namespace std; #define INF 1e16 typedef long long lint; bool went[5]={0}; //全探索で、現在使用中かどうかのフラグ lint tm[5]; //馬車の出発時間 lint S[5]; lint dist; lint D[5]; int n,m; lint answer = INF; //答え lint pre; //適切な出発時間であるような、答えの候補 void judge(){ //tmが適切かどうかを判定する(少し広いところとゴール以外で追いつか //ないか・少し広いところで3つ以上の馬車が同時に追いつかないか) vector<pair<lint,lint> > meet; rep(i,n-1){ for(int j = i + 1;j < n;j++){ int hoge = 0; if(S[i] < S[j]||tm[j]-tm[i] >= (S[i]-S[j])*dist) continue; rep(k,m){ if(tm[i]-tm[j] == (S[j]-S[i])*D[k]){ meet.push_back(make_pair(tm[j]+S[j]*D[k],k)); hoge = 1; break; } } if(!hoge){ return; } } } if(!meet.empty()){ sort(meet.begin(),meet.end()); rep(i,meet.size()-1){ //3つ以上の馬車が同時に少し広いところで追いついている if(meet[i] == meet[i+1]) return; } } pre = 0; rep(i,n){ pre = max(pre,tm[i]+dist*S[i]); } answer = min(answer,pre); } void search(int p){ //全探索 pは探索の深さ if(p == 0){ tm[0] = 0; went[0]=1; search(1); return; } rep(i,n-1){ if(went[i] && went[i+1] && tm[i] >= tm[i+1]) return; } if(p == n){ judge(); return; } rep(i,n-1){ if(went[i] && !went[i+1]){ tm[i+1] = tm[i]+1; went[i+1] = 1; search(p+1); went[i+1] = 0; } //!went[i] && went[i+1]の場合は探索しなくてよい //(馬車iは必ずどこかで他の馬車に追いつくから) } rep(i,n){ if(!went[i]){ rep(j,n){ if((i < j && S[i]<S[j])||(i > j && S[i]>S[j])) continue; if(went[j]){ //iとjが少し広いところkで追いつく rep(k,m){ tm[i] = tm[j]+(S[j]-S[i])*D[k]; went[i] = 1; search(p+1); went[i] = 0; } //iとjがゴールで追いつく tm[i] = tm[j]+(S[j]-S[i])*dist; went[i] = 1; search(p+1); went[i] = 0; } } } } } int main(){ cin >> dist; cin >> n; rep(i,n){ cin >> S[i]; } cin >> m; rep(i,m){ cin >> D[i]; } search(0); cout << answer << endl; }
実装力上げたい。
2013=3*6*11
この一年を振り返ってみようと思ったが、あまり思い出せないので手帳を見ながら書いている。時系列に書こうかな〜
＿人人人人人人＿
＞ JOI本選 ＜ （2月）
￣Y^Y^Y^Y^Y￣
JOIの予選は中三の時に一度受けが、その時は落ちてしまった。高一はディベートの試合と被って受けることが出来ず。高二で蟻本を読んで臨んだらやっと本選に通った。JOIのノリを始めは理解できなかったが、今では少し解ったような気がする(震え声)
この時はそこまで多くの人と話すことは出来なかったが、まあ日程も短かったのでしょうがないのかな・・・試験は、2完しかとることが出来ず、春合宿は無理だと思っていたが、なんとか通過出来たので嬉しかった。春合宿までに蟻本を読了しようと決心したが、結局今もまだ読み終えていない。
＿人人人人人人人人人人人＿
＞ IPhO＆IOI選考春合宿 ＜（3月）
￣Y^Y^Y^Y^Y^Y^Y^Y^Y￣
日程が被った・・・orz 結局は物理を優先することにして、情報は4日中の2日間だけ試験を受けることにした。情報は仮に試験を全て受けていたとしても最下位だったと思う。受験終わったらプログラミングもうちょっと頑張ろうw
物理は二年目 だったが、合宿はかなり盛り上がって楽しかった。みなそれぞれに個性的で、スケジュールの空き時間とかにも議論をしたりして楽しかった。久しぶりにこのメンバーでまた集まりたいですね〜。
＿人人人人人人人人人＿
＞ 進級できました ＜
￣Y^Y^Y^Y^Y^Y^Y^￣
特筆することなし。うん、まあ高２で赤点はなかったですし、新たな学年の始まり。
タケノコの季節(多分)
＿人人人人人＿
＞ 文化祭 ＜ （5月）
￣Y^Y^Y^Y￣
感慨深い、最後の文化祭。五年間関わって来た化研を引退していたので、化研は手伝う程度だった。去年に引き続き、T光と踊った。そういえば、T光とは文化祭前以外あまり話さないなぁ(笑)いや、時々一緒に帰ることはあるけど。
それら意外では、生徒会(長)企画の「世界一受けたい授業」と「NED」に参加した(「世界一受けたい授業」は責任者も)。話す内容とか、スライドとか、考えるのは大変であったが、その分終えた時の達成感はとても大きかった。
しかし、後から考えて自分の話が面白くないことを痛感した。はい、黒歴史認定。
- ネタがすべる
- 具体性に欠けていて、どういう文脈でで話をしているのかがよく解らない。
- リズムが悪い
などなど、反省点をあげればきりが無い。実際に話す立場になってみて、Tehuや生徒会長のトークの上手さに改めて感心した。
＿人人人人人＿
＞ 五月祭 ＜ （5月）
￣Y^Y^Y^Y￣
5月って書かなくても解るわw
生徒会長と一緒に行き、ハーバードに進学した先輩の家で一泊した(その先輩はいなかった・・・)科学オリンピックなどで知り合った先輩に会ったり、また新たな知り合いができたりととても楽しかった。生徒会長の誕生会でのプレゼントとかがかなりネタだった()
また、東大生で、うちの高校のOBが主催している「休学を考える会」というものに参加した。本来は大学生が対象のイベントで、休学の前に入学を考えろという突っ込みを各所から戴いたが、実際に参加してみて、このようなイベントを企画出来る人脈と言うのか行動力と言うのか、凄いと感じましたし、とにかくこんな風に大学生活を楽しむことが出来たら最高だなと思った。高校生なのでまだあまり大学とはどのような場なのか解っていないけれども、やっぱり何もしなければ充実したものにはならないので、真に充実したものにするためには高校生の時以上に能動的に行動しなければならないし、必要とあらば自分で楽しむ場を作り出す程度の気合いが必要なのかなと感じた。しかし、静かに勉強したいという思いもある。合格してから考えよう。
だんだん書くのがめんどくさくなって来た。だが夏休みは受験生とは思えないほどの充実っぷりだった。
＿人人人人＿
＞ IPhO ＜ （7月）
￣Y^Y^Y^Y￣
会誌などにも沢山書いけれど、二年目なのでとにかく楽しもうと思って臨んだ。その目標は十二分に達成出来たと思う。しかし二年目なので去年よりも良い成績を残したいと思っていたが、結局銀メダルだったのはそうは言っても残念。やはり、金メダルを何としてもとってやろうという気迫と、それに見合う努力や演習量がなかったからなのかなと思った 。結果が悪くても後から「え、なんで？こんなに頑張ったのに」とすら思えなかったのが一番残念だった。次の入試は後悔のないように乗り切りたい。というか、今後の人生、すべてのことに対して言い訳せずに全力で臨んで行きたい。
＿人人人人人人＿
＞ 東大プレ ＜ （7月）
￣Y^Y^Y^Y^Y￣
英語：20点
数学：13点
国語：3点
物理：6点
化学：11点
英語は予想していたよりも良かった。以上。
＿人人人人人人人人人＿
＞ 物理チャレンジ ＜ （8月）
￣Y^Y^Y^Y^Y^Y^Y^￣
懐かしいメンバーとの再会も多く、しかし代表や代表候補の人で来ていない人が多かったのが残念。6年間参加したイベントも今年で最後で、これからはOBとしても関わって行きたいです。
＿人人人人人人＿
＞ 東北合宿 ＜ （8月）
￣Y^Y^Y^Y^Y^￣
年来参加したいと思ってはいたのだが、日程がようやく他のものとは重ならずに参加することが出来た。色々な人のお話を聴くと言う形式の合宿ではあったが、実際に行ってみないと気づかないことばかりだったので本当に参加してよかったと思っている。修学旅行でも来てくれたわけだし、福島高校との交流なども続けていってほしい。
＿人人人人人＿
＞ #JOIss ＜ （8月）
￣Y^Y^Y^Y￣
#トレンド入りおめでとうございます！
#トレンド入りおめでとうございます！
雑い
＿人人人人人＿
＞ 体育祭 ＜ （9月）
￣Y^Y^Y^Y￣
まさかの団長。部活以外で後輩と関わる数少ない機会だった。別に大してキレてないのにメーリスでキレた文体で「練習しろ」みたいなメールを送ったのも今となっては良い思い出。最後に色紙を貰った時は泣きそうなほど嬉しかった。
今は母がおせち料理を作ってくれている。今年の年末はだらだらはしていられない・・・。さて、このブログを書いている時間を勉強にまわしたら単語を幾つ覚えられたでしょうか。ではノシ
