英語を頑張った時の話

無職をやった期間の序盤、確か一か月くらいかけて英語を頑張って、TOEICが750から915になったのですが、その時の記憶のメモです。

目的:これから数学・プログラミングの勉強をする上で、原著があるものは原著で読みたい
追加のモチベとして、前職の友達数人と勝負をしてました。元のスコアがバラバラなので、上り幅が多い人が勝ちで、お高い焼肉を賭けて。

やったのは基本的に総合英語ForestDUO 3.0瞬間英作文トレーニングの周回です。

Forest

まず1周、1週間くらいかけて例文は音読しつつ通読して、その後は他の本で文法的に良くわからない部分がある度に該当箇所を読んで、3週間ぐらいしたらもう一回通読しました。2周目は解いトレも同時にやったけど、1周目でもよかったかも。2016年現在はR満点なのですが、英文法は基本これしか読んでないです。英文法はどんなにうまく説明されているように見えても例外ケースがあってモヤモヤするのですが、そういういい加減なものだと割り切って、文法の細かい部分は無理に理解しようとせず丸暗記して口で覚えるのがむしろ楽な気がします。

DUO 3.0

全文覚える。1周目は割と丁寧に、文法的に良くわからんところとかはForestやら見てできるだけ納得した上で、日本語訳から英語を詰まらず言えたら次に行く。その時復習編のCD聞いて、イントネーションとか真似してそれっぽく言う。次は散歩とかしつつ復習編CD聞きながらシャドーイング。できれば同時ぐらいでしゃべる。意味も英語もぱっと浮かんでれば問題ないけど、あやしいやつは本に戻る。そんな感じで口に覚えさせる感じで全文やりました。(が、最後1/3ぐらいは最後まであやしかった)

瞬間英作文トレーニング

これは本を見ながらというのは一回さらっとやっただけで、ひたすらCD聞きながら、日本語言われた後に英語を話す、ということをやってました。これも散歩中が多くて、DUOより負荷が低く感じてたので疲れてる時はこっち優先。ぼーっとしてても口からどんどん英語が出てくる。リスニング/スピーキング両方に効果があった感じがします。

 

反射的に話せる表現とか文法とか単語は多分聞き取れるでしょう、ということでTOEICにはスピーキングないけど出来るだけ”話せる”というのを習得の基準にしてました。

基本的に英語の勉強あまり楽しみが見いだせないのだけど、この時みたいに期間を区切って一気にやったり、こういう抱き合わせとかやりながらぼちぼち勉強してます。

Googleに入社しました

報告らしい報告をしていなかったのですが、先月からGoogle Japanでお仕事しています。
分からないことだらけで右往左往ですが、とにかく親切な方ばかりで楽しくやってます。

再びたくさんの人に使ってもらえるプロダクトに関われます。
早いところ「あれをするにはこれをすればよい」みたいなのが分かるようになって、できるかな的なノリでいろいろ妄想したり作ってみたりしたいなと思ってます。

2年間の独学をふりかえって

2012年と2013年を独学に費やしました。
予定した2年が終ったので、試行錯誤していたやる気対策の話と、お世話になった本のリストを書いて、打ち上げにします。

やる気対策

2年分の時間と教材は確保していたので、あとはやる気をどう生成するかが問題でした。
「やらなきゃ」って気持ちは役に立たないどころか邪魔になることも多かったです。
脳という、意志だけでは制御できない他人みたいな存在に、できるだけやる気をだしていただこうと、いろいろ気を使いました。
試してみた中から、効果を感じられた習慣を挙げます。

運動する

IMG_0420
体調とやる気の相関は強く、体調を整えるためにもコンスタントに運動するように心がけてました。
歩くの好きなので、2日に1回は1時間くらいウォーキングする、みたいな感じです。
歩いてる間、血行が良くなるおかげか頭が回りやすく感じていたので、問題を解いたり考え事をする時間にしてました。あと謎にやる気が湧いてきたりするので、帰ったら何しようかワクワク計画したり。
隔週ぐらいで、遊びも兼ねて自転車での遠出もしてました。

日光を浴びる

IMG_0527
午前中、できればまだ通勤の人が多くない時間帯が一番好きで、天気の良い日はよく外に出てブラブラしてました。
原理はよく知らないけれど、日光を浴びてるとストレスが解けてく感じがします。

広いところに行く

322260_2978695467546_1325038387_o
自分の部屋で勉強してると眠くなりがちでした。
部屋にはベッドがあるのも良くないと思うのですが、そもそも狭い所だと眠くなる傾向があるように思いました。心理的なものか酸欠なのか…
プログラミングではあまり眠くならないので問題無いのですが、読書する時や数学やる時は自習室とかの広めなスペースに良く行ってました。

数値で成果を測る

topcoder-graph
頑張ったら、その頑張りで自分が成長したことを実感して次のやる気につなげたいところです。
自分が前に進んでることを感じたり、学習のやり方が間違ってないと確信するために、TopCoder(競技プログラミング)やTOEICなど能力を数値で表してくれるテストはとても頼りになりました。
数値で進捗を計りづらい学習(設計の勉強とか)も多いですが、そういうのは次に挙げる累積学習時間を成果と考えることにしました。

(自慢ですが、TopCoderの成績はこの2年で上位35%から上位3%まで伸び、その過程でやる気も自信も大きく充填されました。これ無しでは漠然とした不安感が集中の妨げになったりしたのではないかと思います。競技プログラミングの勉強法についても色々考えながらやったつもりなので、別エントリで書こうと思います。)

時間を測る/区切る

スクリーンショット 2014-01-14 7.29.57 AM
自分が頑張ったことを自分で認めて褒めてあげるために、頑張りによって単調増加する「集中して学習していた時間の累計」を記録・参照できるようにしてました。
本を読んでる間とかによく時間を測っていて、測ってる間は別に読み急いだりはしないものの、SNS見たりといった関係ないことは一切しないのをルールにしてました。
プログラミングや数学の問題を解く時は全力で急ぎました。ストップウォッチを持って、「何分何秒で解けた!」とか「30分経ったのでタイムアップ…」みたいな事を記録してました。ダラダラやればやるほどやる気がしぼんでいくのを感じたので、ダラダラできないよう何か制約をかけるのは効果的だと思います。

1日の勉強は、軽いの->重いの->楽しいの の順でやる

IMG_0850
「やればやる気が出るし、やらなければやる気が出ない」というやっかいなフィードバックに対応するために、起き抜けとか長めの休み時間の後は、軽い気持ちですぐ取り掛かれる短時間の勉強を入れてました。
簡単な問題を1問解くとか、読みやすい本を1章分読むとか、10分15分で終わるようなものです。その後何するか(あるいは何もしないか)は、15分の勉強が終わってから考えることにしてました。
加えて、一日の終わりに楽しげな勉強を入れておくことで、それを早くやりたいから重い内容の勉強を頑張って終わらせよう!というモチベーションを作りました。

お世話になった本

読んだ本のうち、良かったなと印象に残ってる本を並べてみました。基礎の幅を広げたいという方針があったので、何かの入門的な本が大半です(どれも僕には十分難しかったですが…)
一度は最後まで読んでいて、時間の記録をしていた本は、読むのにかけた時間も併記しました。

数学

論理学 31.3時間
1対1対応の演習/数学1 新訂版 (大学への数学 1対1シリーズ) 35.3時間
1対1対応の演習/数学A 新訂版 (大学への数学 1対1シリーズ) 25.4時間
1対1対応の演習/数学II 新訂版 (大学への数学 1対1シリーズ) 72.2時間
1対1対応の演習/数学B 新訂版 (大学への数学 1対1シリーズ) 30.7時間
無限論の教室 (講談社現代新書) 5.3時間
新装版 集合とはなにか―はじめて学ぶ人のために (ブルーバックス) 9.0時間
数学ガール フェルマーの最終定理 (数学ガールシリーズ 2) 4.9時間
数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3) 7.2時間
数学ガール 乱択アルゴリズム (数学ガールシリーズ 4) 8.1時間
数学ガール ガロア理論 (数学ガールシリーズ 5) 10.2時間
高校数学でわかる線形代数―行列の基礎から固有値まで (ブルーバックス) 7.9時間
線形代数学(新装版) 79.5時間
集合と位相 (数学シリーズ)
解析入門 原書第3版
はじめての数論 原著第3版 発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで
離散数学「数え上げ理論」―「おみやげの配り方」から「Nクイーン問題」まで (ブルーバックス) 19.5時間

アルゴリズム

アルゴリズムクイックリファレンス 25.4時間
プログラミングコンテストチャレンジブック [第2版] 181.3時間
Introduction to Algorithms 234.6時間
最短経路の本 レナのふしぎな数学の旅
ゲーム制作者のための物理シミュレーション 剛体編 7.2時間

プログラミング、その他

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice) 7.8時間
入門git 10.6時間
すごいHaskellたのしく学ぼう! 35.8時間
Effective Java 45.2時間
Effective STL 23.1時間
パーフェクトJavaScript (PERFECT SERIES 4) 34.3時間
はじめてのNode.js -サーバーサイドJavaScriptでWebアプリを開発する- 25.1時間
iOS Programming: The Big Nerd Ranch Guide, Third Edition (3rd Edition) 85.3時間
初めてのRuby 12.5時間
Ruby on Rails 3 アプリケーションプログラミング 24.5時間
ふつうのLinuxプログラミング Linuxの仕組みから学べるgccプログラミングの王道 17.5時間
30日でできる! OS自作入門
[24時間365日] サーバ/インフラを支える技術 12.4時間
プロセッサを支える技術  --果てしなくスピードを追求する世界 (WEB+DB PRESS plus)
[Web開発者のための]大規模サービス技術入門 10.9時間
Amazon Web Services クラウドデザインパターン 設計ガイド 7.9時間
アジャイルサムライ−達人開発者への道− 9.5時間
CODE COMPLETE 第2版 上
Arduinoをはじめよう 第2版 (Make:PROJECTS)
「レベルアップ」のゲームデザイン ―実戦で使えるゲーム作りのテクニック 17.8時間
ノンデザイナーズ・デザインブック [フルカラー新装増補版] 10.7時間
モバイルデザインパターン― ユーザーインタフェースのためのパターン集 8.3時間

Conclusion

楽しかったー!
感想として、やっぱり2年という時間で何か特別なことがやれる訳では無いんだなぁと思いました。4年サボった分を2年で取り返すことは出来ないです。2年は2年なり。
ですが、この2年分は今後のための基礎としてどうしても欲しかった部分でした。自信も少しついたと思います。主に「飽きずに勉強できたし、これからも続けていけそう」という点で。
この2年間に、今はとても満足してます。

これから?どうしようかな… 目下めっちゃ考え中です!

自動クッキークリッカー

クッキークリッカー楽しい!

けど終盤になって「ゴールデンクッキーをセンターに入れてクリック、ゴールデンクッキーをセンターに入れてクリック」とひたすら繰り返す状態になってしまい、このままでは僕まで人間を辞めてしまうので、禁呪に手を出しました(Chrome Extensionにクリックしてもらうことにしました)。

以下の2ファイルを同一フォルダに入れて、

  1. Chromeの”ツール”から”拡張機能”の画面を開く
  2. 右上の”デベロッパーモード”のチェックボックスにチェックを入れる
  3. 「パッケージ化されていない拡張機能を読み込む」をクリックして、前述の2ファイルが入ったフォルダを選ぶ。
  4. クッキークリッカーのページ開く(既に開いていれば再読み込みする)

以上です。クッキークリッカーの仕様が変わったら動かなくなります。

ファイル1: manifest.json

{
  "manifest_version": 2,
  "name": "Auto Cookie Clicker",
  "version": "1.0",
  "content_scripts": [
    {
      "matches": ["http://orteil.dashnet.org/cookieclicker/"],
      "js": ["clicker.js"]
    }
  ]
}

ファイル2: clicker.js

var bigCookie = document.getElementById('bigCookie');

window.setInterval(function() {
  if (bigCookie) bigCookie.click();
}, 10);

window.setInterval(function() {
  var goldenCookie = document.getElementById('goldenCookie');
  if (goldenCookie) goldenCookie.click();
}, 1000);

設備のアップグレード戦略とか色々考えられるので、Chrome Extensionで遊ぶとっかかりとしても面白そうな気がします。

マラソン頑張りました (TopCoder Open 2013 MM R3参加記)

TopCoderにはマラソンマッチという部門があります。
基本的に”最適解”は求まらない問題が与えられて、できるだけ”ベターな解”を求めるプログラムを書いた人が優勝です。
期間が長いのも特徴で、今回は2週間ありました。
今回の問題はこんな感じ。

平面上に円がたくさん置いてあるので、お互いが重ならないように円の位置を修正してください。
ただし、円にはそれぞれ重さがあって、動かすには(重さ×動かした距離)のコストがかかります。このコストの合計が低ければ低いほど良い解とみなされます。

tco13mmr3-1

今回の問題はTopCoder Openという大会の一部で、4位までが秋にワシントンDCで行われる決勝に招待されて、文字通り世界のトップコーダー達とキャッキャウフフできます。

成績

自分の成績ですが、予想外にも14日のうち7日目辺りから1位争いを始め、13日目まで1位と僅差の2位につけてました。まさかの初参加で決勝進出かと夢を見ます。
tco13mm3-2
初参加の日本人が上位にいるぞということで、こちらから一方的に知ってるだけだった人たちに期待してもらって嬉しい思いをしたり。
そして迎えた最終日。最終的な順位はこうなった。
tco13mm3-3
知ってた!
そんな甘いはずないですよね…

解法概要

剛体シミュレーションによって制約(重なってはいけない)を満たし、円の元々の位置への引力と振動を与えることで局所改善を行った。
初期配置は密度の高い円から順に距離0の位置に配置した上で、配置済みの円の合計面積がある程度(0.75-1.15)以上になれば残りは大きく外側に離した位置からスタートする。
初期配置を決めるパラメータはある程度見込みのない値は学習するが基本ランダム。(ソース)

活動記録

思い出としての気持ちの記録と作業記録をごちゃまぜ箇条書きで。

準備フェーズ(1日目)

  • 問題どこで見れるのか分からない。30分右往左往する。
  • とりあえず1回提出してみよう。適当に円が重ならなくなるまでじわじわ外に動かすプログラム書いてsubmit。ちゃんと点数が付いた。思ったよりとっつきやすい。
  • プログラムの実行状況を絵的に表示するプログラム(ビジュアライザ)は、自分で作るなり改造するなりした方がいいと聞いてたので、前から気になってたCinderを使って実装した。楽しい。
  • 公式のTesterを介さなくてもテスト走らせられるよう、テストケースを2000件ほど抽出しておく。

考察フェーズ(2日目)

  • 以前wataさんに「マラソンのコツはコードを書かないこと」というアドバイスをもらったのを思い出し、コードから離れて問題の性質について考えてみる。
  • 2つの円が重なってる状況とか、1つの円が3つの円に囲まれた状況とか、小さい局面での最適解を考えたりする。
  • 逆にざっくりした捉え方をするなら、できるだけエネルギーの低い結晶をつくるタスクって感じがする。物理法則が役に立ちそうな気配を感じる。
  • 円それぞれに対して、元あった位置への引力を設定した上で、衝突反発と引力がバランスするまでシミュレーションしてみるって方針を立てる。小さい局面のいくつかでも最適解が出そう。

実装フェーズ(3日目〜5日目)

  • 物理思い出しながらコード書いてみる。カオスな動きで謎にテンション上がる。
  • だんだんまともに動き始めてきた。スコアは微妙。
  • 重い円は軽い円を弾き飛ばして内側に入ってきて欲しかったんだけど、最初固まりになりすぎてて重い円がうまく引力で内側に落ちてこれてない。
  • 円の初期配置はある程度ばらしたほうが良さそう。ただ適当にばらすんじゃなく、小さくて重いやつを優先的にいい位置に配置したいので、密度(m/r^2)が高い円ほどスタート位置が内側にくるようにする。
  • このへんで10位以内に。今の方針は悪くなさそうと手応えを得る。

高速化フェーズ(6日目〜7日目)

  • 高速化は終盤にやるのが定跡なんだろうけど、本番サーバの特性知らないのも気がかりなので、早いうちにやっとくことにする。
  • Example Testのログを使って回ってるループ数測ったり時間かかってる部分の特定をがんばる。
  • 座標などはfloatに丸めてシミュレーションした方が速かったのでそうした。要因未調査。キャッシュヒット率とかかな?(効果: 1.2倍)
  • 基本的なSIMD命令を使用(1.3倍)
  • ループ内でのメモリアロケーション排除とか、事前計算可能な値は先やっとくとかの基本的な処置(1.2倍)
  • シミュレーションのアルゴリズム自体の高速化も必要そう。勉強のいい機会なので「ゲーム制作者のための物理シミュレーション 剛体編」読んだりBox2Dのソース読んだりする。
  • 一番のネックになってた衝突検出に、本で勉強したSweep and Pruneを2軸で適用する(5倍)
  • トータルでループ10倍以上回るようになった。
  • とうとう1位に立つ。うまくいきすぎでは・・・

機能追加フェーズ(8日目)

  • 一晩動かした結果のベストな配置を横に表示しながらシミュレーション眺めたりして、より短時間でそこへ到達できるヒューリスティックとか無いか考えたりする。あんま思いつかない。
  • 微妙に効率悪い位置に落ち着いてしまう円があったので、全体を揺らす操作でスコア改善
  • 何度も連続で揺らせばスコア改善が続く場合があったので、過去のベストに近いスコアのときはしつこく揺らすようにしてスコア改善
  • ベストスコアを更新した時の状態を記憶しておいて、直後悪化した場合に一定回数はUndoして別の操作を試みるようにしてスコア改善
  • 引き続き1位。

チューニングフェーズ(9日目〜10日目)

  • プログラム中で使っている定数を調整したいけど、テストケースごとの得手不得手考えるとそれぞれの定数値の評価は300ケースぐらいで判断したい。
  • 調整したい定数の種類×定数値の候補数×300ケースの実行は手動ではやってらんない
  • プログラム起動時に定数値を指定できるように修正して、スクリプト回す。PCがフォーッてなる。EC2借りよう…
  • 借りたのはハイCPUエクストララージインスタンス。大人買い気分。シングルスレッドは手元のノートの方が速かったけど、6並列で頑張ってもらう。GNU Parallel便利だな。
  • 意外にも今まで適当に決めてた値が最善だったって場合がほとんどだった。
  • 2位にはつけてるんだけど、見込んでた伸び代が無いと分かって1位のeldidouさんに勝てる気がしなくなってくる。

悪あがきフェーズ(11日目〜13日目)

  • 今の解は、局所改善に物理シミュを使った多スタート局所探索に分類されるのかな。スタート地点の選び方もっと賢くできないだろうか。
  • 円の初期配置を決めるパラメータについて、ランダムじゃなく焼きなましや遺伝的アルゴリズムを試すも、わずかな効果。シミュ中のrandomnessで凸性が乱されてる感じ?そもそも各種探索手法に慣れてなくて勘所が分からない。
  • 円の初期配置について密度以外の新たな基準試す(初期状態で重なりが少ない円は優先度上げる/これまでの最善配置と重なりが少ない円は優先度上げる等) -> 改善/悪化トータルで誤差程度の影響
  • 円への操作について震わせる以外の新しい操作試す(捻る、広げる、力の大きさを入力に応じて変える等) -> 悪化または有意差なし
  • 今まで調整の対象にしてなかった定数を変えてみる -> 悪化または有意差なし
  • 2位を維持するものの、何やっても無駄な気がする状態に陥る。前半戦で感じてた楽しさを感じられなくなって反省会モードになる。

落胆フェーズ(最終日)

  • 案の定潜伏勢や追い込み勢に抜かれていくのを呆然と眺める。抜き返す気力は悪あがきフェーズで尽きてた。
  • 終了10分前の時点で5位。決勝には一歩届かない。未評価の変更をイチかバチかで入れる。スコアが落ちたのを確認して落ち込みながら終了。
  • 終了後にTL上で行われた感想戦は楽しかった。(参加してない時もそれを見るのは好きだった)

感想

今回成績良かったのは、単純に時間を多く割けたこととか、問題と相性が良かったこととか、colunさんの記事等で事前にある程度心構えができてたことが大きかったと思います。方針もちょっとまぐれ当たりっぽかったかな。
一方、反省点としては終了直後に感じたこのへんがメインかなと。


1は単純に時間の使い方間違い。仕事できない人っぽくてやばい。
2は重い感じがしました。ちゃんと理屈付けながら進めるための基礎力が不足している感は否めないんだけど、今の姿勢でやっててもその基礎力が着くことは無さそうなので次参加する時は強く意識しときたいです。

マラソンマッチについては、期間中使える道具はなんだって使える分新しい道具や技術に触れるきっかけになりそうなのと、解が正解/不正解じゃなくどの程度優れているかで評価されるので競争相手がより強く意識されて、短時間コンテストとはまた違った魅力を感じました。次回の具体的な目標も定まったので、また時間作って参加したいなと思います。

Railsアプリをgit pushでデプロイする

以前作ったSumtimerをわけあってHerokuからAWS(EC2+RDS)に移したんだけど、git pushでのdeployは気に入ってたので頑張って設定した。その作業メモ。

やりたいこと

Railsアプリ(awesome-app)を、
Git Repository(git@example.com:awesome-app.git)にpushしたら、
自動的にhttp://awesome-app.example.com/にデプロイされる

手順

  1. サーバにユーザ’git’を作って公開鍵でsshログインできるようにしておく
  2. # サーバ側(example.com)での作業
    # 事前にローカルPCの公開鍵(ここではid_rsa.pub)をRemoteの適当なところにコピーしておく
    sudo useradd -m -s /bin/bash git
    sudo su git
    mkdir /home/git/.ssh
    cat id_rsa.pub >> /home/git/.ssh/authorized_keys
    
  3. push先のリポジトリを作る
  4. # サーバ側(example.com)での作業。gitでログイン中。
    mkdir ~/awesome-app.git
    cd ~/awesome-app.git
    git init --bare
    
  5. 作ったリポジトリをリモートリポジトリとして登録しておく
  6. # ローカルPC上での作業
    git remote add production git@example.com:awesome-app.git
    
  7. デプロイ先を作る。
  8. # サーバ側(example.com)での作業。gitでログイン中
    mkdir ~/deployed
    cd ~/deployed
    git clone ~/awesome-app.git
    
  9. http://awesome-app.example.com/がデプロイ先を参照するようにしておく
  10. (例:Apache/Passengerの場合)

    <VirtualHost *:80>
       ServerName awesome-app.example.com
       DocumentRoot /home/git/deployed/awesome-app/public
       <Directory /home/git/deployed/awesome-app/public>
          AllowOverride all
          Options -MultiViews
       </Directory>
    </VirtualHost>
    
  11. git pushにhookを仕掛ける
  12. vi ~/awesome-app.git/hooks/post-receive
    chmod +x ~/awesome-app.git/hooks/post-receive
    

    ~/awesome-app.git/hooks/post-receiveの中身はこんな感じ。git pullしてbuild/migrateしてRailsをrestart

    #!/bin/sh
    (
    cd /home/git/deployed/awesome-app &&
    git --git-dir=.git pull &&
    bundle install --path vendor/bundler &&
    RAILS_ENV=production bundle exec rake db:migrate &&
    RAILS_ENV=production bundle exec rake assets:precompile &&
    touch ./tmp/restart.txt
    )
    

以上で、git push production masterとやればデプロイされるようになりました。
Herokuみたいにちゃんとやるなら他にも色々やることありそうだけど、とりあえずヤッター!

『フカシギの数え方』の数え方

狂気を感じる動画として一部で話題になった『フカシギの数え方』

僕も数えてみます!

数え上げ問題なので、まずは定石通りに、問題の状態を数値で表現してみて、それぞれの状態から何通りあるかと考える方針でいきます。

この状態を表現するのに、どのような情報が必要でしょうか。

以下の情報があれば、この状態からゴールまでの通り方の数は一意に決まりそうです。

  • 現在地: (2,2)
  • もう通れない点: (0,0), (1,0), (2,0), (2,1), (1,1), (1,2)

ここからの行き先ですが、左と上はもう通っている点なので行けません。
残りは2通りです。

それぞれ、同じように「現在地」と「もう通れない点」から状態を表現できます。

また、この状態だとどうなるでしょう。

すでにゴールに到達してます。
この状態からゴールまでの通り方の数はもちろん1通りです。

以上から、各状態からのゴールまでの通り方は再帰的に求められます。

  1. 現在地がゴールなら、1通り
  2. そうでなければ、上下左右それぞれに(進める場合は)進んだ状態からのゴールまでの通り方を足し合わせる。

具体的なコードはたとえばこんな感じです。
コード例では、「もう通れない点」の集合を楽に表すためにビット演算を使っています。
座標(0,1)と(0,3)をそれぞれ2進数で0001, 0100などと表すと、(0,1)と(0,3)の集合を0101として1つの整数値に押し込められます。

#include <iostream>
 
const int DX[] = {0, 0, -1, 1};
const int DY[] = {-1, 1, 0, 0};
int W, H;
 
// 座標(x, y)をビットで表す
long long bit(int x, int y) {
  return 1LL << (y * W + x);
}
 
// 現在の座標と通過済みの座標集合から、パターン数を返す
long long dfs(int x, int y, long long visited) {
  // 既にゴールにいるなら、そこからのパターンは1通り
  if (x == W-1 && y == H-1) return 1;
 
  // 現在地(x, y)を通過済みとしてマークする
  visited |= bit(x, y);
 
  long long res = 0;
  // 4つの隣接点でまだ通過してない点があれば、そこに進んだ場合の
  // パターン数を合計に加える
  for (int i = 0; i < 4; i++) {
    int next_x = x + DX[i];
    int next_y = y + DY[i];
    if (next_x >= 0 && next_x < W && next_y >= 0 && next_y < H) {
      if (!(visited & bit(next_x, next_y))) {
        res += dfs(next_x, next_y, visited);
      }
    }
  }
  return res;
}
 
int main() {
  std::cout << "横は何分割? : ";
  std::cin >> W; W++;
  std::cout << "縦は何分割? : ";
  std::cin >> H; H++;
   
  long long ways = dfs(0, 0, 0LL);
 
  std::cout << ways << " だってよ!" << std::endl;
}

結果はこんな感じ。6×6に2分半かかったので、7×7は数百時間にはなりそうです。

$ clang++ -O3 main.cpp && time ./a.out 
横は何分割? : 6
縦は何分割? : 6
575780564 だってよ!

real	2m37.630s
user	2m37.058s
sys	0m0.035s

4分岐で再帰の深さは最大W*Hなので、ざっくり計算量はO(4^(W*H))でしょうか。
最先端アルゴリズムだとちょっぱやらしいので、しばらく考えてみたんですが何も思いつきませんでした!
(それを探して来た人ごめんなさい >< ) 続きを読む 『フカシギの数え方』の数え方

Octopress試した / そうだ競技プログラミング用にしよう

Octopressっていうブログツールが

  • テキストエディタ, git, rakeで投稿が完結するらしい
  • markdown記法で書けるらしい

といかにもプログラマ向けっぽくてデザインもフォントとか好みで気になってはいたのだけど、ruby 1.9.2が必要だったので面倒な気がして放置してました。(Macでrvm使って入れようとすると怒られた)

が、EUROの合間に一念発起してインストールしてみた。

セットアップ

(0) rvmのインストール

$ curl -L get.rvm.io | bash -s stable --ruby
$ source ~/.rvm/scripts/rvm

(1) ruby 1.9.2のインストール

$ rvm install 1.9.2 --with-gcc=clang

で一応入った。なんか警告されたけど今のところ問題ない。

(2) Octopressを取得

$ git clone git://github.com/imathis/octopress.git octopress

(3) Octopressをインストール

$ cd octopress
$ gem install bundler
$ bundle install
$ rake install

(4) 適当に記事を作る

$ rake new_post['Hello, Octopress']

これで、source/_posts/YYYY-mm-DD-hello.markdown みたいなファイルができるので、それをmarkdown記法で編集する

(5) Previewする

$ rake generate
$ rake preview

ブラウザで http://localhost:4000/ を開けばどんな感じになるか確認できる

(6) サーバにアップロードする準備

今回はrsyncで自前サーバにアップロードする方法を採りました。公開鍵の登録とかは先に済んでいてパスワードや秘密鍵指定無しにrsync可能になっていれば、下記Rakefileの編集だけ。

$ vi Rakefile
ssh_user       = "user@domain.com"
document_root  = "~/website.com/"
rsync_delete   = true
deploy_default = "rsync"

(7) サーバにアップロードする

$ rake generate
$ rake deploy

(8) ブログソース(*.markdownとか)をgithubでバージョン管理する

githubにquizblog.gitを作って、そこで管理することにしました。

$ git remote rename origin octopress
$ git remote add origin https://github.com/fuqinho/quizblog.git
$ git config branch.master.remote origin

(9) ブログソースの編集をcommit & push

$ git add .
$ git commit -m 'hogehoge'
$ git push -u origin master

あとは(4),(5),(7),(9)の繰り返しのはず

感想

ブログソースがテキストファイルなので、管理は楽だし一括編集もしやすくてうれしい。
あとやっぱり静的ページはレスポンス早くて良い。負荷がかかればS3とかCDNに置いちゃえばいいし。かかれば。

なに書こう

とはいえ、今のWordpressのブログを移行するのは大変そう。

ということで、最近は毎朝1問、チャレンジブックの練習問題を中心に競技プログラミングのクイズを解くのを日課にしてるので、その解法とかを淡々と貼っていく場所にしようかと。ググって見つかった解法に何度もお世話になってるうちに、自分もちゃんと検索にひっかかる場所に書いてかないとという気になりました。

Octopressで作ったブログ: fuqinho@競技プログラミング

Sumtimerアップデートした (週次まとめビューとか)

前回のハッカソン中に間に合わなかった統計タブの週次まとめビューが、やっぱり無いと絵的に寂しかったので実装しました。

あわせて以下の点をアップデートしました。

  • 設定からCSV形式で記録エクスポートできるようにしました。エクセルとかで開く時用に。
  • ホームでアクティビティのアイコンタップでも計測開始するようにした。スマートフォンで押しにくい問題の暫定対応。

活動時間の記録アプリ作ってみた

一人ハッカソンを開催して、活動時間の記録アプリを作ってみました。

Sumtimer

Sumtimer

今から何やるか選んで、ストップウォッチ的に時間を記録して、後でレビューするためのツールとしてこしらえました。

ろくにテストもしてない状態で晒すのも…とは思ったのですが、できたところまでで晒す!っていうプレッシャーあってのハッカソンって気もしますし、

偉い人もこう言ってることですし。

Twitter/Facebookのアカウントで使えるようにしたので、試しに使ってみるかって方大歓迎です。
ただ、以下のような注意点があります。

  • データについて最低限の多重化はしていますが、万一消えた場合の責任は負いかねます。ごめんなさい。後でデータのExport機能(csv or Google Calendar)を実装しようかなと思ってます。
  • テスト・デバッグはこれからなので、とても不安定です。特にこの先数日は酷いことになってると思います。
  • バグ報告・要望とかもらうとより喜びますが、すぐの対応はできない可能性が高いです。

使い方はこのポストの下の方に。

発端

せっかく今は時間を100%自由にデザインできる期間なので、いつ何をやったかをメモ帳に記録するようにしてました。してましたが、さすがに3ヶ月もたつと「やってらんない・・・」となり、ようやく「今のままだと後で見直すのも大変だし、入力ももうちょっと楽にしたい」と思うに至りました。
多分表計算アプリにフォーム組んだりで改善しそうだし目的にかないそうなアプリやサービスも見つかりましたが、ちょうどRubyとRuby on Railsの本を読んだところだったので自分で作ってみるか、と。

で、やるからにはイベントチックにやったほうが楽しそうだと、(一人だけど)ハッカソンとしてやりました。
ロールプレイングゲームとかでも、発売日はいけるところまで一気にいくつもりでお菓子買い込んだりするのが楽しいですよね。ですよね。
ほんとは旅館とか行けるともっと楽しかったけど、さすがに一人を痛感しそうだったので自宅です・・・

感想

  • とにっかく楽しかった。今からやるぞーって買い出しに行く段階から楽しかった。
  • 最近input重視の勉強だったので、目に見えて出来上がっていくのはテンション上がったしいい気分転換になった。
  • 事前に学習してたRuby, RoRの知識の定着にかなり役立った気がしてる。というかあんま分かってなかったことがよく分かった。
  • 2日後に晒すのが前提だったので、思い付いた仕様の取捨選択に迷いがなくなって前に進めやすかった
  • RoR,Herokuの楽チンさがよく分かった。ちょっと慣れたので今後はもうちょい楽にプロトタイピングとかできると思う。(次はYesodかGAEに手を出したいけど)
  • これでメモ帳記録とサヨナラできる!
  • 両日とも夜には体中ガタガタだは頭痛するは大変だった。ほんと体力無い・・
  • ユースケース的にモバイルインターフェイス必須なのに手が出せなかった。残念。
  • UIやデザインを詰める時間も取れなかった。無念。

アプリの説明

ログインするとこんな画面になります。ざっくりとした分類でよければ(今から勉強するよ、とか)、学習一般の「開始」ボタンを選ぶと計測が始まります。

この画面で「いったん終了」を選ぶと今回の活動時間が記録されます。
何かメモがあれば(100ページ目まで読んだ、とか)、メモ欄に書いておくと時間と一緒に記録されます。
ちなみにこの画面でも開始時間は記録済みなので、ブラウザ閉じても大丈夫です。

こんな感じで履歴に残ります。
統計タブからは、文字通り統計情報を表示するタブです。が、今は指定したサブカテゴリごとの合計時間とかその程度です。

あと、ホームの「他のアクティビティを探す」からより具体的な活動を選べます。
Amazonの検索結果をマージしてるので本とかは見つかりやすいと思います。

「登録」を押すと登録画面へ。ちまみに「詳細」のリンクからAmazonの詳細ページに飛べますが、アフィリエイトタグを仕込んでます。さあ踏んで下さい!

登録する時は、タイトル・カテゴリー・サブカテゴリーは変更できます。自分にとってわかりやすい感じにするとよいかもしれません。
「マイ・アクティビティに登録する」を選べば、ホーム画面に表示されるようになります。

検索で見つからなかったり、独自のアクティビティ(僕の場合は「Sumtimer開発」とか)があれば、ホームの「自分でアクティビティを作る」で作成できます。

「アクティビティの再利用」にチェックを入れると、他の人の検索にヒットして登録できるようになります。「サイクリング」みたいな一般的なのを作る時はチェック入れてもらうとうれしいです。画像はjpg, gif, pngの2MBまでなら使用できます。(無くても大丈夫です。次の画面みたいなアイコンになります。)

実装した画面は以上かな…
自分で使ってみつつ、デバッグ・機能改善していきたいと思います。

あと、とにかく楽しかったし、作りたいものはたくさんあるので、1〜2ヶ月に1回くらいのペースでまたハッカソン出来るとよいなと思いました。

使用した言語・ツール・プラットフォーム等:
Ruby, Ruby on Rails, OmniAuth, carrierwave, JavaScript, Twitter bootstrap, Amazon Advertising API, Heroku, Amazon S3