移転しました

http://d.hatena.ne.jp/todo314/

今月の〇〇(2011年4月)

■Aizu Online Judge

Solved:254/46th
Rating:203.75/50th
Ratingは目標通り200に到達しましたが，そのせいでSolvedの順位が下がってしまいました．5月は，Solvedの順位を30位以上，願わくば20位以上にしたいです．

■TopCoder/Codeforces

Codeforcesは，一旦Div.2に落ちたものの，再びDiv.1に復帰しました．
TopCoderは，Rating微増．

今月の〇〇(2011年3月)

■Aizu Online Judge

Solved:235/43th
Rating:151.76/67th
簡単な問題ばかり解いていたので，Ratingの順位がやや低めです．ということで来月の目標はRating200にしました．

■TopCoder/Codeforces

ほとんど参加できていません．そのためレーティングも代わり映えしていません．そのため来月は，レーティングの昇降は兎も角として，出来るだけ参加することを重視しようと思います．

■専門書

「計算理論の基礎」を読み進めています．5章辺りを読んでいますが，練習問題に全く手を付けていないため，そちらにも着手する必要がありそうです．また，「コンピュータの数学」は今の自分なら十分読めると判断したため，そろそろ真面目に読もうかと考えている次第です．

更新弱化中とその原因そしてその解決策

さて，今月のブログエントリ数が約1年振りに1桁となりましたが，その原因は一体何かと言いますと，即ち卒業研究なわけです．

高専では，最高学年である5年において，丸々1年間を使い指導教員の下卒業研究に取り組みます(多分)．昨年は，色々と手を出し過ぎた事に加え，長期間に渡り体調を崩してしまったため，随分と遅れを取ってしまった事を記憶しています．現在は，どうにか最終発表を無事に終え，あとは卒業論文と学会発表が控えているというわけです．卒業論文と学会の要旨原稿の締切がこれまた，2/10と非常に迫っており，そのため暫くの間ブログの更新は無理そうです．つまるところ，2/10以降には，少しく時間が出来るというわけです．

ちなみに，私が取り組んでいるテーマをひとことで言うと，「家庭用ロボットの効率的な振舞を強化学習によって獲得する」です．

多くの家庭用ロボットにはヒューリスティクスが組み込まれており，それに従って掃除を行っています(ちなみに，業務用掃除ロボットは，高精度センサ使用可能+室内形状が既知という条件から，経路計画さえ済んでしまえば，その経路をロボットがたどるだけで終わります)．そのため結構効率が悪いです．というわけで，効率向上を目的としてロボットに振舞を学習させるわけです，自動で．実環境への適用は滅茶苦茶難しいので，現時点では，実環境を模擬したシミュレーション上での実験を行っています．ある程度の制約はつきますが，それでもいくらかは効率化可能なようです．

余談ですが，競技プログラミングに関わっていたお陰か，随分とシミューレションの高速化が出来ました．どこが一番時間を食っていてどこをどう変えれば高速化するか，というのが直感的に分かるわけです．最終的には，最初のプログラムに比べ100倍近く高速化出来ました．

2011年の目標

というわけで今年の目標を制定します(途中で変更するかも)．

■プログラミング関係
・ICPC
国内予選10位以内
アジア地区予選10位以内
・Aizu Online Judge
10位以内(Solved)
・TopCoder
YellowCoder(1500以上)
・Project Euler
Level 5
・コンパイラ制作
何か一つ，自分専用言語を作ってみたいですね．

達成出来そうで出来なかった目標達です．

■その他
・体調管理
昨年は，半年近くに渡って体調を崩してしまい，多くの方に迷惑をかけてしまいました．
今年は，限度を超えて無理をすることが無いようにスケジュールを組んでいきたいと思います．
・筋トレ
上の達成に貢献できそうなものとして．
・専門書消化
昨年と同様，まだまだ読み終えていない本が沢山有ります．

あまり多過ぎると手付かずのまま時間だけが過ぎ去ってしまうので，この位に止めておきましょう．

2010の目標の達成状況

さて，2010年もあっという間に終わってしまい，2011年に突入しました．昨年を振り返るため，2010年の目標の達成状況を考察してみます．

http://mainly-coding.blogspot.com/2010/01/blog-post.html
↑これ．

■プログラミング関係
・TopCoderでYellowCoderになる
Maxで1463まで行った(+37pでYellow)のですが駄目でした…．
・Project EulerでLevel4になる
この目標を書いた時点で31問，12月入った時点で100問程度でしたが，怒涛の勢いで問題を解いていき，ぎりぎりLevel 4(150問)に到達しました．
・PKU Judge Online，anarchy golfへの参加
anarchy golfは幾つか参加し，POJは現在88問です．むしろAOJへの参加の方が多いでしょう．
・新しい言語を一つ以上習得する
Prolog(論理プログラミング言語)を始めました．習得は出来ていませんが，今も尚，勉強は続けています．

■その他
・溜まった専門書の消化
何冊か読みましたが，それ以上に買った冊数が多い気がします．
・数学，物理，英語の勉強(編入試験勉強を兼ねて)
数学はそこそこ復習しましたが，他は…．
・趣味の充実
ICPCへの参加により充実度やモチベーションが非常に高くなったと思います．

多くの目標は達成できたとは言えませんが，目標が全く無いよりはモチベーションが高くなりますし，また達成感という物が生まれると思います．

後日，今年の目標を書こうと思います．

SuperCon 2010 予選問題

SuperCon(Supercomputing Contest)とは，高校生(含高専生)を対象としたプログラミングのコンテストです．

Supercomputing Contest - Supercomputing Programing Contest Official Site

まず，予選問題が公開されます．予選を通過した10チームは，大阪大学，東京工業大学のスーパーコンピュータを使って本選課題に取り組みます．提出されたプログラムは，審査委員によって評価され，最終的に結果発表，というわけです．

というわけで，予選問題が公開されました．ある図形に対して長方形のレンガを隙間なく並べる場合，その並べ方はいくつあるかといった問題です．それ程難しい問題では無いので，興味ある方はどうぞ．

Supercomputing Contest 2010/予選・認定問題 - Supercomputing Programing Contest Official Site

1次元画像

最近二次元画像が巷に溢れかえっています．Wikipediaには「二次元コンプレックス」なんて項目もあります．しかし，その一方，4次元画像や1次元画像は二次元画像程普及が進んでいません．これは何と由々しき事態でしょう．今回は，その普及に貢献するため1次元画像を作成いたしました．


Fig.1 (x+1)x(x-1)
3次関数の値をグラデーションに割り当てました．関数は3次なのに画像は1次というこのギャップ．


Fig.2 Mickey Mouse
ディズニーのキャラクターというのは，一般に白黒+(彩度の高い)有彩色で構成されていますので，色彩のみからキャラクターを想像することが出来ます．これならうっかり●を3つ描いてしまう恐れもありません．


Fig.3 Noise
彩度，明度ともに最大，色相のみランダムに生成しています．


Fig.4 Monochrome
白と黒だけのシンプルな構成．

今宵の1次元画像，如何でしたでしょうか?

とど丸3号(リボルバータイプ)

とど丸3号(リボルバータイプ)をFig.1に示す．


Fig.1 Todo Maru No.3 Revolver type

これは某hara氏から頂いたものであり，マグネットを5箇所に装備してあるため非常に優れた収納性を有する．畳んだ状態でのとど丸3号(リボルバータイプ)をFig.2にしめす．


Fig.2 Todo Maru No.3 Revolver type(Pechanko)

この例からも分かるように，とど丸3号(リボルバータイプ)は，胸ポケットに丁度スッポリ入るという特性をもつ．

購入した本

ブックオフオンラインにて購入した本の一覧．

英語の構文150 Second Edition \700
基礎英文問題精講 改訂版 \450
英作文のトレーニング 入門編 \500
物理のエッセンス電磁気・熱 新課程 改訂 \450
物理のエッセンス力学・波動 新課程 改訂 \859
困ります、ファインマンさん \600
雪は天からの手紙 中谷宇吉郎エッセイ集 \400

今年の目標

2010年も約1/24が過ぎてしまいましたが，今年の目標．

■プログラミング関係
・TopCoderでYellowCoderになる
　現在Ratingが1216だから，あと284p必要．
・Project EulerでLevel4になる
　31問解いたので，あと119問．
・PKU Judge Online，anarchy golfへの参加
・新しい言語を一つ以上習得する

■その他
・溜まった専門書の消化
・数学，物理，英語の勉強(編入試験勉強を兼ねて)
・趣味の充実

あんまり多いと実行できないのでこの位．(でも多い)

ファインマンに学ぶ科学的良心

年末は，ファインマンに学ぶ科学的良心．

リチャード P. ファインマンの自伝「ご冗談でしょう、ファインマンさん」の「カーゴ・カルト・サイエンス」．これは彼のカリフォルニア工科大学1974年卒業式式辞を文書化したものですが，非常に素晴らしいことが書かれています．ということで一部抜粋．

　今あげたこういう教育上の、または心理学上の研究は、実は私が「カーゴ・カルト・サイエンス(積み荷信仰式科学)」と呼びたいと思っているえせ科学の例なのです。南洋の島の住民の中には積み荷信仰ともいえるものがある。戦争中軍用機が、たくさんのすばらしい物資を運んできては次々に着陸するのを見てきたこの連中は、今でもまだこれが続いてほしいものだと考えて、妙なことをやっているのです。つまり滑走路らしきものを造り、ヘッドホンみたいな恰好のものを頭につけた男(フライトコントローラーのつもり)をその中に座らせたりして、一心に飛行機が来るのを待っている。形の上では何もかもがちゃんと整い、いかにも昔通りの姿が再現されたかのように見えます。
　ところが全然その効果はなく、期待する飛行機はいつまで待ってもやってきません。このようなことを私は「カーゴ・カルト・サイエンス」と呼ぶのです。つまりこのえせ科学は研究の一応の法則と形式に完全に従ってはいるが、南洋の孤島に肝心の飛行機がやってこないように、何か一番大切な本質がぽかっとぬけているのです。

　諸君に第一に気をつけてほしいのは、決して自分で自分を欺かぬということです。己れというものは一番だましやすいものですから、くれぐれも気をつけていただきたい。自分さえだまされなければ、他の科学者たちをだまさずにいることは割にやさしいことす。その後はただ普通に正直にしていればいいのです。
　もう一つ、これは科学にとってはさほど重大なことではないが、私が信じていることを申し上げたい。それは諸君が科学者として話をしているとき、たとえ相手が素人であっても決してでたらめを言ってはならないということです。(中略)私が言わんとしていることは、嘘を言う言わないではなく、科学者として行動しているときは、あくまでも誠実に、何ものもいとわず誠意を尽して、諸君の説に誤りがあるかもしれないことを示すべきだということです。これこそ科学者同士の間ではもちろんのこと、普通の人たちに対するわれわれ科学者の責任であると私は考えます。

　あるとき私はラジオに出演する友人と話をしていて、少なからずびっくりしたことがあります。彼は宇宙論と天文学をやっている男でしたが、この研究がどのようにして実際に応用できるかを、いかに説明すればいいかというので、頭を悩ませていました。私がつい「そうさなあ。応用できることなんか何もないんじゃないか」と言いますと、彼は「うん、実はその通りなんだ。しかしそんなことではこの種の研究に研究費が出してもらえなくなるからな」と言いました。私はこれを一種の不正直さだと考えるのです。もし科学者として立つなら、素人に自分の研究していることをよく説明し、それでも支持してくれないのなら、それは向こうの決めることなのだからしかたがないのではないか。

最近(というかちょっと前)話題になっている「事業仕分け」．それで上の話を思い出しました．
内なる世界にいれば，どうしても盲目的になりがちな気がしますが，そういう人も他の人に対し自分が何をやっているか懇切丁寧に説明しなければならないのではないかと感じました．

ファインマン伝説

・学生時代，ガリ勉野郎の部屋のドアを外して地下室に隠す
・マンハッタン計画中に機密の入った金庫を開けまくる
・余りに腕が良かったので，番号を忘れた仲間から依頼されることも
・検問にむかついたので抜け穴から出る→入るを繰り返してお説教を食らう
・と思ったら今度は検閲にむかついて手紙をジグソーパズル化する．当然怒られる
・当時から物理学の大家であったボーアに「何とち狂ったこと言ってるんだ」と発言
・打楽器ボンゴの名人
・ブラジルにいた頃「明日は名物のパレードが見られますよ」と言われたがそのパレードに参加していた
・精神科医が嫌いなのでいたずらしたら兵役を免れた
・絵も得意．個展を開いたこともある
・たまたま喧嘩を目撃し，皿が飛んでるのをみて皿の運動を計算する
・その理論を元にしてノーベル物理学賞を受賞
・受賞の知らせに「何て無礼な奴なんだ，今深夜じゃないか」
・「辞退する方法はないのか？」「辞退したらもっとややこしいことになりますよ」→諦めて受け取る
・初来日の時，日本に来たんだし日本の旅館に泊まりたい！というので無理を言って宿泊場所を変更
・作法が分からないのでとりあえずﾋｬﾎｩ！と風呂に入ったら先客の湯川博士に怒られた
・別の来日時は「不敗魔」と自己紹介した

ノーベル物理学賞受賞者ファインマン伝説より，一部修正．

第20回 全国高等専門学校プログラミングコンテスト After

10/17~18にかけて第20回 全国高等専門学校プログラミングコンテストが行われました．

今回，競技部門は問題なく進行されました．また，環境に関しても，無線LANが飛んでいたので控室でストリーミング放送を見ることが出来，非常に過ごしやすかったです．プロコン関係者の方々お疲れ様でした．

さて，結果の方はというと，敗者復活戦で1位を取り復帰はしたものの，準決勝では揮わず敗退．大阪府立に実力を見せつけられました(準決勝において，マップAで34ステップを出したものの，大阪はたったの22ステップでした)．

そんなわけで，Itmediaの記事です．
高専プロコンリポート：「最強最速」を見せつけた浪速の高専生 - ITmedia エンタープライズ

ちなみに，主な手法はSA(焼きなまし法)を用いたものでした．ある程度の長さのステップの系列を用意し，系列中のステップを変更させながら焼きなます，といった方法です．個人的には幅優先探索を主体とした場合，ノード数が爆発的に増えるため活用は不可，と考えていました．ところが大阪府立は上手いこと(マップのサイズ毎に)評価関数を作ったのでしょうか，短い時間でステップ数の短い解を叩き出していました．すごいです．

このような大会は非常に刺激があり，今後の開発もモチベーションアップにも繋がりました．睡眠不足にはなりましたが，非常に実のある2日間であったと思います．

ノイマン伝説

・6歳で8桁の割り算は当たり前，8歳で微積分マスターも
・ノイマンの正式名称は悪魔の頭脳
・推定IQは300，仮に東大の医学部を目指せば1週間で入れるレベル
・趣味はスカートのぞき
・同僚が一晩徹夜して解いた難問を数分で解いたため，同僚は青ざめた
・ノイマン先生の車が近付くだけで，学生たちは逃げだした，心臓発作を起こす学生も
・ENIACとの計算勝負に勝ち「俺の次に頭のいい奴が出来た．」
・水爆の効率概算は天井を向いて暗算
・ハンガリー人と思われがちだが，実は火星人
・口癖は「なかよしイケメン」
・1日4時間の睡眠時間以外は常に思考
・世界史，ゲーテの小説は一字一句間違えず暗唱できた
・割り算で答えられる問題を無限級数の和で解答するというファンサービス
・紙とペンだけでセルオートマトンの分野を開拓
・ノイマンは実はまだ数学分かってないもんな．本気で覚えたらスゲエ事になるぞ
・原子力委員会の会合には救急車で出席
・葬式にて知人曰く「ノイマンは人間ではなかった．長い間人間と一緒にいたので，真似がうまくなっただけだ．」

第20回 全国高等専門学校プログラミングコンテスト Before

今年もやってまいりました，全国高等専門学校プログラミングコンテスト．
前回は不本意な終わり方をしましたが．今年は記念すべき20回目，主管校の木更津高専その他頑張っておられると思います．

さて，競技の内容は，パズルゲームです．下記公式サイトに詳細があるのでどうぞ．

http://www.procon.gr.jp/modules/procon20/item.php?itemid=18

前回に比べて圧倒的に難しいです．人力で解くことも勿論できますが，ステップ数を短くするとなると，コンピュータに頼らざるをえませんし，最適解となると時間がかなり掛かります．そして，時間が掛かっていては他のチームに負けてしまいます．また，運の要素が無い(互いに干渉しあう要素が無い)ので，実力勝負になると思われます．

高専プロコン2009競技練習場にて，練習ができます．コルンさん(久留米高専OB)に感謝．人力モードもありますので皆さん解いてみてはいかが?

GOMOKU NARABE

○×ゲーム作成後，それを基盤として作りました．

GOMOKU NARABE



Fig.1
タイトル画面．稚拙ながらも狙って作っている事が窺えます．


Fig.2
ゲーム画面．プレイイヤーはマリオとルイージを交互に配置していきます．


Fig.3
プレイヤー2(ルイージ)が勝ちました．

これを製作した後3人で合作を作り，更にその数か月後，「TETRIS for GBA」を作りました．

○×ゲーム

約3年前，事実上初めて製作したゲームです．
「TETRIS for GBA」と同じくGBAのソフトであり，言語はC，開発環境はDevKit Advanceです．

○×ゲーム

そのまんま○×ゲームです．


Fig.1
タイトル画面．「ゲーム」の文字は手書きっぽくしたようです．


Fig.2
ゲーム画面．非常にシンプルな構成です．プレイヤー1，2は交互に○×を書いていき，縦横斜めの何れか3つ揃えば勝ちです．


Fig.3
一応5本先取という形です．

スプライトの使い方等をまだ知らない状態で作ったので，1ドット単位で描画を行っています．

BLOCK GAME

約2年前，諸事情によりiαppliを作成しました．
iαppliもフリーで作成することができます．言語はJavaです．

BLOCK GAME

コンセプトは，「携帯ゲーム機の色，デザインの模倣」，「無意味に使えるカーソル」といったものだったと思います．


Fig.1
タイトル画面．手抜き感が漂います．(何故か存在する)カーソル(十字キーで移動)で「PLEASE CLICK」をクリックする事により，ゲーム選択画面に移れます．


Fig.2
ゲーム選択画面．これまた手抜きです．


Fig.3
TYPE A．いわゆるスネイク．


Fig.4
TYPE B．障害物(規則的に横並びになっているブロック列．左右どちらかに動きます)にぶつからないように，一番下にあるブロックを移動させます．


Fig.5
TYPE C．変な四角いもの(図では左下)を左右に操作し，他の変な四角いものにぶつからないようにします．


Fig.6
LIFE GAME．ライフゲームです．

時期はTETRIS for GBAの後であり，「極端なシンプルさ」を狙ったものですが，開発期間が1週間程度だった為か，文字や画像，そしてそれらの配置やデザインが非常に稚拙であると感じました．

TETRIS for GBA

以前(2年以上前)作成したモノの紹介．

TETRIS for GBA

TGM3を参考にして，GBA用に作った20Gモードのテトリスです．
ちなみに，GBAのソフトはC言語で作る事ができ，PC上でもエミュレータで動作させる事ができます．


Fig.1
タイトル画面．


Fig.2
ゲーム画面．背景以外は(TGM3を模倣したデザインで)全て自分でドット絵を打っています．

20Gモードですので，IRSや壁蹴り，回転規則の純粋な再現等，割と凝って作った記憶が思い出されます．
また，画像に関しても当時のレベルで出来る事を全てやったようです．