七転八転

よしなしごとを。

北陸旅行

夏休みに旅行した。

コンセプト

鉄道成分多め。UFOと温泉とご飯(のはずだった)。

旅程

1日め:長野(帰省)→金沢
2日め:金沢→高岡→越ノ潟→(新能町→能町)→氷見
3日め:氷見→城端→(新高岡→上越妙高直江津)→越後湯沢→東京

メモ

1日め
  • 実家から直接金沢に向かう。
  • 夕方、金沢着。以前21世紀美術館に行ったときは夜営業していたので、てっきり空いていると思っていたが、金・土のみしか夜間営業していないことに焦る。
  • 慌ててバスで直行するも、チケットカウンタ激混み・・・
  • コンビニで当日チケットも買えることがわかり、ダッシュで買ってくる。危ない。。。
  • 「起点としての80年代」をみた。現代に向かって抽象度が高くなってくるんだけど、なんとなくぼんやり見てみる。
  • でも、作者っぽさがちゃんとあるのが面白い。
  • 例のプールは当然混んでいた。
  • そのまま近江町市場でご飯。
  • 旅行のときに酒飲まなくなった。
  • 歩いて駅前まで。ホテルに。
  • 寝る。
2日め
  • 時間がありそうなので、兼六園へ。素直に香林坊の方に宿とっとけばよかった。
  • 無料開放中。よきかなよきかな。
  • そのまま金沢城公園へ。
  • 香林坊からバス乗ろうと思ったが、やっぱり金沢駅まで歩ききってしまった。
  • 七尾線羽咋コスモアイル羽咋)→和倉温泉に…と思ったら、なんと七尾線が大雨で運休に。
  • 16時和倉温泉→氷見のバス(わくライナー)が最終であり、14時くらいまでは動かないとのアナウンスあり、なくなく見切る。
  • 三セクをたどって、高岡から回ることに。
  • こっちも危険っぽかったが、徐行運転あるも、なんとかセーフ。
  • 高岡。空いた時間でなにするか考える。明日乗るつもりだった城端線も運休。。
  • しょうがないので海王丸を見に行く。万葉線でのんびり。当然終点まで行く客は私だけ。。
  • 幸いにも雨は小ぶりであった。新湊大橋雄大
  • あまり時間もなく、引き返して氷見線に。
  • 氷見。宿が遠いんだ。。バスも期待できず2kmくらい歩いてしまった。
  • 番屋街で飯くおうと思ったら、店ほとんどしまってるし・・・何故だ・・・。
  • 適当に寿司とか買って(泣)ホテルで食べる。
3日め
  • バスをうっかり乗り過ごし、早足で氷見駅まで・・・
  • なんとかセーフ。氷見線城端線城端駅。
  • 善徳寺とかみて、ふらふらする。 夏が映える。(暑かったけど)
  • どことなく小布施に似ている気がした。
  • あとはひたすら列車。
  • 新幹線→越後はねうま→ほくほく
  • 越後湯沢のぽんしゅ館で利き酒。
  • 帰る。
備考
  • 天気!!!天気!!!!

最近プロコンではまったこと:スタック領域

前置き

最近プロコンではまったことをメモる。

本文

普段の環境として、MinGW GCC+Eclipse CDTでC++を使っている。
D - Mixing Experimentを解こうとしていたら、スタックオーバーフローらしき変な戻り値が返ってきて終了する。配列外アクセスとかを疑うが、そのような場所も見つからず。途方にくれてとりあえずsubmitしてみると、普通にサーバ上では動いているっぽく、悩む。
色々と調べるうち、DP用の配列(ざっくり50×500×500くらい)に対してスタック領域が足りてないのでは?という疑念を持つ。試しにstatic宣言してみると普通に動いた。なるほど。

毎回staticでヒープ確保しにいくのも嫌なので、
www.eclipse.org
これを参考にスタック領域を増やす。まあ。

ボードゲームをしました

はじめに

海外赴任中の友人が日本に帰ってきたので、ボードゲームをしました。

お品書き
  • ギリギリカレー
  • シャドウレイダーズ
  • 死ぬまでにピラミッド
  • テストプレイなんてしてないよ
  • 犯人は踊る

#珍しく5人揃った*1ので、ここぞとばかり5人で遊べるゲームを持っていった。

総評

過半数は自分の趣味で買っていったゲームでしたが、メンバーに好評で良かった。
ルールもそんなに難しくなく、気軽に楽しむのにちょうどよいバランスのゲームが揃っていたかなあ。
「テストプレイなんてしてないよ」が一番プレイ時間長かった気がする。

(もう少し重いゲームもやってみたい気もするけど、時間が限られる中で遊べるゲームの数が減ってしまうジレンマ)

メモ(前半のみ)
  • ギリギリカレー

鍋に具を追加していって、ちょうどよいタイミングでゲットするゲーム。
具にバランス値(コスト)、旨味値(ポイント)が設定されており、鍋のリミットを超えない範囲で具を入れていく。鍋の情報はほぼ開示されていない(最初に少しだけチェックできる)。自分がチェックした鍋を無難にしようとすると、みんなによってたかって具を放り込まれたりする。具等の効果がよくできており(例えば、りんごとはちみつが同数存在するとバランスはすべて0になる 等)、楽しめた。

  • シャドウレイダーズ

正体隠匿しながら、相手陣営を全滅させるゲーム。
各キャラには特殊能力があり、個性がでる。例えば、探偵カードといって正体に関する情報が得られるカードがあるのだが、それに嘘をついてよい 等。ドキュメント(能力効果の説明文・説明書のFAQ)が丁寧で、困りそうな点がきちんとフォローされていたのがよかった。装備だったり、運だったりで、2対1くらいだとひっくり返ってしまう可能性が高いように思えた。

  • 死ぬまでにピラミッド

大きくて美しいピラミッドを作るゲーム。
親相当の人が人数+1個のサイコロを振り、ピラミッドの部品を仕入れる。親から順に部品を取っていき、取り終わったら親が移動して続ける。ある特定部品が切れたら終了。得点計算が直感的にわかりずらく、「この変な形のピラミッド、私のきれいなピラミッドと同点なの」みたいなことが起きる。

5個書くのはしんどいので、またこんど。

*1:人望がないので5人で遊ぶのが大体困難

東北を彷徨う

GWに旅行した。

コンセプト

東北でまったり自然を巡る旅。

旅程

1日め:東京→気仙沼→大船渡
2日め:大船渡→遠野
3日め:遠野→仙台→東京

メモ

1日め
  • GWの終わりの方で出発(GW最後2日+GW最後-1日*1を利用)
  • 一ノ関まで新幹線。意外と近い。はやぶさとやまびこだと30分位違う。
  • 一ノ関から大船渡線。外が大雨だったので焦る。
  • 気仙沼。晴れてて助かった。
  • 駅前で自転車を借りる。最後の1台だったとのことでセーフ。
  • 海の市へ。昼食をくおうと思ったが、GW中ともあり、さすがにまだ混んでる。
  • 一回リアス・アーク美術館まで行ってから帰ってこようかとも思ったが、さすがに回り道すぎるという理由で並ぶ。
  • まぐろ丼を食べた。私の馬鹿舌では良し悪しはわからんがおいしかった。
  • あと外の屋台で焼き牡蠣を食べたのだが、非常に好きだった。大きくて肉厚。
  • 気合を入れてリアス・アーク美術館まで自転車であがる。
  • 一般展・震災記録展をみる。被災した方から見た支援への考え方とか、そういったものが記録として残してあるのが、記憶に残った。
  • 気仙沼駅に戻る。
  • BRTで大船渡へ。専用レーンに入るとちょっと感動。
  • 如実に道が新しくなっている所があり、逆に震災の影響を感じる。
  • これに限らず、まだまだ道路工事をしている場所が大量にあった。
  • ホテル着。大変きれい。
  • 近くのキャッセン大船渡でご飯を食べる。
  • スーパーを冷やかしに行く。
  • 寝る。
2日め
  • 朝大船渡発。せっかくなので盛まで徒歩。
  • 三陸鉄道
  • 釜石。寄ってみたかったが、そのままJRに乗り継ぎ。
  • 遠野。
  • 駅前で自転車を借りる。
  • 概ね町中は平坦だが、山口の水車やたかむろ水光園の方は登りなので、アシスト付きがよいかも。
  • 私は最後へとへとになりました。
  • 小さい町なので、どこでご飯を食べるか悩み、まずは道の駅まで行く。
  • ジンギスカン+ひっつみ。うまい。
  • 主要な立寄り地として、松崎観音、福泉寺、伝承村、カッパ淵、市立博物館あたりにいった。
  • とぴあで買い出しして宿に。
  • 疲れ果てて寝る。
3日め
  • ほぼ帰るだけ。新花巻で乗り換え。
  • せっかくなので仙台によって、牛タンを食べる。
  • 帰る。終わり。

*1:月曜日を意味する。最後とは・・・みたいな雰囲気をだしたかった

典型的アルゴリズムについて(2)

前置き

プロコンの典型アルゴリズムに関する記事(第2回)を書く。

取り上げるもの

変数 x_{i} \in \{0,1\}, i = 0..nについて全探索をすること。(bit全探索とかいうのでしょうか?)計算量は当然変数の数に対して指数オーダなので、大規模な問には使えない。

例えば下記が例題となる。
No.43 野球の試合 - yukicoder
総当たりリーグ戦が途中まで終わっている状況で、残りの試合が終わったとき、指定のチームが最高何位になれるかを求める。これはまだ試合していない所について、勝敗の組み合わせを全通り試せばOK。

サンプル
for (int i = 0;i < (1 << M);i++){
	for (int j = M-1; j>=0 ;j--){
		if(i >> j & 1){
		}
	}
}

M個の変数についてこれで探索できる。初めてみた時はちょっと面食らった。
 iは、長さMのbit列に対応する。例えば M = 2としたとき、 iは0から3となり、bit表記するとそれぞれ \{00,01,10,11\}となる。これはすなわち2変数のとりうる組み合わせを列挙している。
 jは、左から順にbitが1であるかを判断している。

例題の場合

#252912 No.43 野球の試合 - yukicoder
先の例題はこんな風にとける。順位を計算する所の書き方がしっくりきていないが、リーグ戦で未試合の部分を見つけて、勝敗について全探索する。

ボードゲームをしました

はじめに

ボードゲームカフェでボードゲームをしたので、感想をメモしておく。

お品書き
  • コルトエクスプレス
  • キングドミノ
  • ブラフ

#そういえば、全てドイツゲーム大賞受賞作である。

メモ
  • コルトエクスプレス

 一回プレイしたことあるはずなのに色々忘れており、インストに苦しむ。
 盗賊となり、列車の中でお宝をたくさん取った人が勝ち。計画→実行という流れで、計画では、手札の行動カード(列車をうつるとか、お宝を強奪する、相手を殴るとか)を、各プレイヤが順次出していく。行動カードは原則公開だが、非公開となるタイミングがあり、これが予想外のずれをうみだす(これがキモ)。実行で、計画で出したカードを順次処理していく。
 このゲーム、頭の中で各自の行動をシミュレートできる人が強いので、プログラミングと親和性が高いのではないかと思った。(私は弱く、全く宝が増やせずに、盗賊ワナビだの清貧な盗賊だの言われた)

  • キングドミノ

 直近でドイツゲーム大賞を受賞しており、遊んでみたいと思った。なんとなくルールは知っており、適当にインスト。ヴァリアントルールはなし。
 1x2のタイルを順次とっていき、最大5x5の王国をつくる。タイルには地形(と点数にかかわる王冠)が描かれており、タイルをつなげる際は、どちらかの地形が一致している必要がある。勝敗は得点できまり、繋がった地形x地形に含まれる王冠数できまる。タイルの選び方に特徴があり、ある手番でいわゆる「いい」タイル(王冠が多いなど)をとると、次の選択手順が遅くなる。
 ついつい地形をつなげて悦に浸ってしまったが、地形数と王冠数との積できまるので、王冠数が少ないとゴミみたいな点数になる。(地形12マスx王冠1個と、地形4マスx王冠3個は同じ点数!)

  • ブラフ

 ニコ動のプレイ動画等で面白そうだと思い遊んでみようと思うが、ルール説明がドイツ語で書かれており無事死亡。気合でルールを思い出しインストすることで、なんとか遊べるレベルに至る。
 ダイスを一人5個もちで、他者にわからないようにふる。プレイヤは全員の出目の数を予想する(5が7個と か)。次のプレイヤは、それ以上の出目の数を宣言するか、ブラフを宣言する。ブラフを宣言した場合、全員の出目を公開して、予想が嘘だったかを確認。嘘だったら、出目を宣言した人のダイスを減らす、本当だったら、ブラフを宣言した人(と場合によってはその他の人)のダイスを減らす。ダイスが残っていた人が勝ち。
 なお、一箇所ルールが不明な所があって、後で調べたら間違っていた。。。(BoardGameGeekで英語の説明を読んだ)ブラフをかけた次のラウンドの開始プレイヤがわからなかったが、これは、前ラウンドでの勝者であった。(すなわちブラフに成功した場合成功した人、失敗した場合出目の予想を宣言した人)
 ひっかけ方のパターンはそれなりに決っているので、知っておいてたまに使う感じ。例えば手元にない出目を宣言して数が釣り上がった所でブラフするとか。シンプルだけど面白い。

自習について

はじめに

 ちまたで流行しているMOOCというものを体験してみたく、ちょっと勉強をはじめた。経緯について少しメモしておく。

サービス、講座の選定

 いまかじっているのはudacityの以下の2コース。

 最初にやってみたいことを考えて、Image Recognitionに関する講義を探していた。はじめはcourseraで探していたがドンピシャなコースが見当たらなかった(?)*1ので、udacityにシフト。udacityでは、"Introduction to computer vision"というドンピシャなネーミングの講義を発見したので、これを受け始めた。
 後者は、前者のコースに飽きてきたので、目先を変えておもしろそうかつ私が知らないことという観点で選んだ。

受講について

 "Introduction to computer vision"は、なかなかボリューミー(そもそも大学の講義なので)。講義自体は前提知識も少なく、すんなり理解できる内容。今まで受講した範囲としては、

  • 画像:関数として表現できる
  • フィルタ(ノイズ除去など):画像に対して関数の畳み込みとして表現できる(e.g. ガウシアンフィルタ)。
  • 物体検知:関数の畳み込みとして実現可能。
  • 辺検知:画像のgradientに着目すると可能(白・黒が急激に変わる→傾きが大)

くらい。(全然進んでない・・・)
 途中課題として、簡単な小クイズと、MATLABを使った簡単な実装がある。MATLABは本来有料ソフトウェアだが、ブラウザ上にて無料で実行可能。

 "Introduction to HTML and CSS"は講義レベルがbeginnerということもあり、さくさく進んでいる。もうちょっとで終わるが、やったことは

  • HTMLとCSSの構造
  • HTML、CSSの編集
  • bootstrapを利用したHTMLページの構築(gridへの切り分け、ドキュメントの読み方等)

あたり。bootstrap使うとそれっぽいのが簡単にできるのだなあと。
 途中課題としては、簡単なクイズ。例えば、必要な機能を実現するbootstrapのクラスは何か?等。

おわりに

 がんばるぞー。
 

*1:と思ったが、今カリキュラムを見たらそれっぽいのもあった。