堀江伸一
兵庫県加古川市加古川町南備後79-16
2011/6/1
バグ取りが終わらないよ何回やっても終わらない。
printf連打も試してみたけど、バグ元がやっぱり見つからない。
コードチェッカーがあれば楽にバグも見つかるけど何回やっても何回やってもバグが見つからない。
2011/5/31
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
この問題は考え方は簡単なんだよな。
一枚ずつシートを追加していき面積と周長を単純に足していく。
シートを足すとき、今まで置いたシートと新しく追加したシートの共通集合、要は2枚だけを選んだとき重なっている部分があればこれを求めこの集合をＡ1とする。
Ａ１の部分の面積と周長は重複して数えられているので、Ａ１だけ周長と面積を引く。
すると今度はＡ１内で2枚以上重なっている部分が余分に引かれてしまうので、今度はＡ1内での共通集合部分を足しこの共通集合部分をＡ２とする。
すると今度はＡ２の中で重なっている部分が生まれるので共通集合の部分の面積を足す。
Ａiと一般化する。
Ａｉはiが奇数なら面積と周長を引き、偶数なら足す。
そして共通集合がなくなるまでこれを繰り返す。
四角形を表す頂点データを扱う関数を一つ作れば後は再帰でいけるのでそんなに難しくはない。
ここでめんどくさいのが2枚のシートが重なっているかを求める時どの部分が重なっているかを求める処理かな。
なんか場合分けがめんどくさそう。
2011/5/29
Ｙｏｕｔｕｂｅに知の回廊という大学の作った教養番組が。
どうせ面接行っても学歴職歴で自動的に落とされるし、この番組のコンプでもしようかな？
でも放送大学の文科系よりレベルは低いような感じもする。
でも生の感覚という点では知の回廊の方が上な感じかな。
放送大学の数学関系は視聴者に理解させる気がないだろうというおいてけぼり番組が多い。
文系番組は非常に面白いのが多かったという記憶があるな。
知の回廊の理系はまあよさそうな感じ。
文系は少しへたそう。
知の回廊は連載でない単発動画なので内容が高度な方に行かない感じもするな。
常識レベルを浅く広く知れるだけ？
って感じかな。
まあ最近プログラムの勉強も行き詰ったし無駄に勉強しとこ。
2011/5/29
Ｙｏｕｔｕｂｅに上がっている第１回 ペーパーマン最強決定戦 IN 秋葉原UDX 決勝
アナウンス付きで上級者プレイが見れるというのは面白い発想。
他のゲームでも解説付き上級者対戦プレイ動画はあるけど、解説がうまいきいてて気持ちがいい。
こういうのってはやったりするんだろうか？
2011/5/29
2011/5/28
なんか最近プログラムの勉強がはかどらない。
会津大学オンラインジャッジの問題に挑戦してもまったく意欲がわかないし不正解を喰らいまくる。
残ってる問題は英語を読み解けなくて解けないか、苦手問題、解けないのもまあ当然なんだけど。
それでも最近の意欲のでなささはちょっとおかしい。
実務や大学で研究してる人のプログラムに比べたら高校生の遊びか大学1年レベルの問題だろうから解けない問題がある＝私のレベルがまだまだ低い。
ということなんだろう、
平均程度の実力があればどの問題ももう少し楽々解けるはずだし意欲だってわくはず。
なんか会津大学の問題もたくさん解いたけどたいして実力アップした気がしない。
会津大学の問題を8割も解けばまあ大学1年レベルのプログラムに到達できたとは思うんだけど？
2011/5/27
するとロジックだな。
優先順位付きキューにレーザー砲までの距離を基準に敵機体を代入。
1分進める。
全ての敵機を1分の距離だけ進め、位置を更新し優先順位付きキューに再代入する。
キューを一つずつ読み込んでいき、レーザー法の有効最短射程Ｒ以下になった機体を代入からはずしその数をカウントする。
この時点で再代入が0になれば計算を終了する。
初めに見つけた距離Ｒ以上のＵＦＯのうち一番近いＵＦＯ Ｕ１を選択する。
Ｕ１を通る直線式Ｌ1を求める。
Ｌ１からの距離がユーフォーの半径内で、Ｌ１と垂直な直線で平面を区切った時Ｕ１と同じ側にあるＵＦＯを撃墜可能か調べる。
撃墜できたなら、その番号を控えておき、再代入からはずす。
これを全てのＵＦＯがいなくなるまで繰り返す。
うーんこの問題？
半径500のＵＦＯが(-30,-40)にいて、レーザーの有効半径が20で(30,40)の座標にいるＵＦＯを撃墜した時、-30、-40のＵＦＯは同時撃墜対象になるのか？
という問題があるな。
2011/5/27
2011/5/25
後は、できた認証レベルを連想配列に貯め込んでカウント。
連想配列のカウント回数を小さい方から一つ大きい方へ足す操作を繰り返す。
これで、事務所1の認証は全てカウントできる。
これを事務所2でも行う。
後は事務所1の値が決まった時の事務所2の連想配列の最小値を探せばいいと。
のだが、計算量が不安になるなこの問題。
深さ優先探索が最悪の場合や意地悪なデータを用意されて上手く機能しない可能性を排除できない。
計算量の安定という面で不安があるから、僕の考えた方法でアセプトできたとしても自己採点60点くらいだな。
2011/5/25
2011/5/23
再帰下降構文解析というものを学習する。
状態遷移マシーンを再帰にすることで構文解析を可能とする手法のことらしい。
考え方は分かる。
が自分で構文解析を作れと言われたらかなり悩むだろうな。
2011/5/22
2011/5/22
以下不正解になるコード。
<stdio.h>
<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分
2011/5/20
モビールを木構造で表す。
木構造でたどるには再帰がいいよな。
モビールの両側がおもりなら、最小の重さのおもりをそのモビールにぶら下げる。
その重さを呼び出し元の関数に返す。
どちらかが下のモビールにつながっていて反対がおもりなら、モビールを先に再帰し戻り値を求め、帰ってきた重さを使って片方のおもりの重さを決める。
モビールの両端が両方モビールにつながっている場合が難しい。
モビールの先がどうつながっているか分からない以上重さの基準値が無いという点が難しい。
ある特定のモビールが与えられたなら連立方程式を解いていけば答えは出る。
一般の場合を解くのは難しそう。
うーん？
この問題を解くには両方モビールの場合を解決しないといけない？
両方のモジュールから帰ってきた重さの戻り値を比較する。
同じならそのまま返す。
両方の戻り値の比を定数倍して最小公倍数を求め、それをここまでのモビールの重さの計とし上に返す？
2011/5/20
<stdio.h>
<math.h>
<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
Aの辺がBiの線分を挟んで交点を持つか接するならAとBiは同じグループに属する。
AとBiを点としグラフでつなげる。
後はグラフ上の問題に帰着される。
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。
良い考え方ないかな？
<stdio.h>
<set>
<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流プログラマとしてどう働く道を見つけるか？
ということなのである。
とりあえず勉強用の今日書きかけのコード。
今日はプログラム書いてても調子が悪いな、全く進まない。
木構造の応用はとても広いらしいが私木構造はかなり苦手なのである。
木構造はメモリを動的に確保したり削除したり、グラフのように最初にどかっとデータを準備するような単純さがないところが苦手だな。
<stdio.h>
<vector>
<string>
<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");
}
}
}
}
