七転八転

よしなしごとを。

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

前置き

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

本文

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

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

ボードゲームをしました

はじめに

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

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

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

総評

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

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

メモ（前半のみ）
  • ギリギリカレー

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

  • シャドウレイダーズ

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

  • 死ぬまでにピラミッド

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

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

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

東北を彷徨う

旅行

GWに旅行した。

コンセプト

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

旅程

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

メモ

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

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

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

競プロ
前置き

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

取り上げるもの

変数 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:と思ったが、今カリキュラムを見たらそれっぽいのもあった。

遠く楽しき沖縄

旅行

いつもの旅行メモ。

コンセプト

年始を優雅に沖縄で過ごす。車なしで頑張る。
バスで頑張る人向けに系統番号をちゃんとメモっておく
（大して頑張ってないが）。

旅程（1/5～1/7）

1日め：羽田→那覇
2日め：那覇→本部→今帰仁→名護
3日め：名護→那覇→糸満→南城→那覇→羽田

メモ

1日め
  • 羽田発。初のP28旅割。
  • 遥か昔クラスJに乗ったイメージで乗ったら、CAが挨拶にくるわ、お食事は出るわでドキドキした。
  • お食事でるのしらなくて、羽田でそばを食べていた事案。
  • 那覇空港。ゆいレールへ。
  • 「県外のICカードは利用できません」。はい。
  • バス、モノレール使いたおすならOKICA買ったほうが楽。
  • 首里駅へ。そのまま首里城へ。
  • 小雨。最近の旅行、天気に恵まれない。。。
  • 独特なイベント、文化が連綿と続いてきたのだなあと。（内地のことをたいして知っているわけでもないが）
  • 昼飯を食べようと沖縄そば屋にいくが、激混みのため断念。
  • 牧志でおりて、国際通りで昼ごはん食べることに。
  • A&Wバーガーにいく。せっかくだから、俺はこのルートビアを選ぶぜ。
  • めちゃ甘シップ味。美味しい。
  • 宿（美栄橋の方、ちょっと遠い）に荷物を置く。
  • 公設市場へ。サーターアンダギーを仕入れる。
  • 幸せですね。あげものなので出来たてが一番だと感じた。
  • もうちょいなにか買えばよかった。
  • ポーク玉子おにぎり。とても東京に輸入したい。そういえばセブンで置いていたけど最近みない。。。
  • チキナーとか油味噌とか。
  • 晩御飯は中身汁定食だった。
  • ファミマでそれっぽい限定品をあさる。黒糖ポーポー。
2日め
  • ATMでお金を下ろすと、懐かしのアレが3枚も（2000円札）
  • 朝の高速バスで美ら海水族館まで(117系統)。
  • 美ら海。水族館の人気って何で決まるのだろうか。
  • ジンベエザメ、マンタとかのでっかい水槽。
  • バスの時刻表に行動が支配されるので、やや面倒。
  • 今帰仁城跡入口までバス（65系統）。そこから頑張って歩く。
  • 壁が独特だよなと。見晴らしもよくていいところ。
  • 名護バスターミナル（BT）に戻る（65系統）
  • チェックイン。市街からちょっと離れ気味なんだよなあ。そもそも宿少ないけど。
  • 晩飯は豆腐チャンプルー。うまかた。近くにあったら通っている。
3日め
  • 朝の名護BT。人少ない。
  • 後、僕の勝手な想像としてバスターミナルって建物があって、いくつかお店があるイメージだったけど、

そんなことないので注意（駅前のロータリーみたいなイメージ）。

  • 名護BT→那覇空港（110系統）120系統というバスもあるが、これは延々と下道を通る。
  • 那覇空港のコインロッカーにリュックを放り込む。
  • 那覇BT→糸満BT(89系統)
  • 始発から乗ったら、ぐるっと市内を一周してからバスターミナルの前にもどってから糸満に行く便で泣いた。赤嶺とか小禄から乗りましょう。少なくとも旭橋。
  • 糸満。バスターミナルの周りで昼ごはんたべようと思ったら、ほぼ何にもなくて泣いた。
  • バスの時間に追われながら15分歩いて南部そばを食べる。
  • 必死に走ってバスに乗る。セーフ。
  • 真栄里入口→ひめゆりの塔前（82系統）
  • ひめゆりの塔。人の記憶が実感を呼ぶ。
  • それにしてもどんなところも観光地化してしまうものだ。。
  • 覚悟をきめて、平和祈念公園まで歩く。雨。。。
  • 平和祈念公園。まずは知ること。
  • 平和祈念堂入口→玉泉洞前（82系統）
  • 玉泉洞。あんまり興味ない城下町もろもろがmustでついてきます。
  • 洞窟はきれい。
  • 全体的に商売っ気が強くて、ちょっとつらかった。まあそもそもテーマパークなんだろうな。
  • エイサーはよかった。
  • 那覇に戻る。玉泉洞前→上泉（83系統）
  • そのままゆいレールで空港まで。
  • 空港食堂で最後のご飯。フーチャンプルー。安いうまい沖縄っぽいでよい。
  • 帰る。