2011/3/8～9
ブルースは探索の先から帰ってきたルートのうち、一番短時間で
捕まえられるルートを選べばいい。
アーロンは一番長いルートを選べばいい？
これで答えが出るはずなのだが？
何かが間違ってるらしく正しい答えが出ない。
<stdio.h>
<algorithm>
void solve();
int searchA(int a,int b,int deep,bool stop);
int searchB(int a,int b,int deep,bool stop);
int map[51][51];//
int m;
int myMax=1000000000;
int moveCatchA[51][51];
int moveCatchB[51][51];
int moveDeepA[51][51];
int moveDeepB[51][51];
bool moveOKsA[51][51];
bool moveOKsB[51][51];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&m);
solve();
}
}
void solve(){
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
scanf("%d",&map[i][j]);
moveCatchA[i][j]=0;
moveCatchB[i][j]=myMax;
moveDeepA[i][j]=0;
moveDeepB[i][j]=myMax;
moveOKsA[i][j]=moveOKsB[i][j]=true;
}
}
int a,b;
scanf("%d %d",&a,&b);
int ans=searchA(a,b,1,false);
printf("ans=%d\n",ans);
}
int searchA(int a,int b,int deep,bool stop)
{
//アーロンの移動
int maxCatch=0;
int t;
if(a==b){
moveDeepA[a][a]=std::max(moveDeepA[a][a],deep);
moveCatchA[a][b]=moveDeepA[a][a];
return moveDeepA[a][a];
}
if(moveOKsA[a][b]==false && deep<=moveDeepA[a][b])return moveCatchA[a][b];
if(moveOKsA[a][b]==false && deep>moveDeepA[a][b]){
moveCatchA[a][b]+=(deep-moveDeepA[a][b]);
moveDeepA[a][b] =deep;
return moveCatchA[a][b];
}
moveOKsA[a][b]=false;
for(int i=0;i<m;i++)
{
if(map[a][i]==1)
{
t=searchB(i,b,deep,false);
if(t>maxCatch)
{
maxCatch=t;
}
}
}
if(stop==false){
t=searchB(a,b,deep,true);
maxCatch=std::max(maxCatch,t);
}
moveDeepA [a][b]=std::max(moveDeepA [a][b],deep);
moveCatchA[a][b]=std::max(moveCatchA[a][b],maxCatch);
return moveCatchA[a][b];
}
int searchB(int a,int b,int deep,bool stop){
//キャッチできたらターンを返す
int minCatch=myMax;
int t;
if(a==b){
moveDeepB[a][a]=std::min(moveDeepB[a][a],deep);
moveCatchB[a][a]=moveDeepB[a][a];
return moveDeepB[a][a];
}
if(moveOKsB[a][b]==false && deep<moveDeepB[a][b]){
moveCatchB[a][b]-=(moveDeepB[a][b]-deep);
moveDeepB[a][b]=deep;
return moveCatchB[a][b];
}
moveOKsB[a][b]=false;
for(int i=0;i<m;i++){
if(map[b][i]==1){
t=searchA(a,i,deep+1,false);
if(t<minCatch) minCatch=t;
}
}
if(stop==false){
minCatch=std::min(minCatch,searchA(a,b,deep+1,true));
}
moveCatchB[a][b]=std::min(moveCatchB[a][b],minCatch);
moveDeepB [a][b]=std::min(moveDeepB [a][b],deep);
return moveCatchB[a][b];
}
<stdio.h>
int map[101][101];//ダイクストラ法で解くためのマップ、より低い移動経路が現れたら更新する
int rootCost[101][101];//i番目の島からｊ番目の島への移動コスト
bool moveOKs[101][101];//i番目の島からの移動を測る
bool calcMapFlag[101];//i番目の島から移動するのが計算済みならtrue 新しい航路が一つでも加えられた一度全部falseに戻す
int n,k;
int myMax=1000000000;
int main(){
scanf("%d %d",&n,&k);
while(n!=0 || k!=0){
solve();
scanf("%d %d",&n,&k);
}
}
void solve(){
ResetMap();
int a,b,e;
for(int i=0;i<k;i++){
scanf("%d",&t);
if(t==0){
scanf("%d %d",&a,&b);
if(calcMapFlag[a]==false){
Dijkstra(a);
}
if(rootCost[a][b]<myMax){
printf("%d\n",rootCost[a][b]);
}else{
printf("-1\n");
}
}else{
scanf("%d %d",&a,&b,&e);
if(map[a][b]>e){
map[a][b]=e;
ResetMap();
}
}
}
}
void ResetMap(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
moveOKs[i][j]=true;
rootCost[i][j]=myMax;
}
calcMapFlag[i]=false;
}
}
void Dijkstra(int s){
rootCost[s][s]=0;
int min;
int p;
int t;
for(int i=0;i<n;i++)
{
min=myMax;
for(int j=1;j<=n;j++){
if(min>rootCost[s][j] && moveOKs[s][j]==true){
min=rootCost[s][j];
p=j;
}
}
if(min==myMax ) return;
moveOKs[s][p]=false;
for(int j=1;j<=n;j++){
if(rootCost[s][p]+map[p][j]<rootCost[s][j]){
rootCost[s][j]=rootCost[s][p]+map[p][j];
}
}
}
}
2011/3/24
実機の戦闘機ってどんな感じなんだろ？
まず、実機は重いよな？
20トンの機体が時速1000ｋｍ2000ｋｍで飛ぶわけだ。
時速1000ｋｍの20ｔｎの弾丸でこの軌道曲げる、と考えたら旋回というものが恐ろしく大変なものだろうということは想像がつくし、翼から空気が剥離したりしてコントロールを失った時の恐怖感というのは想像がつかなくもない、空力の影響を受けながら弾丸のように放物線を描くのだろう、それが下向きだったら最悪だ。
エンジンだって車のように好き放題に微調整できるわけでもないだろう。
燃費だって20トンを高速で動かすために最悪だ、微調整一つのパタン一つ間違えただけで燃料消費が悪くなるだろう。
うーん実機の世界ってどんなものなんだろう？
軽いセスナ機とかは軽いから空気の上にふわっと浮かぶようなイメージだろうか？
一生縁がないとはいえ気になる。
2011/3/24
<stdio.h>
<queue>
void solve();
char **map;
bool **moveOKs;
struct point{
int x,y,no;
};
int main()
{
map=new char*[1001];
moveOKs=new bool*[1001];
for(int i=0;i<1001;i++){
map[i]=new char[1001];
moveOKs[i]=new bool[1001];
}
solve();
for(int i=0;i<1001;i++){
delete [] map[i];
delete [] moveOKs[i];
}
delete [] map;
delete [] moveOKs;
}
void solve(){
int h,w,n;
char t;
point goals[11];
point p;
scanf("%d %d %d",&h,&w,&n);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf(" %c",&t);
if(t=='S'){
p.x=j;p.y=i;p.no=0;
goals[0]=p;
map[i][j]='.';
}else if('9'>=t && t>'0'){
p.x=j;p.y=i;p.no=0;
goals[t-'0']=p;
map[i][j]='.';
}else{
map[i][j]=t;
}
moveOKs[i][j]=true;
}
}
int dx[]={1,0,-1,0};
int dy[]={0,-1,0,1};
int sumTime=0;
point nextPoint;
point nextGoal;
int nx,ny,nNo;
bool goalFlag=false;
for(int i=0;i<n;i++){
std::queue<point> points;
p=goals[i];
nextGoal=goals[i+1];
points.push(p);
for(int j=0;j<h;j++){
for(int k=0;k<w;k++){
moveOKs[j][k]=true;
}
}
while(points.empty()==false){
p=points.front();
points.pop();
moveOKs[p.y][p.x]=false;
for(int i=0;i<4;i++){
nx=p.x+dx[i];
ny=p.y+dy[i];
nNo=p.no+1;
if(nx==nextGoal.x && ny==nextGoal.y){
sumTime+=nNo;
goalFlag=true;
break;
}
if(w>nx && nx>=0 && h>ny && ny>=0 && moveOKs[ny][nx]==true && map[ny][nx]=='.'){
nextPoint.x=nx;
nextPoint.y=ny;
nextPoint.no=nNo;
points.push(nextPoint);
moveOKs[ny][nx]=false;
}
}
if(goalFlag==true){
goalFlag=false;
break;
}
}
}
printf("%d\n",sumTime);
}
2011/3/11
浜別お勧めの一枚ページとか追加したいな。
湘南でサーフするなら湘南の穏やかな波に対応したこのボード。
北海道でサーフするなら、夏～秋にかけての暖かい時期、この時期に来る台風や低気圧による大波を狙ったロングボード。
、、、
とか加えて画面左に県名と浜の名前の一覧、クリックすると画面右に適正体重付きお勧めボードと簡単な解説。
む、私ＨＴＭＬできるし、メール出してページの作りなおし仕事で小銭稼げないだろうか？
とか妄想するも、デザインセンスや納期という言葉にびくびく。
単純肉体労働しかしたことないから提案とか想像もつかないな。
2011/3/17
<stdio.h>
int main()
{
bool map[1002][1002];
int countMap[1002][1002];
int h,w,n;
int t;
while(h!=0 && w!=0 && n!=0){
for(int i=0;i<h+1;i++){
for(int j=0;j<w+1;j++){
if(i<h && j<w){
scanf("%d",&t);
if(t==1) map[i][j]=true;
else map[i][j]=false;
}
countMap[i][j]=0;
}
}
countMap[0][0]=n-1;
int t;
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
t=countMap[i][j];
if(t%2==1){
countMap[i+1][j]=t/2;//南
countMap[i][j+1]=t/2;//東
if(map[i][j]==true){
countMap[i][j+1]++;
}else
{
countMap[i+1][j]++;
}
}else
{
countMap[i+1][j]=t/2;
countMap[i][j+1]=t/2;
}
if(t%2==1)
{
map[i][j]=!map[i][j];
}
}
}
int px=0,py=0;
while(px<w && py<h)
{
if(map[py][px]==true){
px++;
}else{
py++;
}
}
printf("%d %d\n",px+1,py+1)
}
}
2011/3/16
<stdio.h>
void addBlock(int color,int d,int x,int y);
int map[102][102];
int xs,ys,xg,yg;
int w,h;
int main(){
}
void addBlock(int color,int d,int x,int y)
{
if(d==0){
//横向き
map[x][y]=map[x+1][y]=map[x+2][y]=map[x+3][y]=color;
map[x][y+1]=map[x+1][y+1]=map[x+2][y+1]=map[x+3][y+1]=color;
}else{
//縦向き
map[x][y]=map[x][y+1]=map[x][y+2]=map[x][y+3]=color;
map[x+1][y]=map[x+1][y+1]=map[x+1][y+2]=map[x+1][y+3]=color;
}
}
で、リンク先の丸グラフが私の成績。
青色のACが正答率でそれ以外は時間切れや間違い。
うーん簡単な問題が残ってないので、今後は不正解率が上がってくな。
手も足も出ない問題ばかり残った。
大卒なら楽勝なのだろうか？
2011/3/11
<stdio.h>
<set>
<vector>
std::set<int> amari;
std::vector<int> kekka;
std::vector<int> amari2;
std::vector<int>::iterator it_amari;
std::vector<int>::iterator it_kekka;
void solve(int a,int b);
int main(void){
int a,b;
while(scanf("%d %d",&a,&b)!=EOF){
solve(a,b);
}
}
void solve(int a,int b)
{
int lastAmari;
a%=b;
while(a!=0){
while(a/b==0){
a*=10;
if(a/b>0){
break;
}else{
kekka.push_back(0);
}
}
kekka.push_back(a/b);
a%=b;
if(amari.find(a)!=amari.end()){
lastAmari=a;
roopFlag=true;
break;
}else{
amari.insert(a);
amari2.push_back(a);
}
}
it_amari=amari2.begin();
it_kekka=kekka.begin();
if(a==0){
while(it_kekka!=kekka.end()){
printf("%d",*it_kekka);
it_kekka++;
}
printf("\n");
}else{
while(*it_amari)
}
}
2011/3/9
ギガンダム討伐も星の庭師もその他の作品も中途半端だな俺。
創作というのは楽にできる人もいるだろうけど、僕にとっては全力を出さないと作品を作れない。
朝から晩まで作品のことを一生懸命考えて、どうしたらいい作品ができるだろう。
どんなギミックならいいだろうと専門書をあさってようやく少しだけ書ける。
そういうことをするのはとても疲れてめんどくさい作業。
結局続きが書けない。
そうして作っても所詮は3流、大したものじゃない。
作品を読んだ方は分かると思うけど、元ネタ明記で作品を作っている。
元ネタだらけだからオリジナリティも少ない。
結局創作というものを諦めてしまう。
堀江伸一
2011/3/3
<stdio.h>
<algorithm>
void upDown(int *b,int *moves,int n);
void solve(int n);
int myMin(int a,int b);
int b1[104],b2[104];
int moves1[104],moves2[104];//0なら未踏、1以上ならそこからジャンプ、-1なら滑り降りか上りでジャンプではない
int jumpCount;
int newJumpCount;
int main()
{
int n;
scanf("%d",&n);
while(n>0)
{
solve(n);
scanf("%d",&n);
}
}
void solve(int n)
{
//梯子の場合一番上まで昇ってからジャンプ
//それを忘れずに探索すること
for(int i=0;i<n;i++){
scanf("%d",&b1[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&b2[i]);
moves1[i]=moves2[i]=0;
}
for(int i=0;i<3;i++){
moves1[i]=moves2[i]=1;
}
upDown(b1,moves1,n);
upDown(b2,moves2,n);
newJumpCount=1;//ジャンプで新しい地点に到達したらインクリメント、これが0のままなら永遠にたどり着けない
while(newJumpCount>0){
newJumpCount=0;
if(moves1[n-1]>0 || moves2[n-1]>0){
if(moves1[n-1]>0 && moves2[n-1]>0){
printf("%d\n",std::min(moves1[n-1],moves2[n-1]));
}else if(moves1[n-1]>0 && moves2[n-1]<1){
printf("%d\n",moves1[n-1]);
}else if(moves2[n-1]>0 && moves1[n-1]<1){
printf("%d\n",moves2[n-1]);
}
return;
}
for(int i=0;i<n;i++){
if(moves1[i]>0){
if(moves2[i]==0 || moves2[i+1]==0 || moves2[i+2]==0){
newJumpCount++;
}
moves2[i+0]=myMin(moves1[i]+1,moves2[i+0]);
moves2[i+1]=myMin(moves1[i]+1,moves2[i+1]);
moves2[i+2]=myMin(moves1[i]+1,moves2[i+2]);
}
}
upDown(b2,moves2,n);
for(int i=0;i<n;i++){
if(moves2[i]>0){
if(moves1[i]==0 || moves1[i+1]==0 || moves1[i+2]==0){
newJumpCount++;
}
moves1[i+0]=myMin(moves2[i]+1,moves1[i+0]);
moves1[i+1]=myMin(moves2[i]+1,moves1[i+1]);
moves1[i+2]=myMin(moves2[i]+1,moves1[i+2]);
}
}
}
printf("NA\n");
return ;
}
int myMin(int a,int b){
if(b>0){
return std::min(a,b);
}else{
return a;
}
}
void upDown(int *b,int *moves,int n){
//梯子を上る処理
bool upOK=false;
int upMin;
for(int i=0;i<n;i++){
if(b[i]==1 && moves[i]>0 && upOK==false){
upOK=true;
upMin=moves[i];
moves[i]=-1;
}else if(b[i]!=1 && upOK==true){
moves[i-1]=myMin(upMin,moves[i-1]);
upOK=false;
}
if(upOK==true && moves[i]>0){
upMin=std::min(upMin,moves[i]);
moves[i]=-1;
}
}
//滑り降りる処理
bool downOK=false;
int downMin;
for(int i=n-1;i>=0;i--){
if(b[i]==2 && moves[i]>0 && downOK==false){
downMin=moves[i];
moves[i]=-1;
downOK=true;
}else if(b[i]!=2 && downOK==true){
moves[i]=myMin(downMin,moves[i]);
downOK=false;
}
if(downOK==true && moves[i]>0){
downMin=std::min(downMin,moves[i]);
moves[i]=-1;
}
}
}
2011/3/2
<stdio.h>
int b1[101],b2[101];
bool moveOKs1[101],moveOKs2[101];//左右のビルで一度通った場所を２度とおるなら永遠に登れない
int main()
{
int n;
scanf("%d",&n);
while(n>0)
{
scanf("%d",&n);
}
}
void solve(int n)
{
//梯子の場合一番上まで昇ってからジャンプ
//それを忘れずに探索すること
for(int i=0;i<n;i++) scanf("%d",b1[i]);
for(int i=0;i<n;i++) scanf("%d",b2[i]);
}
2011/3/2
<stdio.h>
<string.h>
<set>
<string>
void search();
std::string changeColor(std::string worm,int p);
std::string s1;
std::set<std::string> worms;//一度通った色を覚える
std::set<std::string> nows;//ｎターン目の虫の色たち
std::set<std::string> nexts;//次の虫の色たち
std::set<std::string>::iterator it;
char cWorm[11];
int minTime;
int n;
int timeMax=1000000000;
int main(){
scanf("%s",cWorm);
n=strlen(cWorm);
while(cWorm[0]!='0' && n>1){
minTime=0;
worms.clear();
nows.clear();
nexts.clear();
search();
if(minTime==timeMax){
printf("NA\n");
}else{
printf("%d\n",minTime);
}
scanf("%s",cWorm);
n=strlen(cWorm);
}
}
int rgbCount(std::string cWorm){
int colorCount=0;//同色のカウント
char t=cWorm[0];
for(int i=0;i<n;i++){
if(t==cWorm[i]) colorCount++;
else break;
}
return colorCount;
}
void search(){
//幅優先探索で検索する。
//3＾10≒60000なので何とかなる
nows.insert(cWorm);
worms.insert(cWorm);
if(rgbCount(std::string(cWorm))==n){minTime=0; return;}
std::string worm,nextWorm;
int changeCount=1;
while(changeCount>0){
minTime++;
changeCount=0;
it=nows.begin();
nexts.clear();
while(it!=nows.end()){
worm=(*it);
for(int i=0;i<n-1;i++){
if(worm[i]!=worm[i+1]){
nextWorm=changeColor(worm,i);
if(worms.find(nextWorm)==worms.end()){
worms.insert(nextWorm);
nexts.insert(nextWorm);
changeCount++;
if(rgbCount(nextWorm)==n) return;
}
}
}
it++;
}
nows.clear();
it=nexts.begin();
while(it!=nexts.end()){
nows.insert(*it);
it++;
}
}
minTime=timeMax;
return ;
}
std::string changeColor(std::string worm,int p){
char t1,t2,t3;
std::string nextworm=worm;
t1=worm[p];
t2=worm[p+1];
if((t1=='r' && t2=='g') || (t1=='g' && t2=='r')){
nextworm[p]=nextworm[p+1]='b';
}else if((t1=='r' && t2=='b') || (t1=='b' && t2=='r')){
nextworm[p]=nextworm[p+1]='g';
}else if((t1=='g' && t2=='b') || (t1=='b' && t2=='g')){
nextworm[p]=nextworm[p+1]='r';
}
return nextworm;
}
2011/3/1
チェックしてから投稿することにしよう。
<stdio.h>
<map>
void setmap(int n,int m);
void searchMapCost(int s,int g,int m,std::map<int,int> *map);
std::map<int,int> costMap[101];
std::map<int,int> timeMap[101];
std::map<int,int>::iterator nextHome;
bool moveOKs[101];
int costs[101];
int mymax=1000000000;
int main(void)
{
int n,m;
scanf("%d %d",&n,&m);
while(n!=0 || m!=0){
setmap(n,m);
scanf("%d %d",&n,&m);
}
}
void setmap(int n,int m){
for(int i=1;i<=m;i++){
costMap[i].clear();
timeMap[i].clear();
}
int a,b,cost,time;
for(int i=0;i<n;i++)
{
scanf("%d %d %d %d",&a,&b,&cost,&time);
costMap[a][b]=cost;
costMap[b][a]=cost;
timeMap[a][b]=time;
timeMap[b][a]=time;
}
int k;
scanf("%d",&k);
int p,q,r;
for(int i=0;i<k;i++)
{
scanf("%d %d %d",&p,&q,&r);
if(r==0){
searchMapCost(p,q,m,costMap);
}else if(r==1){
searchMapCost(p,q,m,timeMap);
}
}
}
void searchMapCost(int s,int g,int m,std::map<int,int> *map){
for(int i=1;i<=m;i++){
costs[i]=mymax;
moveOKs[i]=true;
}
costs[s]=0;
int min=mymax;
int p;
int key,v;
for(int k=0;k<m+1;k++)
{
min=mymax;
for(int i=1;i<=m;i++){
if(costs[i]<min && moveOKs[i]==true){
min=costs[i];
p=i;
}
}
if(min==mymax) break;
moveOKs[p]=false;
nextHome=map[p].begin();
while(nextHome!=map[p].end()){
key=(*nextHome).first;
v=(*nextHome).second;
if(costs[p]+v<costs[key]) costs[key]=costs[p]+v;
nextHome++;
}
}
printf("%d\n",costs[g]);
}
最終更新：2011年03月24日 20:09
