「2011年３月」の編集履歴（バックアップ）一覧はこちら
「2011年３月」(2011/03/24 (木) 20:09:59) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*2011/3/8～9
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2108&lang=jp
リンク先問題を解くコード作りかけ
アーロンとブルースでキャッチできた場合を考えると？
ブルースは探索の先から帰ってきたルートのうち、一番短時間で
捕まえられるルートを選べばいい。
アーロンは一番長いルートを選べばいい？
これで答えが出るはずなのだが？
何かが間違ってるらしく正しい答えが出ない。
#include <stdio.h>
#include <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];
}
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0526&lang=jp
リンク先問題を解くコード作りかけ計算量が不安になるなこの問題。
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0558&lang=jp
リンク先問題を解くコード。
自分のコードは実行時間もメモリ使用量も大き目、正答者ランキングを見てみるとどうやってかメモリ使用量0、探索時間0.0001とか叩きだしてる？
#include <stdio.h>
#include <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
http://www.jssurfboards.com/
このサイト、もし僕ならボードのサイズと重さ。
対応する波のサイズ、ボードの浮力の強さ（大きいなら初心者向け）、初心者向け上級者向けという分類、ボードのサイズをメートルで書くだろうな。
浜別お勧めの一枚ページとか追加したいな。
湘南でサーフするなら湘南の穏やかな波に対応したこのボード。
北海道でサーフするなら、夏～秋にかけての暖かい時期、この時期に来る台風や低気圧による大波を狙ったロングボード。
、、、
とか加えて画面左に県名と浜の名前の一覧、クリックすると画面右に適正体重付きお勧めボードと簡単な解説。
む、私ＨＴＭＬできるし、メール出してページの作りなおし仕事で小銭稼げないだろうか？
とか妄想するも、デザインセンスや納期という言葉にびくびく。
単純肉体労働しかしたことないから提案とか想像もつかないな。
*2011/3/17
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0541&lang=jp
を解く問題作りかけ。
この問題はある地点を何回通るかを計算してそれをメモ化してあげるだけで解ける？
と想定して書きかけ。
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0207&lang=jp
最近スランプ。
簡単な問題でもやって調子を整えよう。
書きかけ。
#include <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;
}
}
http://rose.u-aizu.ac.jp/onlinejudge/UserInfo.jsp?id=sinapusu2002
最近の私の成績。
会津大学のプログラムの問題集を解いてる成績。
答えはみず自力で問題を解くという方針で挑戦中。
で、リンク先の丸グラフが私の成績。
青色のACが正答率でそれ以外は時間切れや間違い。
うーん簡単な問題が残ってないので、今後は不正解率が上がってくな。
手も足も出ない問題ばかり残った。
大卒なら楽勝なのだろうか？
*2011/3/11
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0113&lang=jp
リンク先問題を解くコード、作りかけ
何か、循環小数を高速で見つける賢い方法もあるらしいが知らないので、高校生レベルの解き方で解く。
#include <stdio.h>
#include <set>
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
リンク先を解くコード。
意外と例外処理が多いのでめんどくさい。
記述ミスがないか怖いなあ。
#include <stdio.h>
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
を解くコード。
うーん、そのまま実装すればいいんだけど、探索だと計算量がおかしなことになる。
メモカ探索だな。
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0179
を解くコードなのだけど、なぜかテストデータを通らない？
何かポカミスでもあったかな？
変数の初期化忘れだった。
まだまだ高校生レベルプログラムの世界。
もう少し精進しないと。
プログラムの腕を磨いてお金を稼いで、阿部大和ちゃんをお嫁さんにしてかわいい赤ちゃんをまいにち抱っこするような生活送りたいなあ。
#include <stdio.h>
#include <string.h>
#include <set>
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0200&lang=jp
を解くコード。
なのだがテストコードに通すの怖い。
初期化忘れとか、、、怖い。
チェックしてから投稿することにしよう。
#include <stdio.h>
#include <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/3/8～9
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2108&lang=jp
リンク先問題を解くコード作りかけ
アーロンとブルースでキャッチできた場合を考えると？
ブルースは探索の先から帰ってきたルートのうち、一番短時間で
捕まえられるルートを選べばいい。
アーロンは一番長いルートを選べばいい？
これで答えが出るはずなのだが？
何かが間違ってるらしく正しい答えが出ない。
#include <stdio.h>
#include <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];
}
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0526&lang=jp
リンク先問題を解くコード作りかけ計算量が不安になるなこの問題。
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0558&lang=jp
リンク先問題を解くコード。
自分のコードは実行時間もメモリ使用量も大き目、正答者ランキングを見てみるとどうやってかメモリ使用量0、探索時間0.0001とか叩きだしてる？
#include <stdio.h>
#include <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
http://www.jssurfboards.com/
このサイト、もし僕ならボードのサイズと重さ。
対応する波のサイズ、ボードの浮力の強さ（大きいなら初心者向け）、初心者向け上級者向けという分類、ボードのサイズをメートルで書くだろうな。
浜別お勧めの一枚ページとか追加したいな。
湘南でサーフするなら湘南の穏やかな波に対応したこのボード。
北海道でサーフするなら、夏～秋にかけての暖かい時期、この時期に来る台風や低気圧による大波を狙ったロングボード。
、、、
とか加えて画面左に県名と浜の名前の一覧、クリックすると画面右に適正体重付きお勧めボードと簡単な解説。
む、私ＨＴＭＬできるし、メール出してページの作りなおし仕事で小銭稼げないだろうか？
とか妄想するも、デザインセンスや納期という言葉にびくびく。
単純肉体労働しかしたことないから提案とか想像もつかないな。
*2011/3/17
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0541&lang=jp
を解く問題作りかけ。
この問題はある地点を何回通るかを計算してそれをメモ化してあげるだけで解ける？
と想定して書きかけ。
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0207&lang=jp
最近スランプ。
簡単な問題でもやって調子を整えよう。
書きかけ。
#include <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;
}
}
http://rose.u-aizu.ac.jp/onlinejudge/UserInfo.jsp?id=sinapusu2002
最近の私の成績。
会津大学のプログラムの問題集を解いてる成績。
答えはみず自力で問題を解くという方針で挑戦中。
で、リンク先の丸グラフが私の成績。
青色のACが正答率でそれ以外は時間切れや間違い。
うーん簡単な問題が残ってないので、今後は不正解率が上がってくな。
手も足も出ない問題ばかり残った。
大卒なら楽勝なのだろうか？
*2011/3/11
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0113&lang=jp
リンク先問題を解くコード、作りかけ
何か、循環小数を高速で見つける賢い方法もあるらしいが知らないので、高校生レベルの解き方で解く。
#include <stdio.h>
#include <set>
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
リンク先を解くコード。
意外と例外処理が多いのでめんどくさい。
記述ミスがないか怖いなあ。
#include <stdio.h>
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0230&lang=jp
を解くコード。
うーん、そのまま実装すればいいんだけど、探索だと計算量がおかしなことになる。
メモカ探索だな。
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0179
を解くコードなのだけど、なぜかテストデータを通らない？
何かポカミスでもあったかな？
変数の初期化忘れだった。
まだまだ高校生レベルプログラムの世界。
もう少し精進しないと。
プログラムの腕を磨いてお金を稼いで、阿部大和ちゃんをお嫁さんにしてかわいい赤ちゃんをまいにち抱っこするような生活送りたいなあ。
#include <stdio.h>
#include <string.h>
#include <set>
#include <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
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0200&lang=jp
を解くコード。
なのだがテストコードに通すの怖い。
初期化忘れとか、、、怖い。
チェックしてから投稿することにしよう。
#include <stdio.h>
#include <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]);
}
