「aoj2501～2510」の編集履歴（バックアップ）一覧に戻る
aoj2501～2510 - (2013/05/25 (土) 09:44:44) のソース
*2501 Grid Mori
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2501
土地購入を題材にした肩慣らし問題。
解法
競技プログラムのやり方に慣れるための導入問題なので特に考えることもなく解けます。
#include<stdio.h>
int abs(int x,int y){
return x-y>0?x-y:y-x;
}
int main(){
int n,a,b,c,d,ans=1000,t;
scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
a--,b--,c--,d--;
for(int i=1;i<=n;i++){
t=abs(a%i,b%i)+abs(a/i,b/i)+abs(c%i,d%i)+abs(c/i,d/i);
if(ans>t)ans=t;
}
printf("%d\n",ans);
}
*2502 VOCAL ANDROID
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2502
初音ミクを題材にしたプログラムの練習問題。
データが393(ミクさん)に統一されてるサービス問題。
解法
同じフレーズを何度も使用してよいという点に注意すれば、後は値の範囲が狭いだけのナップザック問題なので何も考えずあっという間に解けます。
#include<stdio.h>
#include<string.h>
int main(){
int n,m;
scanf("%d",&n);
int s,l,p;
int memo[394];
memset(memo,-1,sizeof(memo));
memo[0]=0;
for(int i=0;i<n;i++){
scanf("%d %d %d",&s,&l,&p);
for(int i=0;i<393;i++){
if(memo[i]==-1)continue;
for(int j=s;j<=l&&j+i<=393;j++){
if(memo[i+j]<memo[i]+p){
memo[i+j]=memo[i]+p;
}
}
}
}
scanf("%d",&m);
int ws[394];
bool ok=true;
for(int i=0;i<m;i++){
scanf("%d",&ws[i]);
if(memo[ws[i]]==-1){
ok=false;
}
}
if(ok==true){
for(int i=0;i<m;i++){
printf("%d\n",memo[ws[i]]);
}
}else{
printf("-1\n");
}
}
*2503 Project Management
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2503
作業手順のデータが与えられるのでクリティカルパスを計算する問題。
解法
今日びクリティカルパスなんて三流高校卒でも解けます。
#include<stdio.h>
#include<set>
#include<queue>
struct E{
int from,to,c;
bool operator<(const E& e)const{
return to<e.to;
}
};
int main(){
int n,m,a;
std::set<E> G[401];
std::set<E>::iterator it;
std::queue<E> qu;
E e1;
int time[401]={0},conCount[401]={0};
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d %d",&e1.from,&e1.to,&e1.c);
G[e1.from].insert(e1);
conCount[e1.to]++;
if(e1.from==0){
qu.push(e1);
}
}
conCount[0]=-1;//特に意味はないが念のためのおまじない
while(qu.empty()==false){
e1=qu.front();
qu.pop();
conCount[e1.to]--;
if(time[e1.to]<=time[e1.from]+e1.c){
time[e1.to]=time[e1.from]+e1.c;
}
if(conCount[e1.to]==0){
conCount[e1.to]=-1;
for(it=G[e1.to].begin();it!=G[e1.to].end();it++){
qu.push((*it));
}
}
}
printf("%d\n",time[n-1]);
}
*aoj2505 Twins Idol
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2505
二人遊びのボードゲームを題材に取った多分グラフ理論の問題。
普通最小値を求めるアルゴリズムは、グラフ理論の初歩で広く知られているが、この問題では最大値、もしくは無限になる場合を判定しなくてはいけない。
一見１００個と１００個しか点がないので簡単に思えるが中々の難問。
例えばワーシャルフロイド法を素朴に適用すると計算量が100＾6＝１億*100、メモリ使用量が100＾4バイトとなりこれは計算量の点で無理がある。
つまり何か余分な計算を行っているということである。
何か無駄な計算を減らせばよいのだと思うが今のところ解を思いつかない。
#include<stdio.h>
#include<string.h>
#include<vector>
struct edge{
int fromAki,fromMaki,toAki,toMaki,score;
};
int an,am,mn,mm;
char boardAki[101],boardMaki[101],c1;
std::vector<int> conAki[101],conMaki[101];
unsigned char score[100][100][100][100];
std::vector<edge> Es;
void scoreSearch(){
//アキのいる点とマキのいる点のセットで一つの点とし、この点の状態遷移がつながったグラフと見る
//どうしたら過去に通った点を記憶できるのだろうか？過去に通った点は最悪２＾10000通りの状態数が存在し得る
//つまり素朴な動的計画法は×。
//どの探索過程も一つのｄｐを更新すると考えれば？
//ワーシャルフロイド(ＷＦ)法的な何かが？
//WF法だと計算量は100＾6、メモリは100＾4バイト、話にならない。
memset(score,0,sizeof(score));
}
int reScore(edge& E){
return boardAki[E.toAki]==boardMaki[E.toMaki];
}
int main(){
int a,b;
//データの読み込み
scanf("%d %d",&an,&am);
for(int i=0;i<an;i++)scanf("%c%c",&boardAki[i],&c1);
for(int i=0;i<am;i++){
scanf("%d %d",&a,&b);
a--,b--;
conAki[a].push_back(b);
}
scanf("%d %d",mn,mm);
for(int i=0;i<mn;i++)scanf("%c%c",&boardMaki[i],&c1);
for(int i=0;i<mm;i++){
scanf("%d %d",&a,&b);
a--,b--;
conMaki[a].push_back(b);
}
//辺の登録
edge E,E2,E3;
for(int i=0;i<am;i++){
for(int j=0;j<conAki[i].size();j++){
for(int k=0;k<mm;k++){
for(int l=0;l<conMaki[k].size();l++){
E.fromAki=i;
E.toAki=conAki[i][j];
E.fromMaki=k;
E.toMaki=conMaki[k][l];
E.score=reScore(E);
Es.push_back(E);//辺の登録
if(boardAki[E.fromAki]!=boardMaki[E.fromMaki]){
//今いる地点で得点が得られない場合だけ使える辺
E2=E;//マキが動かない場合
E2.toMaki=k;
E2.score=reScore(E2);
E3=E;
E3.toAki=i;//アキが動かない場合
E3.score=reScore(E3);
Es.push_back(E2);
Es.push_back(E3);
}
}
}
}
}
}
