2361 Sort
解法
とりあえずグラフの問題としてダイクストラ法で解いてみましたが速度出てません。
もしかしたら何も考えない深さ優先探索の方が早いかもしれません。
#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
#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
#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
ルールはｍの後にはｗ、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");
}
最終更新：2013年01月28日 11:05
