1145 The Genome Database of All Space Life
まずは100万文字と少ない文字数なので再帰下降構文解析をやって愚直に求めるコードを書いてみた。
高速に動くコードをテストするための自前採点用データ製作機としての役割としてつくっただけでコードは単なる踏み台。
それを改良してと考えたらほんの6行コードを足しただけで高速化できた。
数行つけたしただけで高速化するなんてプログラムってちょっと面白い。
#include<stdio.h>
int p,i,count;
char s[101];
bool last;
void saiki(int re,int p1){
int nextCount=count;
for(int j=0;j<re;j++){
if(j==1)nextCount=count-nextCount;
if(j>0&&count+nextCount<=i){
count+=nextCount;
continue;
}
p=p1;
while(s[p]!='\0'){
char t=s[p];
if(t=='('){
if(last==true)return ;
saiki(re,p1+1);
break ;
}else if('0'<=t&&t<='9'){
int num=0;
while('0'<=s[p]&&s[p]<='9'){
num=num*10+s[p]-'0';
p++;
}
if(last==true)return;
if('A'<=s[p]&&s[p]<='Z'){
while(num--){
//printf("%c",s[p]);
if(count==i&&last==false){
last=true;
printf("%c\n",s[p]);
return ;
}
count++;
}
}else{
saiki(num,p);
}
}else if(t==')'){
//閉じかっこなので上の関数に戻る
return ;
}else{
//英文字
while('A'<=s[p]&&s[p]<='Z'){
//printf("%c",s[p]);
if(count==i&&last==false){
printf("%c\n",s[p]);
last=true;
return;
}
count++;
p++;
}
p--;
}
if(last==true)return ;
p++;
}
}
}
int main(){
while(1){
scanf("%s %d",s,&i);
if(s[0]=='0'&&s[1]=='\0'&&i==0)break;
count=p=0;
last=false;
saiki(1,0);
if(last==false)printf("0\n");
}
}
1147 ICPC Score Totalizer Software
一番簡単な部類の問題なので何も考える必要がありません。
#include<stdio.h>
#include<algorithm>
int main(){
int n,nMin,nMax,a,sum;
while(1){
scanf("%d",&n);
if(n==0)break;
scanf("%d",&sum);
nMax=nMin=sum;
for(int i=1;i<n;i++){
scanf("%d",&a);
sum+=a;
nMin=std::min(a,nMin);
nMax=std::max(a,nMax);
}
printf("%d\n",(sum-nMin-nMax)/(n-2));
}
}
1148 Analyzing Login/Logout Records
マップに放り込んでソートして状態遷移マシンに食わして集計するだけです。
#include<stdio.h>
#include<map>
//あかん、夏バテでコードを検証する気力が欠片も起きない、、、
struct Log{
int no,time;
bool operator<(const Log& l)const{
if(no!=l.no)return no<l.no;//ナンバー順
return time<l.time;//時刻順
}
};
void setData(){
Log l1;
int n,s,r,q,last;
std::map<Log,int> memo;
std::map<Log,int>::iterator it;
scanf("%d",&r);
while(r--){
scanf("%d %d %d %d",&l1.time,&n,&l1.no,&s);
s=s==0?-1:1;
if(memo.find(l1)!=memo.end()){
memo[l1]+=s;
}else{
memo[l1]=s;
}
}
n=-1;
int count;
for(it=memo.begin();it!=memo.end();it++){
if((*it).first.no!=n){
n=(*it).first.no;
count=0;
}
count+=(*it).second;
(*it).second=count;
}
int sTime,ans;
scanf("%d",&q);
while(q--){
scanf("%d %d %d",&l1.time,&last,&l1.no);
ans=0;
it=memo.upper_bound(l1);
if(it!=memo.begin())it--;
if((*it).first.no!=l1.no&&it!=memo.end())it++;
if(it==memo.end()||(*it).first.no!=l1.no){
printf("0\n");
continue;
}
bool isFirst;
if((*it).second==0){
isFirst=true;
}else{
isFirst=false;
sTime=std::max(l1.time,(*it).first.time);
}
if(memo.end()!=it)it++;
while(it!=memo.end()&&(*it).first.no==l1.no&&(*it).first.time<=last){
if((*it).second!=0){
if(isFirst==true){
sTime=(*it).first.time;
isFirst=false;
}
}else{
if(isFirst==false){
ans+=(*it).first.time-sTime;
isFirst=true;
}
}
it++;
}
if(isFirst==false){
if(last>=sTime)ans+=last-sTime;
}
printf("%d\n",ans);
}
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0&&m==0)break;
setData();
}
}
1150 Cliff Climbing
#include<stdio.h>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#include <stdlib.h>
#include<vector>
struct point{
int x,y;
bool operator<(const point& p)const{
if(x!=p.x)return x<p.x;
return y<p.y;
}
};
struct state{
int x,y,turn,LR;//-1なら左足、1なら右足を動かす
};
class turnSorter {
public:
bool operator()(const state& l, const state& r) const {
return l.turn>r.turn;
}
};
class posSorter {
public:
bool operator()(const state& l, const state& r) const {
if(l.x!=r.x)return l.x<r.x;
if(l.y!=r.y)return l.y<r.y;
return l.LR<r.LR;
}
};
void setData(int w,int h){
std::map<state,int,posSorter> memo;
std::priority_queue<state,std::vector<state>,turnSorter> pQ;
char map[62][32],c,ts[2];
state s,nextS;
s.turn=0;
std::set<point> goals;
point p;
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
scanf("%s",ts);
map[y][x]=ts[0];
if('0'<=map[y][x]&&map[y][x]<='9')map[y][x]-='0';
if(map[y][x]=='X')map[y][x]=-1;//-1は進入不可
if(map[y][x]=='S'){
map[y][x]=0;
s.x=x;
s.y=y;
s.LR=1;
pQ.push(s);
s.LR=-1;
pQ.push(s);
}
if(map[y][x]=='T'){
map[y][x]=0;
p.x=x;
p.y=y;
goals.insert(p);
}
}
}
//スタートの設定
int dxs[]={1,1,1, 1, 1,2,2, 2,3};//右足の移動、xに-1を掛けて左足に転用する
int dys[]={2,1,0,-1,-2,1,0,-1,0};//9マス
bool goalOK=false;
//メモ化による枝刈つき幅優先探索
while(!pQ.empty()){
s=pQ.top();
pQ.pop();
p.x=s.x;
p.y=s.y;
if(goals.find(p)!=goals.end()){
goalOK=true;
break;
}
if(memo.find(s)!=memo.end()&&memo[s]<s.turn)continue;
memo[s]=s.turn;
nextS.LR=-s.LR;
for(int i=0;i<9;i++){
nextS.x=s.x+dxs[i]*s.LR;
nextS.y=s.y+dys[i];
if(nextS.x<0 || w<=nextS.x || nextS.y<0 || h<=nextS.y || map[nextS.y][nextS.x]==-1)continue;
nextS.turn=s.turn+map[nextS.y][nextS.x];
if(memo.find(nextS)!=memo.end()&&memo[nextS]<=nextS.turn)continue;
memo[nextS]=nextS.turn;
pQ.push(nextS);
}
}
printf("%d\n",goalOK?s.turn:-1);
}
int main(){
int h,w;
while(1){
scanf("%d %d",&w,&h);
if(w==0&&h==0)break;
setData(w,h);
}
}
最終更新:2012年07月27日 18:25