堀江伸一
兵庫県加古川市加古川町南備後79-16
2011/7/1
４流プログラマなりに作りたいと思っているゲーム４種類。
主にアクションやレース系。
考え方の底が浅いのが特徴。
1
ゲームの時間ごとの状態変化をＳ0、Ｓ1，，，，Ｓｎ。
ユーザーの操作の種類、f,gとしuを自然数とする。
Si+1=g(Si)
Si+1=f(Si,Si-1,,,Si-u)
で次の状態が決まるゲーム。
ｆはｆが連続で呼ばれた回数によって渡されるＳｉの数が異なる。
もしユーザの操作が
gffggfffg
とするなら。
S1=g(S0)
S2=f(S1)
S3=f(S2,S1)
S4=g(S3)
S5=g(S4)
S6=f(S5)
S7=f(S6,S5)
S8=f(S6,S5,S4)
のようにｆは連続で選択されると、過去の状態も計算に入れてゲームの次の状態を決定する。
ｆを連続で選択するとだんだん結果が複雑に分岐するが、その結果は高スコアと大失敗が複雑に入り乱れる。
ｇを選択すると単純に次の状態を予測できるが凡庸な結果になりやすい。
こういう関数を多数用意し、関数同士の間で相互関係ｆの後にｇを選択するのとｇの後にｇを選択するのでは結果が異なるように作りたい。
２
過去の状態でなく操作の連続を基準にした関数でゲームの状態を決定する場合。
前と同じで関数ｆが連続で呼ばれるとｆは過去の操作によって同じ操作でも結果が違ってくるゲーム。
ユーザの操作をＡ0、Ａ1，，，Ａｎとする。
X1=f(X0,A1)
X2=f(X0,A2,A1)
X3=f(Ｘ0,A2,A1,A0)
のように連続でｆが呼ばれると、ｆの結果は前の操作の影響を受ける。
もしくはゲームのステートが前の状態や何回前の影響を受けて決まる。
すこし出鱈目な定義だけど分かりやすい例としてはレースゲームの連続カーブなどがあげられる。
連続カーブに入る前の車の速度、位置、コーナへの新入角等をＸ0とする。
２連続コーナーでは、２つ目のコーナーの曲がり方は最初のコーナーの曲がり方Ａ0の影響を受ける。
最初のコーナーをどう走るかで次のコーナーへのはいり方や走り方が変化するという当たり前の話。
最初のコーナーの走り方が
Ａ0={a0,a1,,,an}
であり
Ａ1={b1,b2,,,bn}
２つ目の走り方がだとすると、Ａ0とＡ1の組み合わせ表ができるが、これはどのbiを選択してもajの選択によってbiの結果は違ってくるという組み合わせの妙が生まれ多様な選択肢が生み出される。
この構造はレースに限らずアクションゲームにも応用できるはずであり、こういう過去にとった選択が次の状態を決定づけるゲームというものを作りたい。
2011/7/7
3
ゲームの状態をx,aこれを変化させる操作をf,gとして
f(x)がパラメータの変化が特定の値に収束し。
g(x)はパラメータの変化が特定の値の組から遠ざかる。
少し一般化して幾つかあるパラメータに対して、ｆ１、ｆ２、、、ｆｎとｎ個の操作を定義し、この各々の操作に対しパラメータの幾つかが特定の値に収束するか特定の値から遠ざかるという組み合わせのあるゲームを適当に作りたい。
4
個人的な好みとしては触って気持ちいいゲームならなんでもいいなあ。
マリオギャラクシーとか着地後の操作にラグがあっていらっとするし、方向転換の微調整が利かずいらっとくる。
こういういらっとくる部分がなく、次々画面に現れる敵を爽快な操作でラグなくスムーズにクリアできる。
そういうゲームだったら俺は全力で買うだろうな。
ゲーム全体にある種の流れやリズムがあってその流れによどみがなく、ゲームの状態や結果を変化させる分岐点が無数に存在し、この分岐点をなんのいらつきかんもラグもなくやってきてスムーズに選択し続けることができるゲーム。
具体的にいえば敵の下を滑って通る、上をジャンプして通る、弾き飛ばすという選択
肢が提示されてどれかをなんのいらつき感もなく選択したら次の選択までスムーズに進む。
間違った選択をとればペナルティが来る。
基本に忠実なゲームでいいんだよな。
スムーズでいらっかんがなくてスイッチを入れたら短時間でばーっと遊べるゲーム、遊びたいなあ。
2011/7/1
うーん、やっぱ３流高卒の私の考えるゲームはワンパターン？
ゲームの状態Ｘtと操作a,bに対して
Xt+1=g(Xt,a)
Xt+1=g(Xt,Xt-1,,,,b)
で決まるような２種類の操作のあるゲーム。
もしくは
のようにユニットの状態などをＺiとしこれに対する操作ｆとｇでＺｊに変更できるときの組み合わせがある。
ｆは先の予測が難しくｇは先の予測が簡単。
そして状態Ziとゲームの状態Ｃｉ(ｆを選ぶとＣの変化が早くないりＧを選ぶとＣの変動が遅くなる)からゲーム内での評価や得点などが決まるとする。
ｇを行うと、先の予測が簡単だが低得点に、ｆを行うと先の予測が難しいが高得点になる可能性がある。
操作ｆやｇによってＣの状態が変化していく。
こういうゲームを作れたらいつまでも飽きないゲームになるんじゃないかと思ったりはするんだけど？うーん、３流高卒なので具体化ができないんだよな。
2011/6/30
2011/6/21
<set>
<stdio.h>
<queue>
struct root{
unsigned int size,rootMemo[4],last;//到達したリングを1bitで管理
bool operator<(const root& r)const{
if(size!=r.size) return size<r.size;
if(last!=r.last) return last<r.last;
if(rootMemo[0]!=r.rootMemo[0]) return rootMemo[0]<r.rootMemo[0];
if(rootMemo[1]!=r.rootMemo[1]) return rootMemo[1]<r.rootMemo[1];
if(rootMemo[2]!=r.rootMemo[2]) return rootMemo[2]<r.rootMemo[2];
if(rootMemo[3]!=r.rootMemo[3]) return rootMemo[3]<r.rootMemo[3];
return false;
}
};
int one=1;
bool addOK(const root& r,int no){
return ((r.rootMemo[no/32] & one<<(no %32))==0);
}
void addRoot(root& r,int no){
r.rootMemo[no/32]|=(one<<(no %32));
r.size++;
r.last=no;
}
void dellRoot(root& r,int no){
r.rootMemo[no/32] &= ~(one<<(no%32));
r.size--;
}
void nodeSearch(int rings[101][101],int nodeSize[101],int gTypes[101],int no,int gType){
int size=nodeSize[no];
gTypes[no]=gType;
for(int i=0;i<size;i++){
if(gTypes[rings[no][i]]==-1){
nodeSearch(rings,nodeSize,gTypes,rings[no][i],gType);
}
}
}
void setData(int n){
int rings[101][101];
int nodeSize[101];
int gTypes[101],gNodeMins[101],gTypeCount=0;
int a,b;
for(int i=0;i<101;i++){
nodeSize[i]=0;
gTypes[i]=-1;
gNodeMins[i]=101;
}
for(int i=0;i<n;i++){
scanf("%d %d",&a,&b);
a--;
b--;
rings[a][nodeSize[a]]=b;
rings[b][nodeSize[b]]=a;
nodeSize[a]++;
nodeSize[b]++;
}
for(int i=0;i<101;i++){
if(gTypes[i]==-1 && nodeSize[i]>0){
nodeSearch(rings,nodeSize,gTypes,i,gTypeCount);
gTypeCount++;
}
}
for(int i=0;i<101;i++){
if(nodeSize[i]>0) gNodeMins[gTypes[i]]=gNodeMins[gTypes[i]]>nodeSize[i]?nodeSize[i]:gNodeMins[gTypes[i]];
}
root r;
r.size=0;
for(int i=0;i<4;i++) r.rootMemo[i]=0;
std::set<root> allRoots;
std::priority_queue<root> qRoots;
for(int i=0;i<101;i++){
if(nodeSize[i]==0) continue;
if(gNodeMins[gTypes[i]]==nodeSize[i]){
addRoot(r,i);
allRoots.insert(r);
qRoots.push(r);
dellRoot(r,i);
}
}
int size,last,t;
while(qRoots.empty()==false){
r=qRoots.top();
qRoots.pop();
last=r.last;
size=nodeSize[last];
for(int i=0;i<size;i++){
t=rings[last][i];
if(addOK(r,t)){
addRoot(r,t);
if(allRoots.find(r)==allRoots.end()){
allRoots.insert(r);
qRoots.push(r);
}
dellRoot(r,t);
}
}
}
std::set<root>::iterator it=allRoots.end();
it--;
printf("%d\n",(*it).size);
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setData(n);
scanf("%d",&n);
}
}
2011/6/15
ドラえもん風の小さい子供向け小説アイディア。
知性のある本
自分の属しているジャンルの本を探している人が通るとその人を感知して自然に手を取らせる本。
読者の心を読みとり、それに合わせて内容を変えていく本。
小説なら波乱万丈、専門書なら適切な内容を返す。
めくるたびに2度と同じ内容が現れない本。
携帯版迷いの森
半径数十メートルにいる人間の方向感覚を惑わせるきりを発生する迷惑アイテム。
2011/6/14
a=(1-2*10^(B)+√c)/2
b=(1+√(4a^2-4a(1-2*10^B)+1))/2
と定まるa,bが指定の桁数Ａ、Ｂの桁数となるなら答えは正しい。
うーん、計算式が少しだけ複雑なので式変形のミスが不安になるなこの問題。
後計算量が1000万回に達するのですこしだけ計算時間が足らない。
2011/6/13
http://www.youtube.com/watch?v=-G2-Omy9FgU&NR=1
室内で動いてる人がいるかどうかを知ることができる新しい防犯システム。
なんか蝙蝠の超音波みたいですごいな。
もっと進化したら、どこらへんを動いてるかもわかるようになるのかも？
ニューロネットとの融合とか敵を探すためのロボ･歩兵用装備とか色々妄想してしまう。
しかしこれ動いている人がいるということを識別するだけで誰が動いている窯では判別できないよな。
個人識別用の別のシステムと併用しないとだめなことを考えると組織でしか使えない気がする？
2011/6/2
自分的プログラム勉強予定。
その１
会津大学オンラインジャッジの問題集をもう少しだけ解く。
これが終わると基礎的なアルゴリズムの勉強はひとまず終わりと定義(あくまで基礎、大学でやってるような高度な数学や工学と融合したアルゴリズムからみたら会津台の問題で身につくアルゴリズムは多分低レベル)。
書籍を読んで色々なプログラムの分野について学ぶ。
アプリ制作講座等を一通り書いてある通りに記述しコンパイルし微改造したりして、アプリを作るということそのものに慣れる。
普通のプログラマなら１０代の時から何年もかけてレベルアップしてその上に大学の知識を身につけているわけだよな。
複雑で高度な抽象的構造物を考えることに慣れた頭、それが普通のプログラマだよな。
いい年してから本気でプログラムを学ぼうとしている私はこの圧倒的な学習時間の差を埋めないといけない。
ただ埋めるだけでなく、私の場合若い時に高度な抽象的思考の訓練や物理や工学的発想といった訓練を受けていないというハンデがある。
この恐ろしく大きな溝を飛び越えないとプログラマに慣れないわけだよな。
社会にでてからは単純肉体労働以外ついたことがないので、世の中のことや業務的な発想というものは全くできない頭ときている。
すると、私が飛び越えなくてはいけない溝はどれだけ大きいか想像がつくと思う。
私がプログラマになれるとしたらブラック系企業しか思いつかない。
元々頭が悪いので脳鍛効果のあることを探してみたりする。
漢字と系統を同じくする文字の書き取り練習はかなり脳鍛効果がありそう。
西夏文字やハングル文字、甲骨文字などの文字の練習をしていると頭に血が集まってる感じがする。
頭全体が熱くなる感じである。
漢字を思い出して書くというのは脳鍛効果があるのだが、私にとって未知の文字であるという効果が加わってるからだろう。
脳は未知のものや新しいものに出会うと活発に働くらしい。
未知の字の練習は、未知かつ思い出しでダブル効果というわけだ。
うーん出版とかしないかな。
脳を鍛える世界の文字練習ドリル。
西夏文字とかキリル文字とかタングート文字とかアラビア文字とか日本人にとってなじみの薄い文字を収録した脳鍛用ドリル。
これをやってると脳全体がアツアツになります。
普通の脳鍛と違い前頭葉以外もバランス良く訓練される最良の書。
ボケ防止にもぴったり。
とかそんなフレーズで。
まあ文字の練習は図書館で本を借りてきて済ますんですけどね。
久しぶりに加古川図書館に行ったら、本棚の本がまるっきりかわってるのでびっくりした。
最後に訪れたのがかなり前なので正確にいは思い出せないけれどかなり本の入れ替えがあったのかも。
論語とかプラトンとかの大判本が無数に並んでいるけど読んでみようかな？
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");
}
}
}
}
最終更新：2011年07月07日 16:32
