「2361～2370」の編集履歴（バックアップ）一覧に戻る
2361～2370 - (2013/01/28 (月) 11:05:54) のソース
*2361 Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361
ソートコストを題材にした問題。
解法
とりあえずグラフの問題としてダイクストラ法で解いてみましたが速度出てません。
もしかしたら何も考えない深さ優先探索の方が早いかもしれません。
#include<stdio.h>
#include<map>
#include<string>
#include<queue>
struct S{
std::string str;
int cost;
bool operator<(const S& s)const{
if(cost!=s.cost)return cost>s.cost;
return str<s.str;
}
};
int main(){
std::map<std::string,int> memo;
std::priority_queue<S> qu;
int n;
scanf("%d",&n);
S s,nextS;
s.cost=0;
std::string str="123456789";
s.str=str.substr(0,n);
int costs[8][8];
char c;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&costs[i][j]);
}
}
qu.push(s);
memo[s.str]=s.cost;
int ans=0;
while(qu.empty()==false){
s=qu.top();
qu.pop();
if(memo.find(s.str)!=memo.end()&&memo[s.str]<s.cost)continue;
memo[s.str]=s.cost;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
str=s.str;
c=str[i];
str[i]=str[j];
str[j]=c;
nextS.cost=s.cost+costs[i][j];
if(memo.find(str)!=memo.end()&&memo[str]<=nextS.cost)continue;
memo[str]=nextS.cost;
nextS.str=str;
qu.push(nextS);
}
}
}
for(std::map<std::string,int>::iterator it=memo.begin();it!=memo.end();it++){
if(ans<(*it).second)ans=(*it).second;
}
printf("%d\n",ans);
}
*2362 Chicken or the Egg
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2362
鶏が先か卵が先かこれを解明できる古文書を読解する問題。
問題のルールを理解するのに少し時間がかかる。
卵鶏卵鶏鶏卵 と並んでいる場合並んでいる鶏で区切って
(卵鶏卵鶏)と(鶏卵)で分割し、分割した内容を後ろから読んでより後ろがご先祖様になる。
この後ろから読むという部分を読解できるかどうかがこの問題最大の難関。
問題を解くコード自体は極めて簡素にできる。
#include<stdio.h>
int main(){
char c,str[7],ans,old=' ';
int count=0,ansCount=0;
while(scanf("%c",&c)!=EOF && c!='\n'){
if(c=='e'){
scanf("%2s",str);
}else if(c=='c'){
scanf("%6s",str);
}
if(c==old){
if(ansCount<count){
ans=c;
ansCount=count;
}
count=0;
}
count++;
old=c;
}
if(ansCount<count)ans=old;
printf("%s\n",ans=='e'?"egg":"chicken");
}
*2364 Lucky Dip
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2364
一度調べたところは二度と調べないようマップにチェックを入れて後は優先順位付きキューと幅優先探索による解法。
簡単な問題だが一回目はタイムリミッド、２回目はメモリオーバー、後は一か所の記述ミスに気づかず２連続WAを食らった。
こんな簡単な問題であまりに恥ずかしい結果である。
#include<stdio.h>
#include<queue>
#include<set>
#include<vector>
char map[1002][1002];
struct P{
int x,y,time;
};
class timeSorter {
public:
bool operator()(const P& l, const P& r) const {
return l.time>r.time;
}
};
class posSorter{
public:
bool operator()(const P& l,const P& r)const{
if(l.x!=r.x)return l.x<r.x;
return l.y<r.y;
}
};
int main(){
int w,h,gx,gy;
scanf("%d %d",&w,&h);
for(int r=0;r<h;r++){
scanf("%s",map[r]);
}
std::priority_queue<P,std::vector<P>,timeSorter> points;
std::set<P,posSorter> wMemo;//開く隔壁のメモ
int wx,wy,time=0;
P p,nextP;
p.time=p.x=p.y=0;
points.push(p);
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
int n;
scanf("%d",&n);
std::vector<int> wxs,wys;
for(int i=0;i<n;i++){
scanf("%d %d",&p.x,&p.y);
wMemo.insert(p);//開く隔壁の場所をメモ
wxs.push_back(p.x);
wys.push_back(p.y);
}
while(!points.empty()){
p=points.top();
points.pop();
//printf("<%d %d %d> ",p.x,p.y,p.time);
if(map[p.y][p.x]=='t')break;//ゴールに到達
if(time<p.time){
if(time>=n)break;//理論上あり得ないが一応念のため
map[wys[time]][wxs[time]]='.';
time=p.time;
}
if(map[p.y][p.x]=='#'){
p.time++;//隔壁が開いてないので待つ
points.push(p);
continue;
}
map[p.y][p.x]='*';//このフロアは調べたので進入禁止
for(int i=0;i<4;i++){
nextP.x=p.x+dxs[i];
nextP.y=p.y+dys[i];
nextP.time=p.time;
if(nextP.x<0||w<=nextP.x||nextP.y<0||h<=nextP.y)continue;
char c=map[nextP.y][nextP.x];
if(c=='*')continue;//調済ずみフロアだった
if(c=='.')map[nextP.y][nextP.x]='*';//このフロアは調べたので進入禁止に
if(c=='#'&&wMemo.find(nextP)==wMemo.end())continue;//この壁は開かない
if(c=='#')nextP.time++;
points.push(nextP);
}
}
if(map[p.y][p.x]=='t')printf("%d\n",p.time);
else printf("-1\n");
}
*2366 Elevator
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2366
一基あるエレベータを使ってエレベータの移動距離が最短になるように建物から荷物をおろしていく問題。
この問題は一階ずつ解決していきます。
まず最上階にある荷物を下ろすために最上階に行きます。
そしてその下にある荷物のある階に荷物を全ておろしいったんエレベータから荷物をすべて出します。
後は、今いる階を最上階とみなして同じ操作を続ければ完了です。
忘れてはいけない点は速度を出すために隠し味として各階の移動に動的計画法を使います。
この問題は不正回を出しまくったうえ自力で正しい考え方に至るのに一週間もかかりました。
もしエレベータの数が複数になって、各エレベータの止まる階や重量制限がバラバラになった場合手も足も出ない問題です。
#include<stdio.h>
#include<vector>
#include<map>
#include <stdlib.h>
struct goods{
int w,floor;//重さと階と
};
int n,m,W,ans=0;
int tempAns;
std::vector<goods> datas;
std::vector<int> floors;
std::map<int,int> memo;
void saiki(std::vector<int>& ws,int state,int w,int all,int count){
if(tempAns<=count)return;
if(state==all){
tempAns=tempAns>count?count:tempAns;
}else{
int no=1;
for(int i=0;i<ws.size();i++){
if((state&no)!=0){
//何もしない
}else if(ws[i]+w>W){
if(memo.find(state)==memo.end()){
memo[state]=count;
}else if(memo[state]>count){
memo[state]=count;
}else{
no*=2;
continue;
}
saiki(ws,state|no,ws[i] ,all,count+1);
}else{
saiki(ws,state|no,w+ws[i],all,count);
}
no*=2;
}
}
}
int main(){
int k;
goods g;
scanf("%d %d %d",&n,&m,&W);
m--;
floors.push_back(0);
for(int i=0;i<n;i++){
scanf("%d",&k);
g.floor=i;//1階をレベル0とする
//一階の荷物は無視する
if(k!=0&&i!=0){
floors.push_back(i);
}
while(k--){
scanf("%d",&g.w);
if(i==0) continue;
datas.push_back(g);
}
}
if(floors.size()>1)ans=abs(m-floors[floors.size()-1]);
for(int i=floors.size()-1;i>0;i--){
int now =floors[i];
int next=floors[i-1];
int move=now-next;
int all=0;
int no=1;
std::vector<int> ws;
ws.clear();
for(unsigned int j=0;j<datas.size();j++){
if(datas[j].floor>=now){
ws.push_back(datas[j].w);
all+=no;
no*=2;
}
}
tempAns=1000;
memo.clear();
saiki(ws,0,0,all,1);
if(tempAns>=1){
ans+=move+(tempAns-1)*move*2;
}
}
printf("%d\n",ans);
}
*2369 CatChecker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2369
鳴き声を表すテキストから、その鳴き声が兎かネコか分類する問題。
ルールはｍの後にはｗ、eの後にe,wの後にｗがこず、ｍから入ってｗで抜ける入れ子構造になってる点。
後はこれをコード化するだけ。
#include<stdio.h>
int main(){
char text[502],c1,c2;
scanf("%s",text);
int in=0;
bool ok=true;
for(int i=0;text[i]!='\0'&&ok==true;i++){
c1=text[i];
c2=text[i+1];
if(in<1&&c1!='m')ok=false;
if(c1=='m'&&c2=='w')ok=false;
if(c1=='e'&&c2=='e')ok=false;
if(c1=='w'&&c2=='m')ok=false;
in+=(c1=='m')-(c1=='w');
if(in<0)ok=false;
}
printf("%s\n",ok==true&&in==0?"Cat":"Rabbit");
}
