「2011年5月」の編集履歴（バックアップ）一覧はこちら
「2011年5月」(2011/07/07 (木) 16:32:54) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
堀江伸一
兵庫県加古川市加古川町南備後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)はパラメータの変化が特定の値の組から遠ざかる。
少し一般化して幾つかあるパラメータに対して、ｆ１、ｆ２、、、ｆｎとｎ個の操作を定義し、この各々の操作に対しパラメータの幾つかが特定の値に収束するか特定の値から遠ざかるという組み合わせのあるゲームを適当に作りたい。
*2011/7/1
うーん、やっぱ３流高卒の私の考えるゲームはワンパターン？
ゲームの状態Ｘtと操作a,bに対して
Xt+1=g(Xt,a)
Xt+1=g(Xt,Xt-1,,,,b)
で決まるような２種類の操作のあるゲーム。
もしくは
#ref(gameImage.gif)
のようにユニットの状態などをＺiとしこれに対する操作ｆとｇでＺｊに変更できるときの組み合わせがある。
ｆは先の予測が難しくｇは先の予測が簡単。
そして状態Ziとゲームの状態Ｃｉ(ｆを選ぶとＣの変化が早くないりＧを選ぶとＣの変動が遅くなる)からゲーム内での評価や得点などが決まるとする。
ｇを行うと、先の予測が簡単だが低得点に、ｆを行うと先の予測が難しいが高得点になる可能性がある。
操作ｆやｇによってＣの状態が変化していく。
こういうゲームを作れたらいつまでも飽きないゲームになるんじゃないかと思ったりはするんだけど？うーん、３流高卒なので具体化ができないんだよな。
*2011/6/30
[[仕事探し]]
*2011/6/21
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
を解くコード書きかけ。
最近Ｂｉｔ演算を覚えた。
自分のプログラムの実力を測ると少しだけプログラムのできる高校生レベルまで到達といったところかな。
ここまで幅優先探索を高速化しといて何だけど深さ優先探索のほうが早いのだろうか？
#include <set>
#include <stdio.h>
#include <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
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が指定の桁数Ａ、Ｂの桁数となるなら答えは正しい。
うーん、計算式が少しだけ複雑なので式変形のミスが不安になるなこの問題。
後計算量が1000万回に達するのですこしだけ計算時間が足らない。
*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/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)
で決まるような２種類の操作のあるゲーム。
もしくは
#ref(gameImage.gif)
のようにユニットの状態などをＺiとしこれに対する操作ｆとｇでＺｊに変更できるときの組み合わせがある。
ｆは先の予測が難しくｇは先の予測が簡単。
そして状態Ziとゲームの状態Ｃｉ(ｆを選ぶとＣの変化が早くないりＧを選ぶとＣの変動が遅くなる)からゲーム内での評価や得点などが決まるとする。
ｇを行うと、先の予測が簡単だが低得点に、ｆを行うと先の予測が難しいが高得点になる可能性がある。
操作ｆやｇによってＣの状態が変化していく。
こういうゲームを作れたらいつまでも飽きないゲームになるんじゃないかと思ったりはするんだけど？うーん、３流高卒なので具体化ができないんだよな。
*2011/6/30
[[仕事探し]]
*2011/6/21
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508
を解くコード書きかけ。
最近Ｂｉｔ演算を覚えた。
自分のプログラムの実力を測ると少しだけプログラムのできる高校生レベルまで到達といったところかな。
ここまで幅優先探索を高速化しといて何だけど深さ優先探索のほうが早いのだろうか？
#include <set>
#include <stdio.h>
#include <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
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が指定の桁数Ａ、Ｂの桁数となるなら答えは正しい。
うーん、計算式が少しだけ複雑なので式変形のミスが不安になるなこの問題。
後計算量が1000万回に達するのですこしだけ計算時間が足らない。
*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");
}
}
}
}
