「2011年5月」の編集履歴（バックアップ）一覧はこちら
2011年5月 - (2011/06/14 (火) 18:50:05) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
堀江伸一
兵庫県加古川市加古川町南備後79-16
*2011/6/13
http://www.youtube.com/watch?v=-G2-Omy9FgU&NR=1
室内で動いてる人がいるかどうかを知ることができる新しい防犯システム。
なんか蝙蝠の超音波みたいですごいな。
もっと進化したら、どこらへんを動いてるかもわかるようになるのかも？
ニューロネットとの融合とか敵を探すためのロボ･歩兵用装備とか色々妄想してしまう。
しかしこれ動いている人がいるということを識別するだけで誰が動いている窯では判別できないよな。
個人識別用の別のシステムと併用しないとだめなことを考えると組織でしか使えない気がする？
http://www.youtube.com/watch?v=R2fyLl7KZXM&feature=related
ぶは。
量子コンピュータの授業が無料で上がってる。
俺には一生縁がない話しだけれど好奇心で見てみるか。
*2011/6/2
自分的プログラム勉強予定。
その１
会津大学オンラインジャッジの問題集をもう少しだけ解く。
これが終わると基礎的なアルゴリズムの勉強はひとまず終わりと定義(あくまで基礎、大学でやってるような高度な数学や工学と融合したアルゴリズムからみたら会津台の問題で身につくアルゴリズムは多分低レベル)。
書籍を読んで色々なプログラムの分野について学ぶ。
アプリ制作講座等を一通り書いてある通りに記述しコンパイルし微改造したりして、アプリを作るということそのものに慣れる。
普通のプログラマなら１０代の時から何年もかけてレベルアップしてその上に大学の知識を身につけているわけだよな。
複雑で高度な抽象的構造物を考えることに慣れた頭、それが普通のプログラマだよな。
いい年してから本気でプログラムを学ぼうとしている私はこの圧倒的な学習時間の差を埋めないといけない。
ただ埋めるだけでなく、私の場合若い時に高度な抽象的思考の訓練や物理や工学的発想といった訓練を受けていないというハンデがある。
この恐ろしく大きな溝を飛び越えないとプログラマに慣れないわけだよな。
社会にでてからは単純肉体労働以外ついたことがないので、世の中のことや業務的な発想というものは全くできない頭ときている。
すると、私が飛び越えなくてはいけない溝はどれだけ大きいか想像がつくと思う。
私がプログラマになれるとしたらブラック系企業しか思いつかない。
-その２
元々頭が悪いので脳鍛効果のあることを探してみたりする。
漢字と系統を同じくする文字の書き取り練習はかなり脳鍛効果がありそう。
西夏文字やハングル文字、甲骨文字などの文字の練習をしていると頭に血が集まってる感じがする。
頭全体が熱くなる感じである。
漢字を思い出して書くというのは脳鍛効果があるのだが、私にとって未知の文字であるという効果が加わってるからだろう。
脳は未知のものや新しいものに出会うと活発に働くらしい。
未知の字の練習は、未知かつ思い出しでダブル効果というわけだ。
うーん出版とかしないかな。
脳を鍛える世界の文字練習ドリル。
西夏文字とかキリル文字とかタングート文字とかアラビア文字とか日本人にとってなじみの薄い文字を収録した脳鍛用ドリル。
これをやってると脳全体がアツアツになります。
普通の脳鍛と違い前頭葉以外もバランス良く訓練される最良の書。
ボケ防止にもぴったり。
とかそんなフレーズで。
まあ文字の練習は図書館で本を借りてきて済ますんですけどね。
久しぶりに加古川図書館に行ったら、本棚の本がまるっきりかわってるのでびっくりした。
最後に訪れたのがかなり前なので正確にいは思い出せないけれどかなり本の入れ替えがあったのかも。
論語とかプラトンとかの大判本が無数に並んでいるけど読んでみようかな？
*2011/6/1
バグ取りが終わらないよ何回やっても終わらない。
printf連打も試してみたけど、バグ元がやっぱり見つからない。
コードチェッカーがあれば楽にバグも見つかるけど何回やっても何回やってもバグが見つからない。
http://dsr.nii.ac.jp/rarebook/08/
古代国家における情報インフラの整備のうち最も重要なものは文字や文法の策定だと思う。
独自文化や独自言語、歴史の話は国家を守る最後の砦。
*2011/5/31
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302
この問題はただ解くだけなら高校生でも考えつく問題、4流プログラマである私でも自力で考えつく程度の問題。
これを制限時間内にコードが答えを出すようにするとなると難しいし、もっと先を見て他の回答者のように高速に動くコードを書くとなると相当難しい。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
この問題は考え方は簡単なんだよな。
一枚ずつシートを追加していき面積と周長を単純に足していく。
シートを足すとき、今まで置いたシートと新しく追加したシートの共通集合、要は2枚だけを選んだとき重なっている部分があればこれを求めこの集合をＡ1とする。
Ａ１の部分の面積と周長は重複して数えられているので、Ａ１だけ周長と面積を引く。
すると今度はＡ１内で2枚以上重なっている部分が余分に引かれてしまうので、今度はＡ1内での共通集合部分を足しこの共通集合部分をＡ２とする。
すると今度はＡ２の中で重なっている部分が生まれるので共通集合の部分の面積を足す。
Ａiと一般化する。
Ａｉはiが奇数なら面積と周長を引き、偶数なら足す。
そして共通集合がなくなるまでこれを繰り返す。
四角形を表す頂点データを扱う関数を一つ作れば後は再帰でいけるのでそんなに難しくはない。
ここでめんどくさいのが2枚のシートが重なっているかを求める時どの部分が重なっているかを求める処理かな。
なんか場合分けがめんどくさそう。
*2011/5/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302
この問題の本質は、一回質問するたびにＹｅｓが帰ってきたら次は質問ＡをＮｏなら質問Ｂを。
というＹｅｓＮｏに合わせた木を求め、木の深さが最小になる木を求めなくてはいけない点。
正答率に騙されてはいけない意外な難問だな。
Ｙｏｕｔｕｂｅに知の回廊という大学の作った教養番組が。
どうせ面接行っても学歴職歴で自動的に落とされるし、この番組のコンプでもしようかな？
でも放送大学の文科系よりレベルは低いような感じもする。
でも生の感覚という点では知の回廊の方が上な感じかな。
放送大学の数学関系は視聴者に理解させる気がないだろうというおいてけぼり番組が多い。
文系番組は非常に面白いのが多かったという記憶があるな。
知の回廊の理系はまあよさそうな感じ。
文系は少しへたそう。
知の回廊は連載でない単発動画なので内容が高度な方に行かない感じもするな。
常識レベルを浅く広く知れるだけ？
って感じかな。
まあ最近プログラムの勉強も行き詰ったし無駄に勉強しとこ。
*2011/5/29
Ｙｏｕｔｕｂｅに上がっている第１回 ペーパーマン最強決定戦 IN 秋葉原UDX 決勝
アナウンス付きで上級者プレイが見れるというのは面白い発想。
他のゲームでも解説付き上級者対戦プレイ動画はあるけど、解説がうまいきいてて気持ちがいい。
こういうのってはやったりするんだろうか？
*2011/5/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300
うーん？
この問題は再帰下降構文解析を書いて、解析した構文をmapに代入する必要があるな？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1301
独力で解くなら少し複雑なベクトルの問題を解かないとだめだな。
公式をみてカンニングしようかしら？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302
質問をすることはＹｅｓＮｏの2分木をたどることと同じ。
積集合は順番を無視して解けるので、質問の選び方は2^11通りと少ないので力ずくで求めても何とかなりそう。
賢い方法は後日考えるとしてとりあえず力づくで解こうっと。
良く考えたらこの問題yes Noにあわせて次の質問を選択するという問題があるんだな。
2＾11では追いつかない。
というか今日はプログラムをやる気が起きない、全然コードが進まない。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1303
うーん？思いつかない。
そもそも問題分が長くて読む気がしない。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1304
縦横斜めに３つ感染源があるマスは感染する。
縦横斜めで感染してる場所が２つか３つなら感染は持続する。
それ以外なら感染が無くなる。
車は感染源にはいることができない。
車の移動が先。
*2011/5/28
なんか最近プログラムの勉強がはかどらない。
会津大学オンラインジャッジの問題に挑戦してもまったく意欲がわかないし不正解を喰らいまくる。
残ってる問題は英語を読み解けなくて解けないか、苦手問題、解けないのもまあ当然なんだけど。
それでも最近の意欲のでなささはちょっとおかしい。
実務や大学で研究してる人のプログラムに比べたら高校生の遊びか大学1年レベルの問題だろうから解けない問題がある＝私のレベルがまだまだ低い。
ということなんだろう、
平均程度の実力があればどの問題ももう少し楽々解けるはずだし意欲だってわくはず。
なんか会津大学の問題もたくさん解いたけどたいして実力アップした気がしない。
会津大学の問題を8割も解けばまあ大学1年レベルのプログラムに到達できたとは思うんだけど？
*2011/5/27
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
この問題を解くコードを書いてみたのだけど。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0508StringWithRings4.txt
問題を解くコード。
ＢＣＣではコンパイルが通りｎが60程度まではきちんと制限時間内に解を出せて動くのだけど、サーバ側のＧＣＣでコンパイルエラーがでて全く通らない。
コンパイルエラーになる原因がなんだかよくわからない。
しょうがないので他の問題に手を出す。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0204
この問題、どう解こうかな？
ＵＦＯの数が少ないので時間切れを怖がる心配はなさそう。
レーザーは最悪100回打てば計算が終わるのでたいしたことはないと。
するとロジックだな。
優先順位付きキューにレーザー砲までの距離を基準に敵機体を代入。
1分進める。
全ての敵機を1分の距離だけ進め、位置を更新し優先順位付きキューに再代入する。
キューを一つずつ読み込んでいき、レーザー法の有効最短射程Ｒ以下になった機体を代入からはずしその数をカウントする。
この時点で再代入が0になれば計算を終了する。
初めに見つけた距離Ｒ以上のＵＦＯのうち一番近いＵＦＯ Ｕ１を選択する。
Ｕ１を通る直線式Ｌ1を求める。
Ｌ１からの距離がユーフォーの半径内で、Ｌ１と垂直な直線で平面を区切った時Ｕ１と同じ側にあるＵＦＯを撃墜可能か調べる。
撃墜できたなら、その番号を控えておき、再代入からはずす。
これを全てのＵＦＯがいなくなるまで繰り返す。
うーんこの問題？
半径500のＵＦＯが(-30,-40)にいて、レーザーの有効半径が20で(30,40)の座標にいるＵＦＯを撃墜した時、-30、-40のＵＦＯは同時撃墜対象になるのか？
という問題があるな。
*2011/5/27
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542
この問題最初は深さ優先探索でタイムリミッド。
深さ優先を高速化させても駄目。
なので部屋の認証レベルを優先にした優先順序付き幅優先探索でアセプト。
大体深さ優先よりも幅優先の方が高速に動くなあ。
*2011/5/25
分からない問題は掲示板任せにして飛ばして次の問題。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542
この問題の解き方は？
うーん？
うん？
深さ優先探索、初めてはいった部屋なら今まで通ってきた部屋と今いる部屋のうちで一番認証レベルの高い部屋の値で訪れた部屋の認証レベルを書き換える。
2度目以降に訪れたなら、1度目よりも低い認証レベルで訪れた時、部屋の認証レベルを部屋の認証レベルか今まで通ってきた部屋の最高認証レベルの高い方に書き換える、1度目よりも高いなら書き換えず部屋にも入らない。
後は、できた認証レベルを連想配列に貯め込んでカウント。
連想配列のカウント回数を小さい方から一つ大きい方へ足す操作を繰り返す。
これで、事務所1の認証は全てカウントできる。
これを事務所2でも行う。
後は事務所1の値が決まった時の事務所2の連想配列の最小値を探せばいいと。
のだが、計算量が不安になるなこの問題。
深さ優先探索が最悪の場合や意地悪なデータを用意されて上手く機能しない可能性を排除できない。
計算量の安定という面で不安があるから、僕の考えた方法でアセプトできたとしても自己採点60点くらいだな。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0542AuthenticationLevel.txt
とりあえずmap<int,int>にある認証レベルがあれば何部屋までいけるかを取得するところまで成功。
ええとここからどうやって、最小の認証レベルの計を求めるかだよな。
最小の計？
*2011/5/25
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
この問題を解くコードを記述。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0508StringWithRings.txt
何か無駄に長いコードになっている気がする？
後よくわからないコンパイルエラーがでてる。
何が悪いんだろ？
*2011/5/23
再帰下降構文解析というものを学習する。
状態遷移マシーンを再帰にすることで構文解析を可能とする手法のことらしい。
考え方は分かる。
が自分で構文解析を作れと言われたらかなり悩むだろうな。
*2011/5/22
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0534
この問題をどう解こう？
計算量を抑えるのが基本だな。
大事なのは消えた部分の上下しか新しく消える部分にならないという点。
キャラクターの列の両端に番兵を用意して、上と下を読み込んでいくマシーンを作るというのが着眼点。
また、消えた部分の上下がひっつくことによる消去以外起きない。
という制限も問題を簡単にしている。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0534chain.txt
高速に動作するコードで一発合格。
まあ会津大学の問題集の中では簡単な問題だから当たり前だけど。
*2011/5/22
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0210
リンク先問題が解けない。
うーん、マップの状態をセルオートマトンに見立てて解こうとしてるんだけど何かが悪いらしく不正解を喰らってしまう。
何が悪いんだろ？
多分、中にいる人をＡさんＢさんＣさんとした場合。
Ａさんが動きＡさんがいた場所にＢさんがきて、Ｂさんがいた場所にＣさんが来るような場合を考えないとだめなんだなきっと。
ってこの場合どう解けばいいんだろう？
ＡさんＢさんＣさんＤさんがうロボロスのように周回に入った場合も解けないとだめだよな？
以下不正解になるコード。
#include<stdio.h>
#include<map>
void setMap(int w,int h);
int dxs[]={1,0,-1,0};
int dys[]={0,-1,0,1};
std::map<char,int> mukis;
int main()
{
mukis['E']=0;
mukis['N']=1;
mukis['W']=2;
mukis['S']=3;
mukis[0]='E';
mukis[1]='N';
mukis[2]='W';
mukis[3]='S';
int w,h;
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
setMap(w,h);
scanf("%d %d",&w,&h);
}
}
void setMap(int w,int h){
char meiro[31][31];
char nextmeiro[31][31];
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf(" %c",&meiro[i][j]);
nextmeiro[i][j]=meiro[i][j];
}
}
//迷路のサイズが小さいことを利用してセルオートマトンとして処理する。
char t;
int count;
int muki;
int nx,ny;
for(int k=0;k<181;k++)
{
count=0;
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
t=meiro[i][j];
if(t=='E' || t=='N' || t=='W' || t=='S')
{
muki=mukis[t]+4;
//printf("<%d>",muki);
count++;
for(int l=-1;l<3;l++)
{
nx=dxs[(muki+l)%4]+j;
ny=dys[(muki+l)%4]+i;
if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
if(meiro[ny][nx]=='.' || meiro[ny][nx]=='X')
{
//printf("/%d/",(muki+l)%4);
meiro[i][j]=mukis[(muki+l)%4];
break;
}
}
}
}
}
if(count==0){
printf("%d\n",k);
return ;
}
//printf("\n");
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
//printf("%c",meiro[i][j]);
//nextmeiro[i][j]=meiro[i][j];
}
//printf("\n");
}
int t;
//scanf("%d",&t);
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
if(meiro[i][j]=='.' || meiro[i][j]=='X')
{
for(int l=0;l<4;l++)
{
nx=dxs[l]+j;
ny=dys[l]+i;
if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
if(mukis.find(meiro[ny][nx])!=mukis.end())
{
if((mukis[meiro[ny][nx]]+2)%4==l)
{
if(meiro[i][j]=='X')
{
nextmeiro[ny][nx]='.';
}else
{
nextmeiro[i][j]=meiro[ny][nx];
nextmeiro[ny][nx]='.';
break;
}
}
}
}
}
}
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
//printf("%c",nextmeiro[i][j]);
meiro[i][j]=nextmeiro[i][j];
}
//printf("\n");
}
}
printf("NA\n");
}
*2011/5/20 22：09分
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0520
↑この問題を解くコードを記述↓
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0520LightestMobile.txt
自信が持てないな。
テストデータを用意するのも大変な問題だし。
*2011/5/20
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0520
この問題難しす。
それでも解けるようにするために問題が簡単になるような条件はある。
モビールはどの部分を見ても釣り合うという条件がそれだな。
モビールを木構造で表す。
木構造でたどるには再帰がいいよな。
モビールの両側がおもりなら、最小の重さのおもりをそのモビールにぶら下げる。
その重さを呼び出し元の関数に返す。
どちらかが下のモビールにつながっていて反対がおもりなら、モビールを先に再帰し戻り値を求め、帰ってきた重さを使って片方のおもりの重さを決める。
モビールの両端が両方モビールにつながっている場合が難しい。
モビールの先がどうつながっているか分からない以上重さの基準値が無いという点が難しい。
ある特定のモビールが与えられたなら連立方程式を解いていけば答えは出る。
一般の場合を解くのは難しそう。
うーん？
この問題を解くには両方モビールの場合を解決しないといけない？
両方のモジュールから帰ってきた重さの戻り値を比較する。
同じならそのまま返す。
両方の戻り値の比を定数倍して最小公倍数を求め、それをここまでのモビールの重さの計とし上に返す？
*2011/5/20
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0215
この問題。
添え字のポカミスに気付かず信じられない回数不正解を喰らう。
解いてみたら単なる教科書通りのメモ化探索。
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
void setMap(int w,int h);
void saiki(int deep,int no,int oldNo);
struct point{
int x,y;
};
int g[5][1001];
point ps[5][1001],sp,ep;
int counts[5];
int ans;
int fNo;
int main(){
int w,h;
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
setMap(w,h);
scanf("%d %d",&w,&h);
}
}
void setMap(int w,int h){
char t;
for(int i=0;i<5;i++) counts[i]=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf(" %c",&t);
if('0'<t && t<'6'){
t-='1';
ps[t][counts[t]].x=j;
ps[t][counts[t]].y=i;
counts[t]++;
}else if(t=='S'){
sp.x=j;
sp.y=i;
}else if(t=='G'){
ep.x=j;
ep.y=i;
}
}
}
int typeC=0;
for(int i=0;i<5;i++){
if(counts[i]>0) typeC++;
}
//printf("\n");
if(typeC<4){
printf("NA\n");
return ;
}
int mymax=1000000000;
ans=mymax;
int tt;
for(int k=0;k<5;k++){
for(int i=0;i<4;i++){
tt=(k+i+1)%5;
for(int j=0;j<counts[tt];j++){
g[i][j]=mymax;
}
//printf("%d<%d>",counts[tt],tt);
}
//printf(")\n");
//printf("%d\n",k);
saiki(0,(k+1)%5,k);
//printf("\n\n");
}
printf("%d %d\n",fNo,ans);
}
void saiki(int deep,int no,int oldNo){
int t;
//printf("(no=%d ono=%d)\n",no,oldNo);
if(deep==0){
for(int i=0;i<counts[no];i++){
g[deep][i]=abs(ps[no][i].x-sp.x)+abs(ps[no][i].y-sp.y);
}
saiki(deep+1,(no+1)%5,no%5);
}else if(deep==4){
for(int i=0;i<counts[oldNo];i++){
t=abs(ps[oldNo][i].x-ep.x)+abs(ps[oldNo][i].y-ep.y)+g[deep-1][i];
if(ans>t){
ans=t;
fNo=no+1;
}
}
}else{
for(int i=0;i<counts[oldNo];i++){
for(int j=0;j<counts[no];j++){
t=abs(ps[oldNo][i].x-ps[no][j].x)+abs(ps[oldNo][i].y-ps[no][j].y)+g[deep-1][i];
//printf("<%d %d>",abs(ps[oldNo][i].x-ps[no][j].x)+abs(ps[oldNo][i].y-ps[no][j].y),g[deep-1][i]);
g[deep][j]=g[deep][j]>t?t:g[deep][j];
}
}
saiki(deep+1,(no+1)%5,no%5);
}
}
*2011/5/18
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0214
この問題の解き方。
四角形を一つずつ読み込みAとする。
読み込み済みの四角形の集合をBとしその要素をBiと表す。
Aの辺がBiの線分を挟んで交点を持つか接するならAとBiは同じグループに属する。
AとBiを点としグラフでつなげる。
後はグラフ上の問題に帰着される。
が接するを記述するのがめんどくさいなあこの問題。
接するか交点を持つか共有点を持つか、四角形の中に四角形があるかを記述してみたらこんなに長くなった、、、
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0214AutumnalIllumination2.txt
これだけ長いと記述ミスが心配になるので投稿は後日に使用。
今提出しても多分記述ミスで不正解を喰らう。
17時14分
畑のジャガイモ育ってるなあ、6月の収穫が楽しみ。
トマトもたくさん植えたしソラマメと玉ねぎの収穫もできるし、キュウリにピーマンにナスビにパプリカと基本は押さえた。
今年の収穫楽しみだなあ。
来年はトウモロコシ植えよ。
*2011/5/15
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2214
この問題はかなり難しい。
問題文に誤りがあり座標は100000までありワープホールは1000個まである。
普通この手の問題はメモ化探索で解くのだけど普通のメモ化では100000*100000マスを計算することになってしまう。
ということは単純なメモ化でなく一段レベルの高い計算方法が必要になる。
何か規則的で多項式時間で終わる計算法が必要だと思うのだけど、ワープホールが恣意的に散らばってるので規則的な計算法は使えないような気がする。
この問題はNP困難問題のような気がする、だとすると計算量は落ちない。
何か賢い方法があるのかもしれないけれど私には規則的な取り扱いを思いつかない。
どうしてもわからなかったので答えをカンニング。
カンニングしてもよくわからない。
http://rsujskf.blog32.fc2.com/?mode=m&no=1474
うーん？
まずワープホールがない場合のスタートからゴールまでの組み合わせ数を計算する？
これは比較的簡単に答えが出そう。
次にスタートからワープホール、ワープホールからワープホール、ワープホールからゴール。
による組み合わせ数の低下を順に引いていくということかな？
なんだか難しそうだ。
とりあえず座標が小さい場合を解く、検証用に作ったコードだけUP。
良い考え方ないかな？
#include<stdio.h>
#include<set>
#include<map>
unsigned int memo[200003];
unsigned int memo2[200003];
void setMap(int n,int m,int k);
struct point{
int sx,sy;
int ex,ey;
bool operator<(const point p)const{
if(sy!=p.sy) return sy<p.sy;
if(sx!=p.sx) return sx<p.sx;
return false;
}
};
int main(){
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
while(n!=0 || m!=0 || k!=0){
setMap(n,m,k);
scanf("%d %d %d",&n,&m,&k);
}
}
void setMap(int n,int m,int k)
{
unsigned int mod=1000000007;
for(int i=0;i<=n+m;i++){
memo[i]=0;
memo2[i]=0;
}
memo[1]=1;
point p;
point outPoint;
std::set<point> warp;
std::map<point,unsigned int> warpOut;
std::set<point>::iterator it;
for(int i=0;i<k;i++){
scanf("%d %d %d %d",&p.sx,&p.sy,&p.ex,&p.ey);
warp.insert(p);
outPoint.sx=p.ex;
outPoint.sy=p.ey;
warpOut[outPoint]=0;
}
for(int i=2;i<=n+m;i++){
for(int j=1;j<i;j++){
p.sx=i-j;
p.sy=j;
if(p.sx>n || p.sy>m ){
continue;
}
if(warpOut.find(p)!=warpOut.end()){
memo2[j]=warpOut[p];
}else{
memo2[j]=0;
}
it=warp.find(p);
if(it==warp.end()){
//ワープポイントでないなら
memo2[j]+=(memo[j-1]+memo[j])%mod;
memo2[j]%=mod;
//printf("%d ",memo2[j]);
}else{
p=(*it);
if(p.ex>n || p.ey>m) continue;
outPoint.sx=p.ex;
outPoint.sy=p.ey;
warpOut[outPoint]+=(memo[j]+memo[j-1]+memo2[j])%mod;
warpOut[outPoint]%=mod;
memo2[j]=0;
//printf("%d ",memo[j]+memo[j-1]+memo2[j]);
}
}
//printf("\n");
for(int j=1;j<=i;j++){
if(j>m || i-j>n) continue;
memo[j]=memo2[j];
}
}
printf("%d\n",memo[m]);
}
*2011/5/14
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0234
む。
この問題は難しいというよりもめんどくさいに分類されるな。
実務での複雑で長い加工手順に比べたら単純なんだろうけど、手軽に挑戦する練習問題としてはちょっとめんどくさい。
左右に移動してから下に移動するわけだが。
移動は
右にm1マス移動してから左にm2マス移動し右m3マス戻る。
左にn1マス移動してから右にn2マス移動して左にn3マス戻る。
n1,n2,n3,,m1,m2,m3は0～ｗまでの自然数。
という移動を考慮してから下移動しないと解けない場合があるからだ。
このめんどくさいのを何も考えずコード化するとかなりコードが長くなる。
しかし、正答者のコードはかなり短い。
つまり何か賢い考え方があってコードを短くできるだろうということだ。
工夫も何もないコードを書いては勉強にならない気がする。
コードを短くする工夫のあるコードを考えつくまでこの問題は保留だな。
PSPのスパロボZ２破界編を遊ぶ。
SRポイントをねらわなければ、精神コマンド込み敵味方戦力比1対10といったところか、小学生もクリアできることを考えたバランスとしてはこんなものか。
レッドショルダーがえらく弱いんだが、あれだけ最強部隊最強部隊とシナリオ中でちりばめてたんだからHP7000くらい合ってもいいよな？
俺はあまりゲームに詳しくないけれどゲームって色々な種類に分けられるな。
エーコンやスパロボみたいに最高難易度にあげてもサクサク進める楽勝ゲーム。
地球防衛軍3やハードな難易度SLGやガチオンライン対戦やリアル系のフライトシミュレータみたいに何も考えずに突撃したり正面から挑むと順当な消耗戦の結果味方部隊が全滅するゲーム。
知恵と工夫で何度か挑戦してクリアするゲームと、誰でもサクサク爽快感をもってクリアできるゲーム。
どちらも面白いんだよな。
スパロボやって思った、ボトムズ作られた時代にはクラスターボムなんてなかった何だよな。
AT部隊はクラスターボム一発で全滅だし、ガンダムのビームライフルは戦車の分厚い装甲に対して内部に熱を伝えることができないので戦車を撃破できず、効いたとしても光学センサーによる高い命中率で戦う戦車には砲撃戦でもまず勝てない。
人型ロボというのは難儀な代物だなあ。
*2011/5/11
僕は4流プログラマとしての実力しかない。
工学系の機械設計のような数万を超える関係式を設定するような問題は手も出ないし
バイオ系のような間接的なデータに高度な数学を適用して細胞内部でおこったことや状態を推測するような高度なコードはかけない。
昨今のゲームのすさまじい作りこみを見ると心が折れるほどの能力差を感じる。
事務系や業務系として働くにはそういった方面の知識がない。
金融商品を作ってるような天才や秀才とも縁がない。
数千種類程度の属性を持つデータを分析して役立つ統計データ解析をするような才能もない。
漫画だったら駄目駄目づくしでもそれでも何か大切なものを持ってたりするものだが、現実ではそんなものついぞ目にかかったこともない、。
業界経験もない。
4流プログラマとしてどう働く道を見つけるか？
ということなのである。
とりあえず勉強用の今日書きかけのコード。
今日はプログラム書いてても調子が悪いな、全く進まない。
木構造の応用はとても広いらしいが私木構造はかなり苦手なのである。
木構造はメモリを動的に確保したり削除したり、グラフのように最初にどかっとデータを準備するような単純さがないところが苦手だな。
簡単な問題なのにえらく時間がかかってしまった。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1217
#include<stdio.h>
#include<vector>
#include<string>
#include<map>
void setTree(int x,int y);
struct node{
node* parentNode;//親のノード
std::string name;
std::vector<node> childNodes;//子のノード
};
int main()
{
int x,y;
char t;
scanf("%d %d",&x,&y);
while(x!=0 || y!=0){
scanf("%c",&t);
setTree(x,y);
scanf("%d %d",&x,&y);
}
}
void setTree(int x,int y){
char space[100];
int sCount=0,k,oldCount=0,t;
node topNode;
topNode.parentNode=&topNode;
node nAdd;
node* n1=&topNode;
std::map<std::string,node*> nodes;
for(int i=0;i<x;i++){
scanf("%[^\n]%*c",space);
k=sCount=0;
while(space[sCount]==' '){
sCount++;
}
while(space[k+sCount]!='\0'){
space[k]=space[k+sCount];
k++;
}
space[k]='\0';
nAdd.name=space;
t=sCount-oldCount;
if(t<0){
for(int i=0;i<-t+1;i++){
n1=n1->parentNode;
}
}else if(t==0){
n1=n1->parentNode;
}
nAdd.parentNode=n1;
n1->childNodes.push_back(nAdd);
n1=&n1->childNodes[n1->childNodes.size()-1];
nodes[n1->name]=n1;
oldCount=sCount;
}
char name1[50],name2[50];
char tempCom[20];
std::string command;
for(int i=0;i<y;i++){
scanf("%s",name1);
command="";
for(int j=0;j<4;j++){
scanf("%s",tempCom);
command+=tempCom;
}
scanf(" %[^.]",name2);
char t;
scanf("%c",&t);
if(command=="isachildof"){
if(nodes[name1]->parentNode->name==name2){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="istheparentof"){
if(nodes[name1]->name==nodes[name2]->parentNode->name){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isasiblingof"){
if(nodes[name1]->parentNode->name==nodes[name2]->parentNode->name){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isadescendantof"){
n1=nodes[name1];
bool ok=false;
while(n1!=&topNode){
n1=n1->parentNode;
if(n1->name==name2) ok=true;
}
if(ok==true){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isanancestorof"){
n1=nodes[name2];
bool ok=false;
while(n1!=&topNode){
n1=n1->parentNode;
if(n1->name==name1) ok=true;
}
if(ok==true){
printf("True\n");
}else{
printf("False\n");
}
}
}
}
堀江伸一
兵庫県加古川市加古川町南備後79-16
*2011/6/14
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2195
この問題は難しいかも。
c=4*10^(2B)-4*10^B+s^2 sは任意の自然数。
cが自然数の2乗であるようなＳを探す。
Ｓが条件を満たす時
a=(1-2*10^(B)+√c)/2
b=(1+√(4a^2-4a(1-2*10^B)+1))/2
と定まるa,bが指定の桁数Ａ、Ｂの桁数となるなら答えは正しい。
うーん、計算式が少しだけ複雑なので計算ミスが不安になるなこの問題。
*2011/6/13
http://www.youtube.com/watch?v=-G2-Omy9FgU&NR=1
室内で動いてる人がいるかどうかを知ることができる新しい防犯システム。
なんか蝙蝠の超音波みたいですごいな。
もっと進化したら、どこらへんを動いてるかもわかるようになるのかも？
ニューロネットとの融合とか敵を探すためのロボ･歩兵用装備とか色々妄想してしまう。
しかしこれ動いている人がいるということを識別するだけで誰が動いている窯では判別できないよな。
個人識別用の別のシステムと併用しないとだめなことを考えると組織でしか使えない気がする？
http://www.youtube.com/watch?v=R2fyLl7KZXM&feature=related
ぶは。
量子コンピュータの授業が無料で上がってる。
俺には一生縁がない話しだけれど好奇心で見てみるか。
*2011/6/2
自分的プログラム勉強予定。
その１
会津大学オンラインジャッジの問題集をもう少しだけ解く。
これが終わると基礎的なアルゴリズムの勉強はひとまず終わりと定義(あくまで基礎、大学でやってるような高度な数学や工学と融合したアルゴリズムからみたら会津台の問題で身につくアルゴリズムは多分低レベル)。
書籍を読んで色々なプログラムの分野について学ぶ。
アプリ制作講座等を一通り書いてある通りに記述しコンパイルし微改造したりして、アプリを作るということそのものに慣れる。
普通のプログラマなら１０代の時から何年もかけてレベルアップしてその上に大学の知識を身につけているわけだよな。
複雑で高度な抽象的構造物を考えることに慣れた頭、それが普通のプログラマだよな。
いい年してから本気でプログラムを学ぼうとしている私はこの圧倒的な学習時間の差を埋めないといけない。
ただ埋めるだけでなく、私の場合若い時に高度な抽象的思考の訓練や物理や工学的発想といった訓練を受けていないというハンデがある。
この恐ろしく大きな溝を飛び越えないとプログラマに慣れないわけだよな。
社会にでてからは単純肉体労働以外ついたことがないので、世の中のことや業務的な発想というものは全くできない頭ときている。
すると、私が飛び越えなくてはいけない溝はどれだけ大きいか想像がつくと思う。
私がプログラマになれるとしたらブラック系企業しか思いつかない。
-その２
元々頭が悪いので脳鍛効果のあることを探してみたりする。
漢字と系統を同じくする文字の書き取り練習はかなり脳鍛効果がありそう。
西夏文字やハングル文字、甲骨文字などの文字の練習をしていると頭に血が集まってる感じがする。
頭全体が熱くなる感じである。
漢字を思い出して書くというのは脳鍛効果があるのだが、私にとって未知の文字であるという効果が加わってるからだろう。
脳は未知のものや新しいものに出会うと活発に働くらしい。
未知の字の練習は、未知かつ思い出しでダブル効果というわけだ。
うーん出版とかしないかな。
脳を鍛える世界の文字練習ドリル。
西夏文字とかキリル文字とかタングート文字とかアラビア文字とか日本人にとってなじみの薄い文字を収録した脳鍛用ドリル。
これをやってると脳全体がアツアツになります。
普通の脳鍛と違い前頭葉以外もバランス良く訓練される最良の書。
ボケ防止にもぴったり。
とかそんなフレーズで。
まあ文字の練習は図書館で本を借りてきて済ますんですけどね。
久しぶりに加古川図書館に行ったら、本棚の本がまるっきりかわってるのでびっくりした。
最後に訪れたのがかなり前なので正確にいは思い出せないけれどかなり本の入れ替えがあったのかも。
論語とかプラトンとかの大判本が無数に並んでいるけど読んでみようかな？
*2011/6/1
バグ取りが終わらないよ何回やっても終わらない。
printf連打も試してみたけど、バグ元がやっぱり見つからない。
コードチェッカーがあれば楽にバグも見つかるけど何回やっても何回やってもバグが見つからない。
http://dsr.nii.ac.jp/rarebook/08/
古代国家における情報インフラの整備のうち最も重要なものは文字や文法の策定だと思う。
独自文化や独自言語、歴史の話は国家を守る最後の砦。
*2011/5/31
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302
この問題はただ解くだけなら高校生でも考えつく問題、4流プログラマである私でも自力で考えつく程度の問題。
これを制限時間内にコードが答えを出すようにするとなると難しいし、もっと先を見て他の回答者のように高速に動くコードを書くとなると相当難しい。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
この問題は考え方は簡単なんだよな。
一枚ずつシートを追加していき面積と周長を単純に足していく。
シートを足すとき、今まで置いたシートと新しく追加したシートの共通集合、要は2枚だけを選んだとき重なっている部分があればこれを求めこの集合をＡ1とする。
Ａ１の部分の面積と周長は重複して数えられているので、Ａ１だけ周長と面積を引く。
すると今度はＡ１内で2枚以上重なっている部分が余分に引かれてしまうので、今度はＡ1内での共通集合部分を足しこの共通集合部分をＡ２とする。
すると今度はＡ２の中で重なっている部分が生まれるので共通集合の部分の面積を足す。
Ａiと一般化する。
Ａｉはiが奇数なら面積と周長を引き、偶数なら足す。
そして共通集合がなくなるまでこれを繰り返す。
四角形を表す頂点データを扱う関数を一つ作れば後は再帰でいけるのでそんなに難しくはない。
ここでめんどくさいのが2枚のシートが重なっているかを求める時どの部分が重なっているかを求める処理かな。
なんか場合分けがめんどくさそう。
*2011/5/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302
この問題の本質は、一回質問するたびにＹｅｓが帰ってきたら次は質問ＡをＮｏなら質問Ｂを。
というＹｅｓＮｏに合わせた木を求め、木の深さが最小になる木を求めなくてはいけない点。
正答率に騙されてはいけない意外な難問だな。
Ｙｏｕｔｕｂｅに知の回廊という大学の作った教養番組が。
どうせ面接行っても学歴職歴で自動的に落とされるし、この番組のコンプでもしようかな？
でも放送大学の文科系よりレベルは低いような感じもする。
でも生の感覚という点では知の回廊の方が上な感じかな。
放送大学の数学関系は視聴者に理解させる気がないだろうというおいてけぼり番組が多い。
文系番組は非常に面白いのが多かったという記憶があるな。
知の回廊の理系はまあよさそうな感じ。
文系は少しへたそう。
知の回廊は連載でない単発動画なので内容が高度な方に行かない感じもするな。
常識レベルを浅く広く知れるだけ？
って感じかな。
まあ最近プログラムの勉強も行き詰ったし無駄に勉強しとこ。
*2011/5/29
Ｙｏｕｔｕｂｅに上がっている第１回 ペーパーマン最強決定戦 IN 秋葉原UDX 決勝
アナウンス付きで上級者プレイが見れるというのは面白い発想。
他のゲームでも解説付き上級者対戦プレイ動画はあるけど、解説がうまいきいてて気持ちがいい。
こういうのってはやったりするんだろうか？
*2011/5/29
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1300
うーん？
この問題は再帰下降構文解析を書いて、解析した構文をmapに代入する必要があるな？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1301
独力で解くなら少し複雑なベクトルの問題を解かないとだめだな。
公式をみてカンニングしようかしら？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302
質問をすることはＹｅｓＮｏの2分木をたどることと同じ。
積集合は順番を無視して解けるので、質問の選び方は2^11通りと少ないので力ずくで求めても何とかなりそう。
賢い方法は後日考えるとしてとりあえず力づくで解こうっと。
良く考えたらこの問題yes Noにあわせて次の質問を選択するという問題があるんだな。
2＾11では追いつかない。
というか今日はプログラムをやる気が起きない、全然コードが進まない。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1303
うーん？思いつかない。
そもそも問題分が長くて読む気がしない。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1304
縦横斜めに３つ感染源があるマスは感染する。
縦横斜めで感染してる場所が２つか３つなら感染は持続する。
それ以外なら感染が無くなる。
車は感染源にはいることができない。
車の移動が先。
*2011/5/28
なんか最近プログラムの勉強がはかどらない。
会津大学オンラインジャッジの問題に挑戦してもまったく意欲がわかないし不正解を喰らいまくる。
残ってる問題は英語を読み解けなくて解けないか、苦手問題、解けないのもまあ当然なんだけど。
それでも最近の意欲のでなささはちょっとおかしい。
実務や大学で研究してる人のプログラムに比べたら高校生の遊びか大学1年レベルの問題だろうから解けない問題がある＝私のレベルがまだまだ低い。
ということなんだろう、
平均程度の実力があればどの問題ももう少し楽々解けるはずだし意欲だってわくはず。
なんか会津大学の問題もたくさん解いたけどたいして実力アップした気がしない。
会津大学の問題を8割も解けばまあ大学1年レベルのプログラムに到達できたとは思うんだけど？
*2011/5/27
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
この問題を解くコードを書いてみたのだけど。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0508StringWithRings4.txt
問題を解くコード。
ＢＣＣではコンパイルが通りｎが60程度まではきちんと制限時間内に解を出せて動くのだけど、サーバ側のＧＣＣでコンパイルエラーがでて全く通らない。
コンパイルエラーになる原因がなんだかよくわからない。
しょうがないので他の問題に手を出す。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0204
この問題、どう解こうかな？
ＵＦＯの数が少ないので時間切れを怖がる心配はなさそう。
レーザーは最悪100回打てば計算が終わるのでたいしたことはないと。
するとロジックだな。
優先順位付きキューにレーザー砲までの距離を基準に敵機体を代入。
1分進める。
全ての敵機を1分の距離だけ進め、位置を更新し優先順位付きキューに再代入する。
キューを一つずつ読み込んでいき、レーザー法の有効最短射程Ｒ以下になった機体を代入からはずしその数をカウントする。
この時点で再代入が0になれば計算を終了する。
初めに見つけた距離Ｒ以上のＵＦＯのうち一番近いＵＦＯ Ｕ１を選択する。
Ｕ１を通る直線式Ｌ1を求める。
Ｌ１からの距離がユーフォーの半径内で、Ｌ１と垂直な直線で平面を区切った時Ｕ１と同じ側にあるＵＦＯを撃墜可能か調べる。
撃墜できたなら、その番号を控えておき、再代入からはずす。
これを全てのＵＦＯがいなくなるまで繰り返す。
うーんこの問題？
半径500のＵＦＯが(-30,-40)にいて、レーザーの有効半径が20で(30,40)の座標にいるＵＦＯを撃墜した時、-30、-40のＵＦＯは同時撃墜対象になるのか？
という問題があるな。
*2011/5/27
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542
この問題最初は深さ優先探索でタイムリミッド。
深さ優先を高速化させても駄目。
なので部屋の認証レベルを優先にした優先順序付き幅優先探索でアセプト。
大体深さ優先よりも幅優先の方が高速に動くなあ。
*2011/5/25
分からない問題は掲示板任せにして飛ばして次の問題。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0542
この問題の解き方は？
うーん？
うん？
深さ優先探索、初めてはいった部屋なら今まで通ってきた部屋と今いる部屋のうちで一番認証レベルの高い部屋の値で訪れた部屋の認証レベルを書き換える。
2度目以降に訪れたなら、1度目よりも低い認証レベルで訪れた時、部屋の認証レベルを部屋の認証レベルか今まで通ってきた部屋の最高認証レベルの高い方に書き換える、1度目よりも高いなら書き換えず部屋にも入らない。
後は、できた認証レベルを連想配列に貯め込んでカウント。
連想配列のカウント回数を小さい方から一つ大きい方へ足す操作を繰り返す。
これで、事務所1の認証は全てカウントできる。
これを事務所2でも行う。
後は事務所1の値が決まった時の事務所2の連想配列の最小値を探せばいいと。
のだが、計算量が不安になるなこの問題。
深さ優先探索が最悪の場合や意地悪なデータを用意されて上手く機能しない可能性を排除できない。
計算量の安定という面で不安があるから、僕の考えた方法でアセプトできたとしても自己採点60点くらいだな。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0542AuthenticationLevel.txt
とりあえずmap<int,int>にある認証レベルがあれば何部屋までいけるかを取得するところまで成功。
ええとここからどうやって、最小の認証レベルの計を求めるかだよな。
最小の計？
*2011/5/25
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
この問題を解くコードを記述。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0508StringWithRings.txt
何か無駄に長いコードになっている気がする？
後よくわからないコンパイルエラーがでてる。
何が悪いんだろ？
*2011/5/23
再帰下降構文解析というものを学習する。
状態遷移マシーンを再帰にすることで構文解析を可能とする手法のことらしい。
考え方は分かる。
が自分で構文解析を作れと言われたらかなり悩むだろうな。
*2011/5/22
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0534
この問題をどう解こう？
計算量を抑えるのが基本だな。
大事なのは消えた部分の上下しか新しく消える部分にならないという点。
キャラクターの列の両端に番兵を用意して、上と下を読み込んでいくマシーンを作るというのが着眼点。
また、消えた部分の上下がひっつくことによる消去以外起きない。
という制限も問題を簡単にしている。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0534chain.txt
高速に動作するコードで一発合格。
まあ会津大学の問題集の中では簡単な問題だから当たり前だけど。
*2011/5/22
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0210
リンク先問題が解けない。
うーん、マップの状態をセルオートマトンに見立てて解こうとしてるんだけど何かが悪いらしく不正解を喰らってしまう。
何が悪いんだろ？
多分、中にいる人をＡさんＢさんＣさんとした場合。
Ａさんが動きＡさんがいた場所にＢさんがきて、Ｂさんがいた場所にＣさんが来るような場合を考えないとだめなんだなきっと。
ってこの場合どう解けばいいんだろう？
ＡさんＢさんＣさんＤさんがうロボロスのように周回に入った場合も解けないとだめだよな？
以下不正解になるコード。
#include<stdio.h>
#include<map>
void setMap(int w,int h);
int dxs[]={1,0,-1,0};
int dys[]={0,-1,0,1};
std::map<char,int> mukis;
int main()
{
mukis['E']=0;
mukis['N']=1;
mukis['W']=2;
mukis['S']=3;
mukis[0]='E';
mukis[1]='N';
mukis[2]='W';
mukis[3]='S';
int w,h;
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
setMap(w,h);
scanf("%d %d",&w,&h);
}
}
void setMap(int w,int h){
char meiro[31][31];
char nextmeiro[31][31];
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf(" %c",&meiro[i][j]);
nextmeiro[i][j]=meiro[i][j];
}
}
//迷路のサイズが小さいことを利用してセルオートマトンとして処理する。
char t;
int count;
int muki;
int nx,ny;
for(int k=0;k<181;k++)
{
count=0;
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
t=meiro[i][j];
if(t=='E' || t=='N' || t=='W' || t=='S')
{
muki=mukis[t]+4;
//printf("<%d>",muki);
count++;
for(int l=-1;l<3;l++)
{
nx=dxs[(muki+l)%4]+j;
ny=dys[(muki+l)%4]+i;
if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
if(meiro[ny][nx]=='.' || meiro[ny][nx]=='X')
{
//printf("/%d/",(muki+l)%4);
meiro[i][j]=mukis[(muki+l)%4];
break;
}
}
}
}
}
if(count==0){
printf("%d\n",k);
return ;
}
//printf("\n");
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
//printf("%c",meiro[i][j]);
//nextmeiro[i][j]=meiro[i][j];
}
//printf("\n");
}
int t;
//scanf("%d",&t);
for(int i=0;i<h;i++)
{
for(int j=0;j<w;j++)
{
if(meiro[i][j]=='.' || meiro[i][j]=='X')
{
for(int l=0;l<4;l++)
{
nx=dxs[l]+j;
ny=dys[l]+i;
if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
if(mukis.find(meiro[ny][nx])!=mukis.end())
{
if((mukis[meiro[ny][nx]]+2)%4==l)
{
if(meiro[i][j]=='X')
{
nextmeiro[ny][nx]='.';
}else
{
nextmeiro[i][j]=meiro[ny][nx];
nextmeiro[ny][nx]='.';
break;
}
}
}
}
}
}
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
//printf("%c",nextmeiro[i][j]);
meiro[i][j]=nextmeiro[i][j];
}
//printf("\n");
}
}
printf("NA\n");
}
*2011/5/20 22：09分
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0520
↑この問題を解くコードを記述↓
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0520LightestMobile.txt
自信が持てないな。
テストデータを用意するのも大変な問題だし。
*2011/5/20
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0520
この問題難しす。
それでも解けるようにするために問題が簡単になるような条件はある。
モビールはどの部分を見ても釣り合うという条件がそれだな。
モビールを木構造で表す。
木構造でたどるには再帰がいいよな。
モビールの両側がおもりなら、最小の重さのおもりをそのモビールにぶら下げる。
その重さを呼び出し元の関数に返す。
どちらかが下のモビールにつながっていて反対がおもりなら、モビールを先に再帰し戻り値を求め、帰ってきた重さを使って片方のおもりの重さを決める。
モビールの両端が両方モビールにつながっている場合が難しい。
モビールの先がどうつながっているか分からない以上重さの基準値が無いという点が難しい。
ある特定のモビールが与えられたなら連立方程式を解いていけば答えは出る。
一般の場合を解くのは難しそう。
うーん？
この問題を解くには両方モビールの場合を解決しないといけない？
両方のモジュールから帰ってきた重さの戻り値を比較する。
同じならそのまま返す。
両方の戻り値の比を定数倍して最小公倍数を求め、それをここまでのモビールの重さの計とし上に返す？
*2011/5/20
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0215
この問題。
添え字のポカミスに気付かず信じられない回数不正解を喰らう。
解いてみたら単なる教科書通りのメモ化探索。
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
void setMap(int w,int h);
void saiki(int deep,int no,int oldNo);
struct point{
int x,y;
};
int g[5][1001];
point ps[5][1001],sp,ep;
int counts[5];
int ans;
int fNo;
int main(){
int w,h;
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
setMap(w,h);
scanf("%d %d",&w,&h);
}
}
void setMap(int w,int h){
char t;
for(int i=0;i<5;i++) counts[i]=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf(" %c",&t);
if('0'<t && t<'6'){
t-='1';
ps[t][counts[t]].x=j;
ps[t][counts[t]].y=i;
counts[t]++;
}else if(t=='S'){
sp.x=j;
sp.y=i;
}else if(t=='G'){
ep.x=j;
ep.y=i;
}
}
}
int typeC=0;
for(int i=0;i<5;i++){
if(counts[i]>0) typeC++;
}
//printf("\n");
if(typeC<4){
printf("NA\n");
return ;
}
int mymax=1000000000;
ans=mymax;
int tt;
for(int k=0;k<5;k++){
for(int i=0;i<4;i++){
tt=(k+i+1)%5;
for(int j=0;j<counts[tt];j++){
g[i][j]=mymax;
}
//printf("%d<%d>",counts[tt],tt);
}
//printf(")\n");
//printf("%d\n",k);
saiki(0,(k+1)%5,k);
//printf("\n\n");
}
printf("%d %d\n",fNo,ans);
}
void saiki(int deep,int no,int oldNo){
int t;
//printf("(no=%d ono=%d)\n",no,oldNo);
if(deep==0){
for(int i=0;i<counts[no];i++){
g[deep][i]=abs(ps[no][i].x-sp.x)+abs(ps[no][i].y-sp.y);
}
saiki(deep+1,(no+1)%5,no%5);
}else if(deep==4){
for(int i=0;i<counts[oldNo];i++){
t=abs(ps[oldNo][i].x-ep.x)+abs(ps[oldNo][i].y-ep.y)+g[deep-1][i];
if(ans>t){
ans=t;
fNo=no+1;
}
}
}else{
for(int i=0;i<counts[oldNo];i++){
for(int j=0;j<counts[no];j++){
t=abs(ps[oldNo][i].x-ps[no][j].x)+abs(ps[oldNo][i].y-ps[no][j].y)+g[deep-1][i];
//printf("<%d %d>",abs(ps[oldNo][i].x-ps[no][j].x)+abs(ps[oldNo][i].y-ps[no][j].y),g[deep-1][i]);
g[deep][j]=g[deep][j]>t?t:g[deep][j];
}
}
saiki(deep+1,(no+1)%5,no%5);
}
}
*2011/5/18
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0214
この問題の解き方。
四角形を一つずつ読み込みAとする。
読み込み済みの四角形の集合をBとしその要素をBiと表す。
Aの辺がBiの線分を挟んで交点を持つか接するならAとBiは同じグループに属する。
AとBiを点としグラフでつなげる。
後はグラフ上の問題に帰着される。
が接するを記述するのがめんどくさいなあこの問題。
接するか交点を持つか共有点を持つか、四角形の中に四角形があるかを記述してみたらこんなに長くなった、、、
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=2011%E5%B9%B45%E6%9C%88&file=0214AutumnalIllumination2.txt
これだけ長いと記述ミスが心配になるので投稿は後日に使用。
今提出しても多分記述ミスで不正解を喰らう。
17時14分
畑のジャガイモ育ってるなあ、6月の収穫が楽しみ。
トマトもたくさん植えたしソラマメと玉ねぎの収穫もできるし、キュウリにピーマンにナスビにパプリカと基本は押さえた。
今年の収穫楽しみだなあ。
来年はトウモロコシ植えよ。
*2011/5/15
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2214
この問題はかなり難しい。
問題文に誤りがあり座標は100000までありワープホールは1000個まである。
普通この手の問題はメモ化探索で解くのだけど普通のメモ化では100000*100000マスを計算することになってしまう。
ということは単純なメモ化でなく一段レベルの高い計算方法が必要になる。
何か規則的で多項式時間で終わる計算法が必要だと思うのだけど、ワープホールが恣意的に散らばってるので規則的な計算法は使えないような気がする。
この問題はNP困難問題のような気がする、だとすると計算量は落ちない。
何か賢い方法があるのかもしれないけれど私には規則的な取り扱いを思いつかない。
どうしてもわからなかったので答えをカンニング。
カンニングしてもよくわからない。
http://rsujskf.blog32.fc2.com/?mode=m&no=1474
うーん？
まずワープホールがない場合のスタートからゴールまでの組み合わせ数を計算する？
これは比較的簡単に答えが出そう。
次にスタートからワープホール、ワープホールからワープホール、ワープホールからゴール。
による組み合わせ数の低下を順に引いていくということかな？
なんだか難しそうだ。
とりあえず座標が小さい場合を解く、検証用に作ったコードだけUP。
良い考え方ないかな？
#include<stdio.h>
#include<set>
#include<map>
unsigned int memo[200003];
unsigned int memo2[200003];
void setMap(int n,int m,int k);
struct point{
int sx,sy;
int ex,ey;
bool operator<(const point p)const{
if(sy!=p.sy) return sy<p.sy;
if(sx!=p.sx) return sx<p.sx;
return false;
}
};
int main(){
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
while(n!=0 || m!=0 || k!=0){
setMap(n,m,k);
scanf("%d %d %d",&n,&m,&k);
}
}
void setMap(int n,int m,int k)
{
unsigned int mod=1000000007;
for(int i=0;i<=n+m;i++){
memo[i]=0;
memo2[i]=0;
}
memo[1]=1;
point p;
point outPoint;
std::set<point> warp;
std::map<point,unsigned int> warpOut;
std::set<point>::iterator it;
for(int i=0;i<k;i++){
scanf("%d %d %d %d",&p.sx,&p.sy,&p.ex,&p.ey);
warp.insert(p);
outPoint.sx=p.ex;
outPoint.sy=p.ey;
warpOut[outPoint]=0;
}
for(int i=2;i<=n+m;i++){
for(int j=1;j<i;j++){
p.sx=i-j;
p.sy=j;
if(p.sx>n || p.sy>m ){
continue;
}
if(warpOut.find(p)!=warpOut.end()){
memo2[j]=warpOut[p];
}else{
memo2[j]=0;
}
it=warp.find(p);
if(it==warp.end()){
//ワープポイントでないなら
memo2[j]+=(memo[j-1]+memo[j])%mod;
memo2[j]%=mod;
//printf("%d ",memo2[j]);
}else{
p=(*it);
if(p.ex>n || p.ey>m) continue;
outPoint.sx=p.ex;
outPoint.sy=p.ey;
warpOut[outPoint]+=(memo[j]+memo[j-1]+memo2[j])%mod;
warpOut[outPoint]%=mod;
memo2[j]=0;
//printf("%d ",memo[j]+memo[j-1]+memo2[j]);
}
}
//printf("\n");
for(int j=1;j<=i;j++){
if(j>m || i-j>n) continue;
memo[j]=memo2[j];
}
}
printf("%d\n",memo[m]);
}
*2011/5/14
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0234
む。
この問題は難しいというよりもめんどくさいに分類されるな。
実務での複雑で長い加工手順に比べたら単純なんだろうけど、手軽に挑戦する練習問題としてはちょっとめんどくさい。
左右に移動してから下に移動するわけだが。
移動は
右にm1マス移動してから左にm2マス移動し右m3マス戻る。
左にn1マス移動してから右にn2マス移動して左にn3マス戻る。
n1,n2,n3,,m1,m2,m3は0～ｗまでの自然数。
という移動を考慮してから下移動しないと解けない場合があるからだ。
このめんどくさいのを何も考えずコード化するとかなりコードが長くなる。
しかし、正答者のコードはかなり短い。
つまり何か賢い考え方があってコードを短くできるだろうということだ。
工夫も何もないコードを書いては勉強にならない気がする。
コードを短くする工夫のあるコードを考えつくまでこの問題は保留だな。
PSPのスパロボZ２破界編を遊ぶ。
SRポイントをねらわなければ、精神コマンド込み敵味方戦力比1対10といったところか、小学生もクリアできることを考えたバランスとしてはこんなものか。
レッドショルダーがえらく弱いんだが、あれだけ最強部隊最強部隊とシナリオ中でちりばめてたんだからHP7000くらい合ってもいいよな？
俺はあまりゲームに詳しくないけれどゲームって色々な種類に分けられるな。
エーコンやスパロボみたいに最高難易度にあげてもサクサク進める楽勝ゲーム。
地球防衛軍3やハードな難易度SLGやガチオンライン対戦やリアル系のフライトシミュレータみたいに何も考えずに突撃したり正面から挑むと順当な消耗戦の結果味方部隊が全滅するゲーム。
知恵と工夫で何度か挑戦してクリアするゲームと、誰でもサクサク爽快感をもってクリアできるゲーム。
どちらも面白いんだよな。
スパロボやって思った、ボトムズ作られた時代にはクラスターボムなんてなかった何だよな。
AT部隊はクラスターボム一発で全滅だし、ガンダムのビームライフルは戦車の分厚い装甲に対して内部に熱を伝えることができないので戦車を撃破できず、効いたとしても光学センサーによる高い命中率で戦う戦車には砲撃戦でもまず勝てない。
人型ロボというのは難儀な代物だなあ。
*2011/5/11
僕は4流プログラマとしての実力しかない。
工学系の機械設計のような数万を超える関係式を設定するような問題は手も出ないし
バイオ系のような間接的なデータに高度な数学を適用して細胞内部でおこったことや状態を推測するような高度なコードはかけない。
昨今のゲームのすさまじい作りこみを見ると心が折れるほどの能力差を感じる。
事務系や業務系として働くにはそういった方面の知識がない。
金融商品を作ってるような天才や秀才とも縁がない。
数千種類程度の属性を持つデータを分析して役立つ統計データ解析をするような才能もない。
漫画だったら駄目駄目づくしでもそれでも何か大切なものを持ってたりするものだが、現実ではそんなものついぞ目にかかったこともない、。
業界経験もない。
4流プログラマとしてどう働く道を見つけるか？
ということなのである。
とりあえず勉強用の今日書きかけのコード。
今日はプログラム書いてても調子が悪いな、全く進まない。
木構造の応用はとても広いらしいが私木構造はかなり苦手なのである。
木構造はメモリを動的に確保したり削除したり、グラフのように最初にどかっとデータを準備するような単純さがないところが苦手だな。
簡単な問題なのにえらく時間がかかってしまった。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1217
#include<stdio.h>
#include<vector>
#include<string>
#include<map>
void setTree(int x,int y);
struct node{
node* parentNode;//親のノード
std::string name;
std::vector<node> childNodes;//子のノード
};
int main()
{
int x,y;
char t;
scanf("%d %d",&x,&y);
while(x!=0 || y!=0){
scanf("%c",&t);
setTree(x,y);
scanf("%d %d",&x,&y);
}
}
void setTree(int x,int y){
char space[100];
int sCount=0,k,oldCount=0,t;
node topNode;
topNode.parentNode=&topNode;
node nAdd;
node* n1=&topNode;
std::map<std::string,node*> nodes;
for(int i=0;i<x;i++){
scanf("%[^\n]%*c",space);
k=sCount=0;
while(space[sCount]==' '){
sCount++;
}
while(space[k+sCount]!='\0'){
space[k]=space[k+sCount];
k++;
}
space[k]='\0';
nAdd.name=space;
t=sCount-oldCount;
if(t<0){
for(int i=0;i<-t+1;i++){
n1=n1->parentNode;
}
}else if(t==0){
n1=n1->parentNode;
}
nAdd.parentNode=n1;
n1->childNodes.push_back(nAdd);
n1=&n1->childNodes[n1->childNodes.size()-1];
nodes[n1->name]=n1;
oldCount=sCount;
}
char name1[50],name2[50];
char tempCom[20];
std::string command;
for(int i=0;i<y;i++){
scanf("%s",name1);
command="";
for(int j=0;j<4;j++){
scanf("%s",tempCom);
command+=tempCom;
}
scanf(" %[^.]",name2);
char t;
scanf("%c",&t);
if(command=="isachildof"){
if(nodes[name1]->parentNode->name==name2){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="istheparentof"){
if(nodes[name1]->name==nodes[name2]->parentNode->name){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isasiblingof"){
if(nodes[name1]->parentNode->name==nodes[name2]->parentNode->name){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isadescendantof"){
n1=nodes[name1];
bool ok=false;
while(n1!=&topNode){
n1=n1->parentNode;
if(n1->name==name2) ok=true;
}
if(ok==true){
printf("True\n");
}else{
printf("False\n");
}
}else if(command=="isanancestorof"){
n1=nodes[name2];
bool ok=false;
while(n1!=&topNode){
n1=n1->parentNode;
if(n1->name==name1) ok=true;
}
if(ok==true){
printf("True\n");
}else{
printf("False\n");
}
}
}
}
