「1002 : Extraordinary Grid I」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
1002 : Extraordinary Grid I
普段はもっとスマートなコードを書くのですが、今回は良い方法を思いつかなかったので力ずくでメモ化探索するコードを書きました。
これが試験なら最低点、ぎりぎり○といったところです。
1 最小移動距離を求める問題ですが、この時司書は進む時、左から右へか上下へ移動するのはあっても右から左へ戻ることはありません。
2 ある交差点にいる時、今までたどってきた経路のうち最短距離以外の経路は無視してもよい。
この性質を利用しメモ化します。
1列ずつ処理します。
ある列にいる時、横道3行全てから上下移動して本を返し次の列のn(1~3)行目に移動します。n行目同士で最短距離を比較し一番短いものを残す。
この時今いる行*次の行での位置という3行*3行の9通りの移動が考えられます。
状況としては返す本がある無しの4通り、36通りの状況が考えられます。
この縦一列の本を処理する時の36通り全ての最短移動距離を手作業で求めてコード化しました。
4行やn行と一般になった時でも解ける手法で解くのが100点とするならこのコードは20点程度でしょうか。
#include <stdio.h>
#include <algorithm>
void setMap(int);
int memo[3][20004];/*司書が一列ずつ棚を処理した時、3行n列目までの最短距離のメモカ*/
int map[2][20004];/*通路一列ずつ本を返す返さないの処理*/
int main()
{
int m,n;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d",&n);
setMap(n);
}
}
void setMap(int n){
char t;
int x,y;
for(int i=0;i<n*4;i++){
y=i/(2*n);
x=i%(2*n);
map[y][x]=0;/*棚の初期化*/
}
for(int i=0;i<n*4;i++){
y=i/(2*n);
x=i%(2*n);/*ある列に返す本があるかどうかあるなら1を設定する*/
scanf(" %c",&t);
map[y][(x+1)/2]+=((t=='Y') ? 1:0);
}
memo[0][0]=0;
memo[1][0]=1;
memo[2][0]=2;
/*棚を左から右へ一列ずつ処理し、次の列へ行った時最短距離だけを残していく*/
for(int i=0;i<n;i++){
memo[0][i+1]=memo[1][i+1]=memo[2][i+1]=100000000;
if(map[0][i]>0 && map[1][i]>0){
memo[0][i+1]=std::min(memo[0][i]+4,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+4,memo[2][i+1]);
}else if(map[0][i]>0 && map[1][i]==0){
memo[0][i+1]=std::min(memo[0][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+4,memo[2][i+1]);
}else if(map[0][i]==0 && map[1][i]>0){
memo[0][i+1]=std::min(memo[0][i]+4,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+2,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+2,memo[2][i+1]);
}else{
memo[0][i+1]=std::min(memo[0][i]+1,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+1,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+2,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+1,memo[2][i+1]);
}
}
/*最終列だけ特別な処理が必要*/
if(map[0][n]>0 && map[1][n]>0){
memo[0][n]+=3;
memo[1][n]+=2;
}else if(map[0][n]>0 && map[1][n]==0){
memo[0][n]+=1;
memo[1][n]+=1;
}else if(map[0][n]==0 && map[1][n]>0){
memo[0][n]+=3;
memo[1][n]+=2;
}else{
memo[1][n]+=1;
}
memo[2][n]+=2;
int ans;
ans=std::min(memo[0][n],memo[1][n]);
ans=std::min(ans,memo[2][n]);
printf("%d\n",ans);
}
1002 : Extraordinary Grid I
普段はもっとスマートなコードを書くのですが、今回は良い方法を思いつかなかったので力ずくでメモ化探索するコードを書きました。
これが試験なら最低点、ぎりぎり○といったところです。
1 最小移動距離を求める問題ですが、この時司書は進む時、左から右へか上下へ移動するのはあっても右から左へ戻ることはありません。
2 ある交差点にいる時、今までたどってきた経路のうち最短距離以外の経路は無視してもよい。
この性質を利用しメモ化します。
1列ずつ処理します。
ある列にいる時、横道3行全てから上下移動して本を返し次の列のn(1~3)行目に移動します。n行目同士で最短距離を比較し一番短いものを残す。
この時今いる行*次の行での位置という3行*3行の9通りの移動が考えられます。
状況としては返す本がある無しの4通り、36通りの状況が考えられます。
この縦一列の本を処理する時の36通り全ての最短移動距離を手作業で求めてコード化しました。
4行やn行と一般になった時でも解ける手法で解くのが100点とするならこのコードは20点程度でしょうか。
#include <stdio.h>
#include <algorithm>
void setMap(int);
int memo[3][20004];/*司書が一列ずつ棚を処理した時、3行n列目までの最短距離のメモカ*/
int map[2][20004];/*通路一列ずつ返す本があるかないかに関する記述、図でいえば上下2列に分かれている*/
int main()
{
int m,n;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d",&n);
setMap(n);
}
}
void setMap(int n){
char t;
int x,y;
for(int i=0;i<n*4;i++){
y=i/(2*n);
x=i%(2*n);
map[y][x]=0;/*棚の初期化*/
}
for(int i=0;i<n*4;i++){
y=i/(2*n);
x=i%(2*n);/*ある列に返す本があるかどうかあるなら1を設定する*/
scanf(" %c",&t);
map[y][(x+1)/2]+=((t=='Y') ? 1:0);
}
memo[0][0]=0;
memo[1][0]=1;
memo[2][0]=2;
/*棚を左から右へ一列ずつ処理し、次の列へ行った時最短距離だけを残していく*/
for(int i=0;i<n;i++){
memo[0][i+1]=memo[1][i+1]=memo[2][i+1]=100000000;
if(map[0][i]>0 && map[1][i]>0){
memo[0][i+1]=std::min(memo[0][i]+4,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+4,memo[2][i+1]);
}else if(map[0][i]>0 && map[1][i]==0){
memo[0][i+1]=std::min(memo[0][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+4,memo[2][i+1]);
}else if(map[0][i]==0 && map[1][i]>0){
memo[0][i+1]=std::min(memo[0][i]+4,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+3,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+2,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+2,memo[2][i+1]);
}else{
memo[0][i+1]=std::min(memo[0][i]+1,memo[0][i+1]);
memo[1][i+1]=std::min(memo[0][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[0][i]+3,memo[2][i+1]);
memo[0][i+1]=std::min(memo[1][i]+2,memo[0][i+1]);
memo[1][i+1]=std::min(memo[1][i]+1,memo[1][i+1]);
memo[2][i+1]=std::min(memo[1][i]+2,memo[2][i+1]);
memo[0][i+1]=std::min(memo[2][i]+3,memo[0][i+1]);
memo[1][i+1]=std::min(memo[2][i]+2,memo[1][i+1]);
memo[2][i+1]=std::min(memo[2][i]+1,memo[2][i+1]);
}
}
/*最終列だけ特別な処理が必要*/
if(map[0][n]>0 && map[1][n]>0){
memo[0][n]+=3;
memo[1][n]+=2;
}else if(map[0][n]>0 && map[1][n]==0){
memo[0][n]+=1;
memo[1][n]+=1;
}else if(map[0][n]==0 && map[1][n]>0){
memo[0][n]+=3;
memo[1][n]+=2;
}else{
memo[1][n]+=1;
}
memo[2][n]+=2;
int ans;
ans=std::min(memo[0][n],memo[1][n]);
ans=std::min(ans,memo[2][n]);
printf("%d\n",ans);
}