「AOJ541～550」の編集履歴（バックアップ）一覧に戻る
AOJ541～550 - (2011/11/10 (木) 17:54:36) のソース
----
*0541 Walk
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0541
格子の街並みを東か南に移動しながらマップの外まで散歩し次回の散歩では一度通った交差点を次に通る時は前回東なら次は南、前回南なら次は東とするとき、ｎ回目の散歩がどの地点に到達するかを答える問題。
解法
この問題はある地点を何回通るかということが重要となります。
スタート地点で考えてみましょう。
スタートが東で通る回数が1回のとき、2回のとき、、、ｎ回のときと考えると。
ｎが奇数回目のときは必ず東に向かい、ｎが偶数回目のときは必ず南に向かいます。
この条件が全ての交差点で成り立ちます。
つまり、どの交差点も何回訪れたかで南か東かが決まります。
これを利用してｎ-1回目までの散歩を道路にまとめて流すと下記のようなコードとなります。
ｎ-1回目までの結果、東南がどう変わったかを利用して最後のwhileが実行されます。
#include<stdio.h>
#include<string.h>
int map[1002][1002];
int memo[1002][1002];
int h,w,n;
void setData(){
int x,y,t;
for(y=0;y<h;y++){
for(x=0;x<w;x++){
scanf("%d",&map[y][x]);
}
}
memset(memo,0,sizeof(memo));
memo[0][0]=n-1;
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
t=memo[y][x];
if(map[y][x]==0){
if(t%2==0){
memo[y+1][x]+=t/2;
memo[y][x+1]+=t/2;
}else{
map[y][x]=1;
memo[y+1][x]+=t/2+1;
memo[y][x+1]+=t/2;
}
}else{
if(t%2==0){
memo[y+1][x]+=t/2;
memo[y][x+1]+=t/2;
}else{
map[y][x]=0;
memo[y+1][x]+=t/2;
memo[y][x+1]+=t/2+1;
}
}
}
}
y=x=0;
while(y<h && x<w){
if(map[y][x]==0)y++;
else x++;
}
printf("%d %d\n",y+1,x+1);
}
int main(){
while(1){
scanf("%d %d %d",&h,&w,&n);
if(h==0 && w==0 && n==0) break;
setData();
}
}
----
*0542 Authentication Level
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542
格子状に連なった部屋をつなぐドアに保安レベルが設定されておりレベル以上の認証レベルを持ってないとその部屋を訪れることが出来ない。
ある一定数以上の部屋を訪れることのできる認証レベルを求める問題。
解法
優先順位付きキューでレベルの低い部屋から優先して訪れある部屋に一番低いレベルで訪れたらその部屋はそのレベルでないと入れない部屋としてレベルを更新します。
Lv３の部屋に行く途中でどのような経路を通っても途中にLv10の部屋を挟まないといけないなら、Lv３の部屋はLv10でないと入れない部屋に更新するわけです。
そして全ての部屋を訪れた後更新されたレベルでそのレベルで訪れれる部屋数をカウントします。
最後に必要なレベルを算出するために訪れれる部屋数をキーにレベルを値にしてMapに入れなおして最後のループで答えを求めます。
素直な実装をしてみたところランキングではメモリ多消費の割には平凡なコード実行速度になりました。
もう少し良いコードがあるようです。
#include<stdio.h>
#include<queue>
#include<map>
#include<string.h>
struct room{
int x,y,level;
bool operator<(const room r)const{
return level>r.level;
}
void set(int ix,int iy,int ilevel){
x= ix;
y= iy;
level= ilevel;
}
};
const int roomSize=501;
int dxs[4]={0,1,0,-1};
int dys[4]={1,0,-1,0};
void search(int sx,int sy,int w,int h,int level[roomSize][roomSize],std::map<int,int>& ans){
std::priority_queue<room> qu;
room r,nextR;
int nx,ny,nLevel;
r.set(sx,sy,level[sy][sx]);
qu.push(r);
ans.clear();
ans[0]=0;
ans[1]=1;
bool moveOKs[roomSize][roomSize];
memset(moveOKs,true,sizeof(moveOKs));
moveOKs[sy][sx]=false;
while(!qu.empty()){
r=qu.top();
qu.pop();
for(int i=0;i<4;i++){
nx=r.x+dxs[i];
ny=r.y+dys[i];
nLevel=r.level;
if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
if(moveOKs[ny][nx]==false) continue;
moveOKs[ny][nx]=false;
if(level[ny][nx]>nLevel)nLevel=level[ny][nx];
level[ny][nx]=nLevel;
nextR.set(nx,ny,nLevel);
if(ans.find(nLevel)==ans.end()){
ans[nLevel]=1;
}else{
ans[nLevel]++;
}
qu.push(nextR);
}
}
}
void print(int level[roomSize][roomSize],int h,int w){
printf("\n\n");
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
printf("%d ",level[y][x]);
}
printf("\n");
}
printf("\n\n");
}
int level[2][roomSize][roomSize];
void setData(int r){
int w,h,sx,sy;
std::map<int,int> levelCounts[2];
for(int i=0;i<2;i++){
scanf("%d %d %d %d",&w,&h,&sx,&sy);
sx--;
sy--;
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
scanf("%d",&level[i][y][x]);
}
}
//print(level[i],h,w);
search(sx,sy,w,h,level[i],levelCounts[i]);
//print(level[i],h,w);
}
std::map<int,int> roomCounts[2];
std::map<int,int>::iterator it,it2;
int back;
for(int i=0;i<2;i++){
it=levelCounts[i].begin();
back=0;
while(it!=levelCounts[i].end()){
back+=(*it).second;
roomCounts[i][back]=(*it).first;
it++;
}
}
it=roomCounts[0].begin();
int temp,sumLevel,sumRoom,ans=1000000000;
while(it!=roomCounts[0].end()){
temp=r-(*it).first;
it2=roomCounts[1].lower_bound(temp);
sumRoom=(*it).first+(*it2).first;
if(sumRoom<r){
it++;
continue;
}
sumLevel=(*it).second+(*it2).second;
ans=ans>sumLevel?sumLevel:ans;
it++;
}
printf("%d\n",ans);
}
int main(){
int r;
while(1){
scanf("%d",&r);
if(r==0) break;
setData(r);
}
}
----
*0543 Receipt
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0543
レシートのデータで一つだけ金額がかすれているので残りの金額からかすれた部分の値段を求める問題。
解法
中学生にでも出題しそうな簡単な問題なので計算するだけです。
#include<stdio.h>
int main(){
int sum,all,i,t;
while(1){
scanf("%d",&all);
if(all==0) break;
i=9,sum=0;
while(i--){
scanf("%d",&t);
sum+=t;
}
printf("%d\n",all-sum);
}
}
----
*0544 Sugoroku
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0544
すごろくの升目データとさいころの情報が与えられるので何手目でゴールできるかを答える問題。
解法
サイを振った後、升目の進む戻るで
ゴールを超えた升目を参照しないように注意さえすれば簡単な問題です。
コードをきれいにまとめられませんでした。
#include<stdio.h>
void setData(int n,int m){
int map[1002];
for(int i=1;i<=n;i++){
scanf("%d",&map[i]);
}
int xai,nowP=1,ans;
bool goal=false;
for(int i=1;i<=m;i++){
scanf("%d",&xai);
if(goal==true) continue;
nowP+=xai;
if(n<=nowP){
ans=i;
goal=true;
continue;
}
nowP+=map[nowP];
if(n<=nowP){
ans=i;
goal=true;
}
}
printf("%d\n",ans);
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0 && m==0) break;
setData(n,m);
}
}
----
*0545 Party
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0545
誰と誰が友達かの情報から、友達の友達が何人いるか答える問題です。
解法
友達の友達が実は単なる友達で探索が続く場合にさえ注意すれば再起探索で間に合う問題です。
素直に再起で実装しました。
#include<stdio.h>
#include<string.h>
//簡単な問題なのでグローバル変数で手抜き
const int max=502;
bool con[max][max],moveOKs[max];
int ans,n,m;
void search(int deep,int no){
//友達の友達が実は友達だった場合探索が続くので注意
for(int i=2;i<=n;i++){
if(con[no][i]){
if(moveOKs[i]==true)ans++;
moveOKs[i]=false;
if(deep==0)search(deep+1,i);
}
}
}
void setData(){
memset(con, false, sizeof(con));
memset(moveOKs,true , sizeof(moveOKs));
moveOKs[1]=false;
ans=0;
int a,b;
for(int i=0;i<m;i++){
scanf("%d %d",&a,&b);
con[a][b]=con[b][a]=true;
}
search(0,1);
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d %d",&n,&m);
if(n==0 && m==0) break;
setData();
}
}
----
*0546 Lining up the cards
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0546
数字の書かれたカードの中から数枚選んでカードを並べるとき何通りの数が出来上がるか答えよという問題です。
解法
再起探索で全ての組み合わせを全生成し出来た数字を文字列としてstd::set<std::string> allに入れて重複を削除します。
後はall.sizeで答えが出ます。
グローバル変数を使わずに解いてみました。
実務ならグローバル変数はクラス内に隠されますし変数の受け渡し部分が煩わしくなるのであまり意味のないコードになりました。
素直にグローバル変数を使ったほうがよいという例です。
#include <iostream>
#include<string>
#include<set>
#include<vector>
#include<string.h>
void saiki( int deep, std::string s,std::vector<std::string>& nums,
bool moveOKs[11], std::set<std::string>& all, int k, int n){
if(k<=deep){
//std::cout<<s<<"\n";
all.insert(s);
}else{
for(int i=0;i<n;i++){
if(moveOKs[i]==true){
moveOKs[i]=false;
saiki(deep+1,s+nums[i],nums,moveOKs,all,k,n);
moveOKs[i]=true;
}
}
}
}
void setData(int n,int k){
std::set<std::string> all;
std::vector<std::string> nums;
std::string num;
bool moveOKs[11];
memset(moveOKs,true,11);
for(int i=0;i<n;i++){
std::cin>>num;
nums.push_back(num);
}
saiki(0,"",nums,moveOKs,all,k,n);
std::cout<<all.size()<<"\n";
}
int main(){
int n,k;
while(1){
std::cin>>n>>k;
if(n==0 && k==0) break;
setData(n,k);
}
}
----
*0547 Commute routes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547
升目状の道路で目的地までの通り方が何通りあるか答える問題。
解法
升目が最大10000マスと小さいので気楽に実装します。
縦移動の後は横移動、横移動の後は縦移動という性質を使って縦横に分解してメモ化で計算します。
最後に縦と横の計を集計して終わりです。
#include<stdio.h>
#include <algorithm>
#include<string.h>
void setData(int w,int h){
int moveTate[102][102];//縦移動後
int moveYoko[102][102];//横移動後
memset(moveTate,0,sizeof(moveTate));
memset(moveYoko,0,sizeof(moveYoko));
if(w<h)std::swap(w,h);//コードを短くするため横方向を長くする
moveYoko[0][0]=moveTate[0][0]=moveYoko[0][1]=moveTate[1][0]=1;
const int mod=100000;
for(int i=0;i<h;i++){
for(int x=i;x<w;x++){
for(int x2=x+2;x2<w;x2++){
moveYoko[i][x2]+=moveTate[i][x];
}
}
for(int y=i;y<h;y++){
for(int y2=y+2;y2<h;y2++){
moveTate[y2][i]+=moveYoko[y][i];
}
}
for(int x=i+1;x<w;x++){
//縦移動
for(int y=i+2;y<h;y++){
moveTate[y][x]+=moveYoko[i][x];
moveTate[y][x]%=mod;
}
}
for(int y=i+1;y<h;y++){
//横移動
for(int x=i+2;x<w;x++){
moveYoko[y][x]+=moveTate[y][i];
moveYoko[y][x]%=mod;
}
}
}
int ans=0;
ans+=moveYoko[h-1][w-1]+moveYoko[h-2][w-1]+moveTate[h-1][w-1]+moveTate[h-1][w-2];
printf("%d\n",ans%mod);
}
int main(){
int w,h;
while(1){
scanf("%d %d",&w,&h);
if(w==0&& h==0) break;
setData(w,h);
}
}
----
*0548 Reindeer with no sense of direction
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0548
サンタクロースがプレゼントを配っていくルートがいくつあるか答える問題。
解法
逆戻りでプレゼントを配り終わった状態からスタートへ戻ることを考えます。
最初の一手目教会から東西南北一番近い家にプレゼントを回収しなければなりません。
そうしないとその近い家の煙に阻まれて教会にたどり着くことが出来ないからです。
その次の家でも同じ条件となります。
これで計算量は上下左右の家4方向しかないので最悪4＾23通り、実際の組み合わせ数はもっと減ります。
しかしこれだけではまだ計算量が少し大きいのでメモ化で計算をまとめます。
過去にプレゼントを回収した家が同じで今いる家が同じになる経路をroots変数で一つにまとめてメモ化して計算します。
これによって計算量を抑えます。
またｎ件目までまわった場合とその次だけをrootsにメモすることでメモリ消費量を大幅に抑えます。
#include<stdio.h>
#include<string.h>
#include<map>
struct Move{
int x,y,houses;
bool operator<(const Move m)const{
if(houses!=m.houses) return houses<m.houses;
if(y!=m.y) return y<m.y;
return x<m.x;
}
};
//グローバル変数一覧
int map[11][11];//マップ
int m,n;
int houseCount;
const int dxs[4]={1,0,-1,0};
const int dys[4]={0,1,0,-1};
int houseBits[11][11];
std::map<Move,int> memo;
int ans;
//グローバル変数終わり
int search(Move move,int h,int w){
std::map<Move,int> roots[2];
std::map<Move,int>::iterator it;
int type,now,next,nx,ny,perm;
Move nextMove;
roots[0][move]=1;
for(int i=0;i<=houseCount;i++){
type=i==houseCount?2:1;
now =i%2;//メモ化探索
next=(i+1)%2;
roots[next].clear();
it=roots[now].begin();
while(it!=roots[now].end()){
move=(*it).first;
perm=(*it).second;
for(int i=0;i<4;i++){
for(int j=1;j<11;j++){
nx=move.x+dxs[i]*j;//上下左右の探索
ny=move.y+dys[i]*j;
if(nx<0 || w<=nx || ny<0 || h<=ny) break;
if(type==map[ny][nx] && (move.houses&houseBits[ny][nx])==0){
nextMove.x=nx;//上下左右がプレゼント未回収の家か教会だったので経路を加算
nextMove.y=ny;
nextMove.houses=move.houses|houseBits[ny][nx];
if(roots[next].find(nextMove)==roots[next].end()){
roots[next][nextMove]=perm;
}else{
roots[next][nextMove]+=perm;//同じルートをまとめる
}
break;
}
}
}
it++;
}
}
return roots[next][nextMove];
}
void setData(){
houseCount=0;
int sx,sy;
memset(houseBits,0,sizeof(houseBits));
memo.clear();
for(int y=0;y<n;y++){
for(int x=0;x<m;x++){
scanf("%d",&map[y][x]);
if(map[y][x]==1){
houseBits[y][x]=1<<houseCount;//intの中で1bitだけで家を表現
houseCount++;
}else if(map[y][x]==2){
sx=x;//教会をスタート位置に
sy=y;
}
}
}
Move move;
move.houses=0;//訪れた家を1bit単位で管理
move.x=sx;
move.y=sy;
ans=0;
printf("%d\n",search(move,n,m));
}
int main(){
while(1){
scanf("%d %d",&m,&n);
if(m==0 && n==0) break;
setData();
}
}
----
*0549 A Traveler
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549
一本道の街道にある宿場町とその間の距離が与えられる。
宿場から宿場への移動ルートの情報が与えられるので総移動距離を求めよという問題。
解法
宿場Aと宿場Bの距離は宿場1からAまでの距離をA1、宿場１から宿場Bまでの距離をB1とすると
abs(A1B1)となります。
後はこれを順次足すだけです。
#include<stdio.h>
#include<stdlib.h>
#include<vector>
void setData(int n,int m){
std::vector<int> points;
points.push_back(0);
int len,move,sum=0,now=0;
for(int i=1;i<n;i++){
scanf("%d",&len);
points.push_back(points.back()+len);
}
for(int i=0;i<m;i++){
scanf("%d",&move);
sum+=abs(points[now]-points[now+move]);
sum%=100000;
now+=move;
}
printf("%d\n",sum);
}
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
setData(n,m);
}
}
----
*0550 Dividing Snacks
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0550
お菓子の棒を二人で分ける問題。
分割する場所によって分割時間が異なり最小時間で二人で分けないといけない。
分割場所が最大9999個あるので何も考えないと2＾9999個の分割組み合わせを考えないといけない問題です。
解法
この問題は問題の性質から見て動的計画法もしくは特定のデータを優先して処理することで解決できる問題のようです。
正答者データにあるコード実行時間を考慮すると線形的な解はなさそうなことがわかります。
そこで計算量の安定する動的計画法を採用します。
まず、組み合わせ数を減らします。
ある切断方法がある場合切断位置をA1,A5,A4と切断するのも
A1 A4 A5と切断するのもタイムに変わりはありません。
よって左端から切断していくこととして組み合わせ数を減らします。
次に、左端から切断していった場合二人をAさんBさんとします。
切断したものを左から見てAさんBさんの分配を見ていくと
ABABA,,,という順番でしか分けられないことが判明します。
もし
ABBAのような分配があればBBは切断する必要がありません。
よってABAB、、、のような配置となります。
左から切断していってAさんBさんと切断した端から二人に分けていった場合ｒ個目の切断位置がAiだったとします。
するとAiまでで何か所どこを切断したかという情報は必要なくなります。
必要な情報はAさんが何個でBさんが何個で今どの部分の切断箇所を分離したかという情報とここまでの切断タイムと次の切断をもらうのがAさんかBさんかだけが重要となります。
①Ai個目を切断したときAさんがK個でBさんがi-k個でタイムはtで次の切断をもらうのがAさんかBさんか。
後は①が同じ条件になる別の切り方の中で一番タイムの短い切り方以外残す必要がありません。
こうなると動的計画法で片が付き計算量は大雑把に見積もって5000*10000*2の1億回、実際はもう少し減らせるまで圧縮できます。
計算回数は最悪の場合でも現実的なタイムで合格できそうです。
この発想の場合思考力と分析力さえあれば高校生でも解ける問題であることが判明しました。
後はこの発想を丁寧に実装するだけです。
#include<stdio.h>
#include<string.h>
const int A=0;//二人をAさんBさんとする
const int B=1;
void setData(int n){
int memo[2][5002];//[次にもらうのがAさん＝0 Bさん＝1][Aさんがここまででもらった個数]=最小切断時間
int next[2][5002];//次の切断箇所の検討
int cutTimes[10001];//切断時間
int cutTime,herf=n/2,nowTime;
int up;
for(int i=0;i<n-1;i++)scanf("%d",&cutTimes[i]);
memset(memo,127,sizeof(memo));//足される切断秒数は10000なのでオーバーフローしない
memo[A][1]=0;//計算しやすいようAさんが1個目を取得した状態から始める
for(int turn=0;turn<n-1;turn++){
memset(next,127,sizeof(next));//ダミーデータ
cutTime=cutTimes[turn];//切断箇所を左から一つずつ検証していく
up=turn+1>herf?herf:turn+1;//上限
for(int k=1;k<=up;k++){
nowTime=memo[A][k];//Aさん
//切断せずAさんが続けてもらう
next[A][k+1]=nowTime;
//切断して次はBさんがもらう
next[B][k]=nowTime+cutTime;
}
for(int k=1;k<=up;k++){
//Bさんの番
nowTime=memo[B][k];
//Bさんが続けてもらう
next[B][k]=next[B][k]>nowTime?nowTime:next[B][k];
//Aさんがもらう
nowTime+=cutTime;
next[A][k+1]=next[A][k+1]>nowTime?nowTime:next[A][k+1];
}
memcpy(memo,next,sizeof(next));
}
nowTime=memo[A][herf]>memo[B][herf]?memo[B][herf]:memo[A][herf];
printf("%d\n",nowTime);
}
int main(){
int n;
scanf("%d",&n);
setData(n);
while(scanf("%d",&n)!=EOF){
}
}
