2281 Swap Cipher
解法
一番簡単な部類の問題なので何も考えずに実装します。
一度全部読んで逆操作で復元しましたが、手前からリニアに読みこんで処理する方法でコンパクトなアルゴリズムを考えつきませんでした。
#include<stdio.h>
#include<algorithm>
void calc(int n){
char text[110];
int as[101],bs[101];
scanf("%s",text);
for(int i=0;i<n;i++)scanf("%d %d",&as[i],&bs[i]);
for(int i=n-1;i>=0;i--){
char sa=(bs[i]-as[i])%26;
char c1=text[as[i]-1]-'a';
char c2=text[bs[i]-1]-'a';
c1=(c1+sa)%26+'a';
c2=(c2+sa)%26+'a';
text[as[i]-1]=c2;
text[bs[i]-1]=c1;
}
printf("%s\n",text);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
2283 Seishun 18 Kippu
解法
何も考えずダイクストラ法を二回適用するだけです。
#include<stdio.h>
#include<string>
#include<iostream>
#include<map>
#include<vector>
#include<queue>
struct Rosen{
std::string str;
int time;
bool operator<(const Rosen& r)const{
return time>r.time;
}
};
int D(std::string s,std::string g,std::map<std::string,std::vector<Rosen> >& G){
std::priority_queue<Rosen> qu;
Rosen r,nextR;
r.time=0;
r.str=s;
qu.push(r);
std::map<std::string,int> timeMemo;
while(qu.empty()==false){
r=qu.top();
qu.pop();
if(r.str==g)break;
if(timeMemo.find(r.str)!=timeMemo.end()&&timeMemo[r.str]<=r.time)continue;
timeMemo[r.str]=r.time;
for(std::vector<Rosen>::iterator it=G[r.str].begin();it!=G[r.str].end();it++){
nextR.str=(*it).str;
nextR.time=r.time+(*it).time;
if(timeMemo.find(nextR.str)!=timeMemo.end()&&timeMemo[nextR.str]<=nextR.time)continue;
qu.push(nextR);
}
}
return r.time;
}
void calc(int n,int m){
std::string s,p,g,a,b;
int d,t;
std::map<std::string,std::vector<Rosen> > G;
std::vector<Rosen> v;
std::cin>>s>>p>>g;
G[s]=v;
G[p]=v;
G[g]=v;
Rosen r;
for(int i=0;i<m;i++){
std::cin>>a>>b>>d>>t;
if(G.find(a)==G.end())G[a]=v;
if(G.find(b)==G.end())G[b]=v;
r.str=a;
r.time=d/40+t;
G[b].push_back(r);
r.str=b;
G[a].push_back(r);
}
printf("%d\n",D(s,p,G)+D(p,g,G));
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0&&m==0)break;
calc(n,m);
}
}
aoj2284 The Legendary Sword
解法
オーソドックスに動的計画法で解きました。
コードの書きやすさを優先した結果余り速度は出てません。
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<map>
#include<set>
struct P{
int x,y;
bool operator<(const P& p)const{
if(x!=p.x)return x<p.x;
return y<p.y;
}
};
int timeCalc(int x1,int y1,int x2,int y2){
return (x1>x2?x1-x2:x2-x1)+(y1>y2?y1-y2:y2-y1);
}
void calc(int w,int h){
int gx,gy;
char cell[10];
std::map<int,std::vector<P> > Os;
std::vector<P> v;
P p,oldP;
int last=1;
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
scanf("%s",cell);
char c=cell[0];
if(c=='S'){
p.y=y;
p.x=x;
Os[0]=v;
Os[0].push_back(p);
}else if(c=='G'){
gx=x;
gy=y;
}else if(c=='.'){
//何もしない
}else{
int no;
sscanf(cell,"%d",&no);
if(no>=last)last=no+1;
p.y=y;
p.x=x;
if(Os[no].empty()==true)Os[no]=v;
Os[no].push_back(p);
}
}
}
Os[last]=v;
p.x=gx;
p.y=gy;
Os[last].push_back(p);
std::map<P,int> memo,next;
memo[Os[0][0]]=0;
std::map<int,std::vector<P> >::iterator it;
for(unsigned int i=1;i<Os.size();i++){
for(unsigned int j=0;j<Os[i-1].size();j++){
oldP=Os[i-1][j];
int time=memo[oldP];
for(unsigned int k=0;k<Os[i].size();k++){
p=Os[i][k];
int nextTime=time+timeCalc(p.x,p.y,oldP.x,oldP.y);
if(next.find(p)==next.end()||next[p]>nextTime)next[p]=nextTime;
}
}
memo.clear();
memo.insert(next.begin(),next.end());
next.clear();
}
printf("%d\n",(*memo.begin()).second);
}
int main(){
int w,h;
while(1){
scanf("%d %d",&w,&h);
if(w==0&&h==0)break;
calc(w,h);
}
}
2285 Anipero
予算と各メンバの満足度と雇用費が与えられるので満足度を最大にできる呼ぶメンバを選ぶ問題。
解法
動的計画法で一発です。
二人だけ特別枠から選ぶという部分を上手くルール化できませんでした。
この問題拡張を考えｎグループからa1,a2,,,an人を指定して選ぶ場合、動的計画法の部分を関数化して分離する必要があります。
#include<stdio.h>
#include<vector>
#include<string.h>
int memo[102][1002];
struct A{
int e,s;
};
void calc(int limit,int n,int m,int x){
std::vector<A> SEC;
A a,a2;
int e,s;
char name[40];
memset(memo,-1,sizeof(memo));
memo[0][0]=0;
for(int i=0;i<n;i++){
scanf("%s %d %d",name,&a.e,&a.s);
SEC.push_back(a);
}
for(int i=1;i<=m;i++){
scanf("%s %d %d",name,&e,&s);
for(int j=i;j>0;j--){
for(int k=limit-e;k>=0;k--){
if(memo[j-1][k]==-1)continue;
int nextS=memo[j-1][k]+s;
if(memo[j][k+e]<=nextS)memo[j][k+e]=nextS;
}
}
}
for(int i=x;i<=m;i++){
int max=0;
int start=0;
for(int j=0;j<=limit;j++){
if(memo[i][j]!=-1)break;
start++;
}
for(int j=start;j<=limit;j++){
if(memo[i][j]>max)max=memo[i][j];
else memo[i][j]=max;
}
}
int ans=0;
for(int i=0;i<n;i++){
a=SEC[i];
for(int k=x;k<=m;k++){
if(a.e<=limit){
int sum=memo[k][limit-a.e];
if(sum!=-1){
sum+=a.s;
if(ans<sum)ans=sum;
}
}
}
for(int j=i+1;j<n;j++){
a2=SEC[j];
for(int k=x;k<=m;k++){
if(a.e+a2.e<=limit){
int sum=memo[k][limit-a.e-a2.e];
if(sum!=-1){
sum+=a.s+a2.s;
if(ans<sum)ans=sum;
}
}
}
}
}
printf("%d\n",ans);
}
int main(){
int limit,n,m,x;
while(1){
scanf("%d %d %d %d",&limit,&n,&m,&x);
if(limit==0&&n==0&&m==0&&x==0)break;
calc(limit,n,m,x);
}
}
2286 Farey Sequence
解法
オーソドックスにファイ関数を使って下から足し上げてみました。
数学の知識がないために速度出てません。
#include<stdio.h>
#include<iostream>
long long int phiTable[1000*1000+1];
int phi(int n){
double re=n;
for(int i=2;i*i<=n;i+=(i&1)+1){
int p=i;
int count=0;
while(n%p==0){
n/=p;
count++;
}
if(count>0)re*=(1-1.0/p);
}
if(n!=1)re*=(1-1.0/n);
return (int)re+0.5;
}
int main(){
phiTable[1]=2;
phiTable[2]=3;
phiTable[3]=5;
long long int sum=5;
for(int i=4;i<=1000000;i++){
sum+=phi(i);
phiTable[i]=sum;
}
int n,t;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&t);
std::cout<<phiTable[t]<<"\n";
}
}
最終更新：2013年02月08日 14:36
