「AOJ2021～2030」の編集履歴（バックアップ）一覧に戻る
AOJ2021～2030 - (2013/01/24 (木) 20:51:42) のソース
*2021 Princess in Danger
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2021
毒に倒れたお姫様を助けるために冷凍施設のある町で血液を冷凍しながらお姫様のいる街まで冷凍血液をとどけるグラフの問題。
この問題0分で冷凍施設のある町に到達した場合冷凍可能ということに注意しながら動的計画法で片が付きます。
動的計画法の取る状態は、memo[ある町に血液が到達して][残り冷凍時間]=この状態へ到達する最小タイムとして求めます。
動的計画法の中で注意するのは移動先を冷凍施設のある町(ゴールも含む)のみと制限するくらいです。
ちょっとしたテクとしては計算量を抑えるために全ての２つの街の間の最短移動距離をワーシャルフロイド法で求めておくことくらいです。
これくらいの工夫は自分がCPUになって自分の間抜けなコードを実行させられる立場になったらと想像したら要求して当然のデータです。
特に気にする部分のない基本的な問題で私のコードは実行速度で12/82位と平凡な順位となりました。
速度を求めればコードが分かりにくくなるような気がするのでこのへんが手の打ちどころでしょう。
動的計画法の内部ループを冷凍施設のある街だけループするよう縮めるくらいですかね。
#include<stdio.h>
#include<string.h>
#include<queue>
struct E{
int no,time,coldTime;
bool operator<(const E& e)const{
return time>e.time;
}
};
void wf(int con[101][101],int n){
//まずはワーシャルフロイド法で全街間の最小距離を求める
int t;
for(int y=0;y<n;y++){
for(int x=0;x<n;x++){
if(con[x][y]==-1)continue;
for(int i=0;i<n;i++){
if(con[y][i]==-1)continue;
t=con[x][y]+con[y][i];
if(con[x][i]==-1||con[x][i]>t){
con[x][i]=t;
}
}
}
}
}
bool setData(){
int n;//街の数
int m;//スタート時の冷凍時間
int l;//再冷凍可能な街の数
int k;//道路の数
int a;//スタート
int h;//ゴール
int x,y,t;
scanf("%d %d %d %d %d %d",&n,&m,&l,&k,&a,&h);
if(n+m+l+k+a+h==0)return false;
bool isColdCity[101];//冷凍施設のある街の一覧
memset(isColdCity,false,sizeof(isColdCity));
for(int i=0;i<l;i++){
scanf("%d",&x);
isColdCity[x]=true;
}
isColdCity[a]=isColdCity[h]=true;
int con[101][101];
memset(con,-1,sizeof(con));
for(int i=0;i<k;i++){
scanf("%d %d %d",&x,&y,&t);
con[x][y]=con[y][x]=t;
}
wf(con,n);//全ての街の間の最短距離を求める
//動的計画法で解く
int memo[101][101];//memo[街の番号][血液の冷凍時間]=ここまでの最短タイム
memset(memo,-1,sizeof(memo));//
//printf("scanOK");//適切に読み込み完了
E e,nextE;
e.no=a;
e.coldTime=m;
e.time=0;
std::priority_queue<E> pq;
pq.push(e);
int nextTime;
while(!pq.empty()){
e=pq.top();
pq.pop();
if(e.no==h){
memo[h][0]=e.time;//仮の答えを入れていく
break;
}
t=memo[e.no][e.coldTime];
if(t!=-1&&t<=e.time)continue;
memo[e.no][e.coldTime]=e.time;
for(int i=0;i<n;i++){
t=con[e.no][i];
if(t==-1||t>m||isColdCity[e.no]==false)continue;//同じ街に移動しようとしたか、ｔがｍを超えた
nextE.no=i;
if(t<=e.coldTime){
//冷凍しなくても到達できる
nextE.time=e.time+t;
nextE.coldTime=e.coldTime-t;
}else{
nextE.time=e.time+t+(t-e.coldTime);//移動時間
nextE.coldTime=0;
}
t=memo[nextE.no][nextE.coldTime];
if(t!=-1&&t<=nextE.time)continue;
pq.push(nextE);
}
}
if(memo[h][0]==-1)printf("Help!\n");
else printf("%d\n",memo[h][0]);
return true;
}
int main(){
while(setData());
}
*2022 Princess, a Cryptanalyst
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2022
与えられた１０単語の重複部分を重ねて繋げた時最も短い文字列を作るという問題。
解法
より左にある単語の順番を決めて単語を繋げた場合、繋げ方は貪欲法に帰属します。
後は単語は１０単語までしかないので全ての並び順10！を試すだけです。
この問題は１年前に一度挑戦してその時は手も足も出ない問題でした。
今年再挑戦してみたら３時間ほどで解法を思いつきました。
最初string型を使った方法で速度が出なかったのでchar型になおして解きましたこれの修正に手間取りました。
他の人のコードを見るともっと高速に解けてるようなのでもっと賢い方法があるようです。
#include<stdio.h>
#include<string.h>
#include<iostream>
int spents[10];
char words[10][12],ans[110];
int n;
void strCon(char *str1,char *str2,int len){
int len2=strlen(str2);
int p=len-11;
if(p<0)p=0;
for(int i=p;i<len;i++){
bool ok=true;
for(int j=0;j+i<len&&j<len2;j++){
if(str1[j+i]!=str2[j]){
ok=false;
break;
}
}
if(ok==true){
if(len-i>=len2){
return ;
}else{
memcpy(str1+i,str2,len2+1);
return ;
}
}
}
memcpy(str1+len,str2,len2+1);
}
void saiki(char *text,int deep,int size){
if(deep==0){
for(int i=0;i<n;i++)spents[i]=false;
text[0]='\0';
ans[0]='\0';
}
if(deep==n){
if(ans[0]=='\0'){
memcpy(ans,text,size+1);
}else if(strlen(ans)>size){
memcpy(ans,text,size+1);
}else if(strlen(ans)==size&&strcmp(ans,text)>0){
memcpy(ans,text,size+1);
}
}else{
for(int i=0;i<n;i++){
if(spents[i]==false){
spents[i]=true;
strCon(text,words[i],size);
saiki(text,deep+1,strlen(text));
text[size]='\0';
spents[i]=false;
}
}
}
}
int main(){
char text[110];
while(1){
scanf("%d",&n);
if(n==0)break;
for(int i=0;i<n;i++)std::cin>>words[i];
saiki(text,0,0);
std::cout<<ans<<"\n";
}
}
*2025 Eight Princes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2025
8人の王子が丸いテーブルに均等に並んだ席に座る。
王子たちは互いに仲が悪く隣り合う席も互いに対面する席も拒否する。
座らせ方は何通りあるか？
解法
奇数席の時は簡単な動的計画法で済みます。
偶数席の場合反対の席が使えなくなるのでひと工夫必要です。
全員をきちんと座らせた時、テーブルを真中で割ります。
テーブルの片方にいる王子をＬ、片方にいる王子をＲ、空席をＢ(blank)として片方の王子全員に反対の席に移動してもらうと、n/2の長さのＬＲＢの文字列の組み合わせを計算する問題に問題が縮約します。
後は時計回りに席を埋めていって最初の席がＬかＲかブランクであることに注意しながらメモ化計算していくだけです。
#include<stdio.h>
#include<vector>
#include<iostream>
#include<string.h>
long long int lastMult=8*7*6*5*4*3*2*1;
void calcMod0(int n){
//偶数席の場合の計算
long long int memo[9][3][3][100];//memo[座った王子の人数][0番席のＲＬ空席][今のＲＬ空席][i席目]1100も確保すれば十分だろう多分
int R=0,L=1,blank=2;
memset(memo,0,sizeof(memo));
memo[0][blank][blank][0]=1;
memo[1][L][L][0]=1;
memo[1][R][R][0]=1;
int herf=n/2-1;
for(int i=0;i<herf;i++){
for(int j=0;j<=8;j++){
for(int k=0;k<3;k++){
if(j<8) memo[j+1][k][R][i+1]+=memo[j][k][L][i]+memo[j][k][blank][i];
if(j<8) memo[j+1][k][L][i+1]+=memo[j][k][R][i]+memo[j][k][blank][i];;
memo[j][k][blank][i+1]+=memo[j][k][L][i]+memo[j][k][R][i]+memo[j][k][blank][i];
}
}
}
long long int ans=memo[8][L][L][herf]+memo[8][L][blank][herf];
ans+=memo[8][R][R][herf]+memo[8][R][blank][herf];
ans+=memo[8][blank][R][herf]+memo[8][blank][L][herf]+memo[8][blank][blank][herf];
std::cout<<ans*lastMult<<"\n";
}
void calcMod1(int n){
std::vector<long long int> memo[9];
for(int i=1;i<=8;i++){
for(int j=0;j<=n;j++)memo[i].push_back(0);
}
//まず0番席以外の計算を行う時計回りにみた時
//1番席に最初の王子が座る場合、、2番席に最初の王子が座る場合、、、とする
//0番席はｎ-1番席に最後の王子が座れない場合がでるので特別に後で計算する
for(int i=1;i<n;i++)memo[1][i]=1;
for(int i=0;i<n;i++){
for(int j=2;j+i<n;j++){
for(int k=1;k<8;k++){
memo[k+1][i+j]+=memo[k][i];
}
}
}
long long int ans=0;
for(int i=0;i<n;i++)ans+=memo[8][i];
//0番席に王子が座った場合の組み合わせ
for(int i=1;i<=8;i++){
for(int j=0;j<=n;j++)memo[i][j]=0;//リセット
}
memo[1][0]=1;
for(int i=0;i<n;i++){
for(int j=2;j+i<n;j++){
for(int k=1;k<8;k++){
memo[k+1][i+j]+=memo[k][i];
}
}
}
for(int i=0;i<n-1;i++)ans+=memo[8][i];//0番席の左隣を足さないようにする
std::cout<<ans*lastMult<<"\n";
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
if(n<17)printf("0\n");
else if(n%2==0) calcMod0(n);//偶数席
else calcMod1(n);//奇数席
}
}
