パスワードを忘れた? アカウント作成
12380696 journal
日記

Yak!の日記: Maker Faire Tokyo 2015 メモ

日記 by Yak!

今更ながら 8/1(土)、8/2(日)に東京ビッグサイトで開催された Maker Faire Tokyo 2015 のメモです。参加したのは 8/2(日)、その週で前売り(大人1000円)を購入しての参加でした。Make 系イベントは Maker Faire の前身 Make Tokyo Meeting からちょこちょこ参加していて多摩美術大学→東工大→日本科学未来館と会場の規模がでかくなってるなぁと思っていたのですが、遂に東京ビッグサイト!とか思っていたら去年もそうだったみたいですね。一昨年からの差の印象になってしまいますが企業ブースが結構大きかったのとその中でも Intel 頑張ってるなぁというのがまず大きな印象でした。あとパンフレットの表紙にもありますけど「家族連れ」をターゲットにした広報は規模拡大に貢献してそうな気がします。実際、動いてるだけで楽しい、という小さなお子さんは「面白そうなのでとりあえず作ってみる」という Maker の中では結構大きいと思われる派と相性がいいはず。

前述の通り、この手のイベントにちょこちょこ参加はしていますが、ぼっち参加でもあり、どうしても浮いてるというか馴染めない感が残るタイプだったのですが、今回比較的色々と話ができたと思います(あくまで自分内比較)。最初に、台湾から来てた人にカタコトで英語で話しかけてハードル超えたのが良かったのかもしれません。以下、順不同でいくつかコメント。

企業系
なんでこんな企業多いんだろうと思ったら IoT 関係でってことみたいでした。ただ増えてる分の企業展示は Maker のイベントということもあってかフレームワーク系のもの(何かを作るための環境)が多くて「いまいち感」はありました。正直「フレームワークなんてなんだっていい」「とっとと一つにまとめてくれないかな」が正直な感想だと思うんですよ。何を作るかに意味があるのであってどうやって実現するかはなんだっていいというか。この辺、恐らく垂直統合にはならないので、逆に外から無理やり水平分業に持っていったところが勝つんじゃないかなぁという気もします。

HUIS
他の赤外線リモコンの内容を学習できて電子ペーパーで表示の内容もカスタマイズできるリモコン。クラウドファンディング中ということで頑張って宣伝してました(2015/8/14 現在達成済みで継続中)。悪くないかな、と思ったのですがこの後知った IRKit (WiFi 経由で制御できる赤外線リモコン) の方がスマフォを UI に使えたりプログラムから制御もできるし自由度高くていい気がします(っていうか IRKit 買いました)。まぁ単体で完結するのは一般向き?

スーパーLチカコンピュータ
ICを使わずLEDだけで作ったコンピュータ。ニコニコ動画でタイトルだけ見て動画未視聴だったのですが実物見てきました。こんなことができるという事(DTL)自体知らなかったわけですが、超「コンピュータ」って感じですよ。ボード1枚分でDIP SW満載のROM部分が圧巻。

Galaxy360×Area360
スマフォVRで世界各地の全周囲画像表示。Googleが段ボールのスマフォVR箱を出していることは知っていたのですが初体験。というか知っていたけど結びつきませんでした。箱いゴーグル状のものを覗いて左右360度だけでなく上下に振ってみてもちゃんと追随するのに「うおおぉ」と思って「これどうやってるんですか?」と聞いたら「スマフォです」との答えでこれが例のとやっと思い至りました。思っていたよりも全然いけますね、これ。ということで帰宅後 milbox 買っちゃいました。

おなかの現実
締めることで胴回り+圧力を図れるベルト。確かにわざわざ測るって面倒くさいんですよね。これが体重でできないかなぁと思ったりもするわけですが。体重が測れる椅子はチームラボの人が作ってた気がします(この辺)。椅子だと条件がきついので玄関マット的なものでできないかなぁ、とか。

RE_ACCEL
DIY 電動カートの作成。みんなで何かを作ろうというのに電気自動車だと作るのが大変なので電動カートを作成、とのこと。実際動いてるところも見られて「すげーはえー」(小並感)。いくつか質問して回答して頂いたのに詳細を忘れているという体たらく。確か6人チームで、期間、費用についても思っていたよりかからずにできるんだという印象でした。

AirWitch
スマフォを置くことで空中映像を表示できるキット。スマフォでホログラムだとつい最近CDケースで工作するネタが話題になっていましたが、それとは異なり中空に表示されているように見えます。こればっかりは現物見ないと分かりにくいですが、公式サイトの動画より元になっている技術の研究室の動画の方がまだ分かりやすいかもしれません。で、中空の映像に触ると挙動を変えることもできる、と(これはスマフォのカメラで認識)。スマフォVRもそうですけどスマフォってセンサの塊でもあるし便利なデバイスだなぁと再認識。

「プロジェクター用動画の自由変形」ソフト
プログラムに載っているタイトル「立体地図に対するGIS情報のプロジェクションマッピング」と展示内容が大分違うということに今気づいた訳ですが、まぁ投影面に合わせた動画の変形という意味では技術ソースは同じなんでしょうか。内容としては、動画の四隅を自由にドラッグで動かせてその四角形に合わせて表示するソフト、なわけですがプロジェクタの表示調整というと光学系調整がベースで対称な調整という頭があったので「その発想は無かったわ」という感じでした。こっちの方がはるかに直観的です。もちろん解像度の均一性とか犠牲にしているものはありますが、そこに拘る必要のない用途の方が多い気がします。ドライバ層とかでできると嬉しいかも。デスクトップ OS のマルチディスプレイの設定だと複数ディスプレイの位置合わせができますが、これがミラーリング時だとミラー側表示の4隅が動かせるとか。

プレゼンテーション「実際のハードウェアスタートアップ」
ハードウェアスタートアップを立ち上げた3人に対して実状を聴こうという企画。雰囲気メガネだけちょっと聞いたことあったかも。ここで IRKit の話を聞いて速攻で購入しました。それだけでも意義があったわけですが(本題と違う)、3人中2人がハードウェア初めてというのは驚きでした。その分、人の繋がりが大事というか、自分一人ではできないので知見のある人に協力してもらうことが必要というのが一番印象に残ったことでしょうか。小さく生むのであればそんなに費用かからないでできるものもある(IRKit の当初自己資金投入は 150万)というのも自分にとっては新しいものでした。

プレゼンテーション「5億人が必要とするバイオ機器を自宅で作る」
20分のプレゼンですがぶっちゃけ感銘を受けました。My best in Maker Faire Tokyo 2015。「Maker Faire で何に一番興味を持たれたのか知りたい」みたいなことを言われていたのでそれでこれ挙げちゃ駄目じゃん感がありますが。ARによる人工衛星の位置トラッキングアプリから始まってDNA増幅器の生産にまで繋がる流れを駆け足に紹介という感じだったのですが「世の中すげぇ人居るな」というのが率直な感想でした。資料を探したのですが上がっていないようで、TEDxTokyo 2014 の記事が割と内容近いかもしれません。自分も何かやらなきゃ、と思える素晴らしいプレゼンだったと思います。

メントス×コーク大噴水ショー
Amazing Science の表紙にもなってる例のアレです。メントス×コークやるなら成功しても失敗しても両手を挙げろ、べたつかないからダイエットコークおすすめ、温度高い方が高く上がる(実演あり)、とか有りましたが、まぁ細けぇことはいいんだよ\(゜∀。)/でいいですよね、うん。結構人集まってましたし、そして思っていたよりも楽しかったです。通訳の方もいい仕事をしてたと思います。

総評
総じて楽しかったです。行って良かった。受け身で自堕落側になりがちなので何か作ろうという刺激を受けられただけでも良かったと思います。余波で色々とぽちってしまいましたがそれはそれで。

番外
Facebook による買収前(1年半くらいも前ですね、びっくり)に Oculus Rift DK2 を買うだけ買って眠らせていたのですが Maker Faire 直前くらいに開梱して動作させてみたら PC が非力でちょっとがくがくしてました。ということで実演展示をしている G-Tune : Garage に行ってきました(今調べたら名古屋店舗でもやってるみたいですね……)。試したのは UnityCoaster2 Ver G-Tune でしたが、凄いですわ。重力を感じる。勝手に左右に体が倒れる感じで、立った状態で着けてましたが机のへり握ってなかったら倒れてたかもしれません。ということで、しばらくメインPC(ノート)を変えていなかったこともあり NEXTGEAR NOTE i5702 購入してしまいました。

10214278 journal
日記

Yak!の日記: 叛逆の物語 感想 2

日記 by Yak!

とりあえずどこかに吐きだしておこうということで、魔法少女まどか☆マギカ 新編 叛逆の物語のネタばれメモ、感想をつらつらと。最速上映、次の日の朝、フィルム配布後の3回見た後のものです。見るのが怖くて他の人の感想はほとんど見てません。Pixiv くらいは見られるようになりました。なお、映画見たい方はもう既に見た後ではないかと思いますが、これからご覧になる方は、パンフレットは絶対に買って、鑑賞前は見ずに、一度自分で感想をまとめてからパンフレットを読むのをお薦めします。では以下ネタばれ。

総評: 最速上映視聴組で、その時点で次の回も予約してしまっていましたが、終了後「どうすんだよこれ」という感じで色々とヘビーであり色紙だけもらって視聴スキップしようかとまで考えましたが、パンフレット見て2回目視聴して受け入れられる気になりました。「世界は広げておいてやった。後は好きに妄想してみろ」という公式からの挑戦状ですよ、これは。まどか☆マギカの世界は続けたいみたいなことは言われていましたが、まどかとほむらについてはある程度決着が付くのではないかと予想あるいは期待していたのですが、こう来るとは。ちょっとほむらに対してどS過ぎやしませんかね。今回は虚淵氏ではなく新房総監督等が発端みたいですが。新房総監督はインキュベーターの逆襲というタイトルを付けたかったという話は明らかになっていたのでそれだけですまないよなと思ってはいましたが想像を超えてました。

まどほむ・ほむまど的視点: 公開前、まどほむスレでもただ単にお迎えされるだけだと他の子と同じじゃないかという意見を見ましたが、確かに対になる存在とも言える立場になったわけで特別ではありますね、うん。しかし仮に対決するとしてほむらが勝つ展開が全く想像できません。ちょっとまど神様が目に涙浮かべて「ほむらちゃん、どうして……」とか言ったらそれだけで無力化ですよ、多分。
まど神様から見ると、最高の友達が大ピンチだってんで、お供2人も引き連れてお迎えに行った上、「これからはずっと一緒だよ」というプロポーズ級の台詞を吐いたというのに、「あなたを救ってあげる」とばかりに自分の一部をひっぺがされた訳です。まど神様は怒ってもいい。でもあまり真剣に怒ってる姿が想像できないというか、どっちかって言うと自分を責めそうですよね。
ほむらが優位に立つとしたら、涙目のまどかの涙を舌で拭って「泣いているまどかもかわいいわ」ぐらい言ってのけるくらいじゃないと駄目だと思いますが、ラストで何も知らないまどかに抽象的な質問を一般的に答えられただけで涙目という体たらく。正にへたれ。だがそこがいい。
そもそも双方が相手に害をなす気がまるでないというか、むしろ相手のためなら自分の存在さえ捨てられるという勢いな訳です。ほむらの業が深いというか、まどかが幸せにならなければ自分が幸せになってはならない、という呪いをかけてるかのようで、一緒に居たいんだろ?特に何するでもなくただ側に居られればいいんだろ?、と思うのに、「これからはずっと一緒だよ」とまで言ってくれてるのに、それでも人としてのまどかの幸せを望む、と。あぁ、すれ違い。なので、最早双方とも時間を超越しちゃったわけですし思う存分直接対決っていうか「二人で良く話し合って」的に直接対話してもらえればいい気がするんですけどねー。ほむら自身もこれやっちゃうと負けるのは自覚してそうな気もしますが。とはいえまど神様がこの状態をずっと放置するとも思えず(一旦は「ほむらちゃんが望むなら」的に引いちゃうかもしれませんが)、なんとかほむらを幸せにして欲しいです。今回大活躍だったさやかちゃんが起点になると面白いですね。

最速上映: 東浦で見ましたが、23:00くらいに付くように行って、早く来すぎたかなと思ったら超並んでました。恐らく並び過ぎで場所が確保できないということで、23:30予定という告知でしたが23:05くらいから入場開始に。物品販売は整理券配布で No.188 でした。結局パンフレットしか買わないし別途見るつもりならそのときに買えば良かったんですけどね。で、整理券もらって一時退出。ちなみにこの回と次の日の朝もらった色紙は両方とも杏さやでした……。フィルムは宇宙。

雑多なメモ(時系列ばらばら):

  • マナー広告: 物語シリーズから忍野扇(CV:水橋かおり)、八九寺真宵(CV:加藤英美里)という俺得ラインナップでした。間は阿良々木火憐(CV:喜多村英梨)だったそうで声優の有効活用ですね。
  • OPで盛大なネタばれ: 某動画的には「○分で分かる叛逆の物語」でOPまま流してOKな勢い。2回目見ないと分からないネタもありますが、それ抜きでもあのOP見たらこりゃあかんと覚悟決めますよね。
  • 鳴き声: 何度見てもきゅうきゅう言うキュゥべえがあまりにもきもすぎ。顔面に拳入れたい。
  • Do you enjoy the movie?: スタッフの「おまえらこういうきゃっきゃうふふなのが見たかったんだろ?ん?ん?」みたいな煽りを感じたわけですが。えぇ、サニーデイライフ大好きです。
  • さやほむ: 二人で対峙するシーンは二回目見ると切ないです。本編では基本対立してるので特に。
  • さやかちゃん: 本編の不遇からは考えられない大活躍。株爆上げですが、活躍そのものもさることながら、マミ、杏子は別の世界のことを知らない、まどかは忘れているということで、立ち位置が視聴者に近いというのがある気がします。「同情せずにはいられない」とか「頑張った奴にはご褒美がなくちゃね」とか台詞に共感しまくり。
  • 飛行船: 大量に飛んでる飛行船はキュゥべえの観測機械の投影ってことですよね。
  • マミさん: 強すぎ。「あなたの魔法はすごいけど自分が絶対的優位に立っていると思わない事ね」とか言ってましたが普通どうやっても超えられない優位だと思うんですが。そりゃ本編でも強制退場させられますよ。そうそう、席立つ時にちらっと見えるリボンとか複数回視聴も面白いです。The Different Story のラストの台詞を思うとその前の独白「魔法少女としての生き方がこんなに満ち足りたものになるなんて(台詞適当)」も重い。この世界を誰が望んだのかを考えるとそれもまた切ないですが。あと「佐倉さんや暁美さんもこっちについてくれて」みたいなことも言うんですが、これ、記憶が朧気にでも残ってないと言えない台詞な気がします。それともこの世界観でも魔法少女ドンパチやってたんでしょうか。
  • 消火器: 拘束されたほむらの解放にさやかちゃんがやってきますが、あえて消火器を投げ込むファンサービスが憎い。
  • ほむら魔女: イメージが断罪人で処刑台まで自前用意とかどんだけ自罰的なのか。蓄音機のスピーカー部分みたいなのが付いててBGMはそこから出てるイメージだと思いますが、自分の場所を誇示することで早くマミあんに討ってくれってことだと思ってます。そして視聴3回目でようやく気付きましたが、紫の手(他の方の感想を見るにリボンみたいですね)は本体が処刑台に行こうとするのに抵抗したり、救出組に手を合わせて祈ってるけど本体はその手を叩き切ったり、全体と逆の行動してるんですよね。切ない。喪服ほむらは正に Homu"lilly" って感じで可憐ですが、咲いている彼岸花はそういう花言葉ですか。うあぁ。
  • 魔女大戦: たとえこの後ああなるとしても、やっぱり misterioso かかる魔女大戦は何回見ても胸熱になります。
  • ほむら: パンフで虚淵氏が「ほむらの成長」と書いていて、これを成長と表現するかとびびった訳ですが、今まで受ける一方だったのが世界に対して能動的に働きかけたという意味では、まぁそうなのかなと思わないでもないです。とはいえ、クーほむになってもリボほむになっても魔女になっても悪魔になっても、ほむらの本質はまるで変わってない気がします。「自分だけの時間に逃げ込むつもり?」と言われてましたが、自分だけの世界に、にすれば継続して適用できるんじゃないかという感じですね。まぁ自分の想いは出せるようになったので次は他人の想いとの調停でしょうか。そういう意味では今までまどか以外のキャラクターとは関わりが薄い感じでしたが、今回「私はあの人が苦手だった」以降のマミに対する思いだとか、杏子に最初に相談するだとか、さやほむ対峙だとか、色々と燃料が投下された気がします。
    蛇足ですが、花畑でまどかの前から走り去る時にものすごい女の子走りで切ないシーンのはずなのに半笑いになりました。
    もう一つ、ダークオーブにとかげのシルエットが有り魔女化のところでも下半身だけのとかげとか、魔女化最後のタイミングでも涙を流すとかげがでてだりとかしますが、この辺は他の人の考察とか読みたいですね。
  • ラストパート: この演出何なんだろう?と思っていたのですが、一人カラフル、一人ルミナスですか……。ほんとまど神様お願いします。キュゥべえ?ま、妥当な扱いなんじゃないですかね。せいぜい搾取される側に回ってください。
  • for the next episode: 総集編前後編で一番好きな BGM が for the next episode だったりしますが(さやほむ対峙でかかって嬉しかったです)、BGM の話ではなく。このままだと話終わらないだろってことで妄想向けにラスト辺りでいくつかメモ。杏さやは指輪、指のシンボルで魔法少女継続確定。マミさんは自分では確認できませんでした。仮にこれが「もう貴方は戦わなくていい」とかいう気遣いだったりすると何が悪魔だよという感じになりますが。杏子は同じクラスのまま。まどかに声かける時に他のクラスメイトが超引いててほむらはクラスで恐れられてそう。まぁ無理もない。

妄想: 各人各様で様々な妄想ができそうですが。前述の通り、直接対決するとそのまま終わりそうなので。まど神様の直接介入はまどかに影響を与え不安定な世界を壊しかねない。ということで旧魔女勢の皆さんがまど神様の意を受けて潜入することに。一方、ほむらは旧魔女勢をこの世界の秩序を乱す存在ということにしてこれに対抗する魔法少女を用意するのだった、みたいな。これだとカラクリが全部見えてる状態なので、キュゥべえの新たな計画が絡むとか。マミさんの魔法少女復帰とか、ほむら対信号機組とか色々と妄想が捗る訳ですよ。

と、吐きだしたところで漫画版見て感想めぐりでもしてきましょうかね。

4189390 journal
日記

Yak!の日記: "せいさいよだつ"の生殺与奪 5

日記 by Yak!

某コメントが流れる動画サイトで動画を見ていたところ、"せいさつよだつ"という台詞が流れてきた。普通にあぁ生殺与奪ね、と思ったら「せいさいだろ」みたいなコメントが。あれ?今まで間違ってた?と思ってぐぐってみたら辞書サイトでは全て「せいさつよだつ」表記であり、「せいさいだったのに今はせいさつになってる」みたいな話がちらほら。事例1 事例2 事例3

で、まぁ、普通だったら言語というものは変わるものだし今はせいさつになってるのね、みたいな納得の仕方で終わらせるところなのだが(せいさつで正しい、は変わらないので)、辞書から抹消するのはどうなのよ。 という tweet を見て、本当に変わってるのなら『「せいさい」とも。』と書く辞書くらいあってもいいだろうということでと思い立って市立図書館行って調べてみた(アニソン三昧聞きながら)。

  • 広辞苑 第3版 昭和58年12月6日(第1刷時)
  • 三省堂国語辞典 第6版 2008年1月10日(第1刷)
  • 学研現代新国語辞典 改訂第4版 2008年1月25日(初刷)

以上は「生殺与奪(せいさつよだつ)」の項はあって「せいさいよだつ」の言及はなく「生殺与奪(せいさいよだつ)」の項もなかった。とりあえず自分の年齢なら「せいさつよだつ」としか聞いていないだろうという感じであるがもうちょい古い情報が欲しい。ということで県立図書館にも行ってみた。

  • 大日本国語辞典 第11版 大正10年6月10日

とりあえず開架で一番古そうな物が↑だったのだが、「生殺(せいさつ)」の項はあって「せいさい」の言及はなく「生殺(せいさい)」の項もなかった。

大正10年(1921年)から昭和58年(1983年)の間にA→B→Aしてる可能性は0ではなく、県立図書館には1950~70年代の国語辞典もあったようなのでそこは押さえとけよという話ではあるのだが、まず「生殺与奪(せいさいよだつ)」は誤りで現在存命の人が生きていた時代で正しかった時期はない、と言っていいのではないだろうか?

1099177 journal
日記

Yak!の日記: 今更 blog 開設

日記 by Yak!

こんなところを見ている人も居ないと思いますが、C++11 Advent Calendar および Boost Advent Calendar を機に http://yak-ex.blogspot.com/ を開設しました。プログラミング、ソフトウェア関連のネタは(どれだけ書くかはともかく)以降そっちに書くと思います。

850491 journal
日記

Yak!の日記: 碧の軌跡 クリア感想

日記 by Yak!

とりあえず碧の軌跡クリアしたので雑多な感想など。

■総合

プレイ時間 123:15:34。寝落ちや放置も含んでると思いますが。獲得実績 34/56 2250pt。みーしぇのイベントだけ検索かけちゃいましたが他はノーヒント。結構頑張った方じゃないでしょうか。アニエス揃えられたのは嬉しかったですね。

なのですが感想というと、うーん。ラスト絵のところに空の軌跡の時のようにメッセージが出るんですが "Comletedly Finished" になってました。なんか違う。そぅ、クリア後の感想としてもなんか違うというかもっと良くできたんじゃないの?という気が。特に最後、単純に流れを見せられるだけなのはどうかと。同一世界観で話が続いていくのはともかくクロスベルの話としてはきちっとけりをつけてもらわないと。一旦エンドでその後プレイアブルにクロスベル解放してくれれば満足してたような気もします。

■ラストダンジョン

4つの「○の領域」を作る必要があったんでしょうか?作った割にあっさりしすぎかと。作るんだったらもっと各キャラクターの内面を掘り下げるべきだったような気がします。それこそ空の軌跡 the 3rd の扉みたいなものとか。中盤怒濤の展開でリーシャとシャーリィに因縁ができるわけですが双方ともサブキャラクターなわけでその後にもうちょっと何かが欲しかったと思います。リーシャの好感度が上がってるとイベントがあったのかもしれませんけど(エリィonlyプレイでした)。

もう一つ。Falcom さんはリアリティよりプレイアビリティを優先する、という方針なんじゃないかな、と思っています。ラストダンジョンでも途中でメルカバまで戻りやすくなってるというのはその顕れかな、と。ただメルカバ自体での移動までできるのはやり過ぎだったんじゃないでしょうか。せっかく突破イベントやってるくらいなんですからラストダンジョン入ったらもう戻れないくらいの方が緊張感があって良かったんじゃないかと思います。

後、最終盤の戦闘は相変わらず長かったですね。それも単純に長けりゃいいって思ってるわけじゃないですよね?とちょっと疑念を抱くような感じで。

■マスターアーツ

使いまくっておきながらなんですが、慈愛のルーンさんまじチート。防御系だと回数なのですぐ消えたりしてタイミングを計る必要がありますが継続効果があるというのが大きいですね。しかも終了して即時開始すれば HP50% 回復も選択可能です。ということで終盤の回復ポイント後の戦闘では使いまくってました。以前はアーツによる完全防御(アースウォールとかアダマスガード)は封じ手にしてたんですけどね。グラールスフィアとかは使ってましたが。まぁ何らかの手段を講じないと一撃死するのでもうしょうがないという感じです。

■その他

・誤字、脱字

これだけのテキスト量があれば誤字・脱字くらいあるでしょうが前作よりかなり気になりました。

・改善

「情報」で見えてる情報なのか色で分かるようになってたり、一部特殊クォーツが全体に効くようになってたり、インテリア揃えるとイベント発生したり細かい改善がされててプレイ当初感心してました。

337121 journal

Yak!の日記: C における一時オブジェクトの生存期間 6

日記 by Yak!

Twitter 上で C++ STL の vector に関して評価順序不定ではまっているコードの例が流れていてそこから C 言語における(規格上の)落とし穴に行き着いたのでメモ。

// from http://www.jpcert.or.jp/sc-rules/c-exp35-c.html
#include <stdio.h>

struct X { char a[6]; };

struct X addressee(void) {
  struct X result = { "world" };
  return result;
}

int main(void) {
  printf("Hello, %s!\n", addressee().a);
  return 0;
}

上記コードは C++ では問題ないコードであるが、一方 C99 では未定義動作を含むコードである。理由はJPCERT のページに記述されているが、

一時オブジェクトの生存期間(という説明は C の規格上はされていないが)が次の副作用完了点までだと規定されているからである。この場合 printf 呼び出しの「前」が次の副作用完了点になる。

9899:1999 6.5.2.2 Function calls / 5
(snip) If an attempt is made to modify the result of a function call or to access it after the next sequence point, the behavior is undefined.

一方 C++ では full-expression の最後まで、と規定されているため printf 呼び出し「後」、となり問題がない。

14882:2003 12.2 Temporary objects / 3
(snip) Temporary objects are destroyed as the last step in evaluating the full-expression (1.9) that (lexically) contains the point where they were created. This is true even if that evaluation ends in throwing an exception.

この点は標準化委員会でも認識されている(Lifetime of temporaries)。この文書ではさらに嫌らしい例が挙げられていて

int f()
{
    return 'i';
}

int main()
{
    printf("%c%c!\n", salutation().a[0], f());
    return 0;
}

salutation() と a[0] の間に f() 呼び出しという副作用完了点が入るかもしれないというものである。

これに対して修正提案がされており(Extending the lifetime of temporary objects)、DIS(n1570) では以下のような少々無理矢理感がある記述となっている。

n1570 6.2.4 Storage durations of objects / 8
A non-lvalue expression with structure or union type, where the structure or union contains a member with array type (including, recursively, members of all contained structures and unions) refers to an object with automatic storage duration and temporary lifetime. Its lifetime begins when the expression is evaluated and its initial value is the value of the expression. Its lifetime ends when the evaluation of the containing full expression or full declarator ends. Any attempt to modify an object with temporary lifetime results in undefined behavior.

さて、もう一点補足しておくと、JPCERT のページでは gcc で -std=c99 オプションなしだと落ちるとの記述があるが実はこの問題のせいで落ちているわけではない(未定義動作であることに変わりはないが)。-Wallで出る警告も

eval.c:11: warning: format '%s' expects type 'char *', but argument 2 has type 'char[6]'

と書式指定文字列の不一致に対する警告である。これは配列がポインタに decay されずにそのまま配列として渡されているからだ(6 バイトスタックに積まれている)。この挙動は GCC マニュアルの 6.22 Non-Lvalue Arrays May Have Subscripts にも簡単に記述されている。C99 では右辺値の配列もポインタに decay されるが C89 では左辺値の配列のみに限定されている(らしい。C89 は規格を持っていないので引用できない)。ということで C99 に対応していないはずの VC ではコンパイルされないという挙動が正しいはずである。実際に Comeau C++ では C89/90 モードではコンパイルできずに(error: invalid use of non-lvalue array) C99 モードならばコンパイルできる。

333236 journal

Yak!の日記: Google Code Jam 2011 Round2

日記 by Yak!

ooo-o--- で 39pts 594 位。Round 2 は通過ならず。仕方ないというか大健闘と言っていい感じかと。初の T シャツゲットです、多分。とりあえず small 専業と割り切ったのはレベル相応で悪くない判断だったと思っています。B-large、C-large、D-small は解けても良かったかもと思わないでもないですが、バグ無しで思ったコードをさくっと書けないというコーディング力や、練習が足りないという点も含めてやっぱり実力がちょっと足りなかったと思います。なお、以下は Contest Analysis を読まない状態で書いています。

A. Airport Walkways

速度が遅いところから greedy に t 秒とっていけばいいだけ。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {
        UI x, s, r, t, n; cin >> x >> s >> r >> t >> n;
        vector<UI> len(n), speed(n);
        UI len0 = x;
        REP(i, n) {
            UI     b, e, w; cin >> b >> e >> w;
            len[i] = e - b;
            speed[i] = s + w;
            len0 -= len[i];
        }
        if(len0) {
            len.push_back(len0);
            speed.push_back(s);
        }
        vector<UI> index(len.size()); iota(RNG(index), 0);
        sort(RNG(index), [&](UI i1, UI i2) { return speed[i1] < speed[i2]; });
        double tt = t, result = 0;
        REP(i, index.size()) {
            UI ii = index[i];
            UI leni = len[ii], speedi = speed[ii];
//cerr << i << ':' << result << ':' << leni << ':' << speedi << endl;
            if(tt > 0) {
                double speed_ = speedi + (r - s);
                if(leni / speed_ >= tt) {
                    result += tt + (leni - tt * speed_) / speedi;
                    tt = 0;
                } else {
                    result += leni / speed_;
                    tt -= leni / speed_;
                }
            } else {
                result += double(leni)/speedi;
            }
        }

        cout << "Case #" << casenum+1 << ": " << fixed << setprecision(12) << result << endl;
    }

    return 0;
}

B. Spinning Blade

small 専用で割り切ってループでぶん回しています。large は和の取り方を工夫するんだろうなぁと思いつつスキップ。ちゃんと復習しておきたい問題です。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI r, c, d; cin >> r >> c >> d;
        vector<vector<UI>> table(r, vector<UI>(c, d));
        for(auto &v1 : table) {
            string s; cin >> s;
            REP(i, c) {
                v1[i] += (s[i] - '0');
            }
        }
        UI k = min(r,c); bool flag = false;
        while(k >= 3) {
            REP(i, r-k+1) {
                REP(j, c-k+1) {
                    ULL sx = 0;
                    ULL sy = 0;
                    ULL sum = 0;
                    REP(ii, k) {
                        REP(jj, k) {
                            if((ii == 0 || ii == k - 1) && (jj == 0 || jj == k - 1)) continue;
                            sx += ii * table[i+ii][j+jj];
                            sy += jj * table[i+ii][j+jj];
                            sum += table[i+ii][j+jj];
                        }
                    }
//cerr << k << ':' << sx << ':' << sy << ':' << sum << endl;
                    if(2 * sx == (k-1)*sum && 2*sy == (k-1)*sum) {
                        flag = true;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
            --k;
        }

        if(k >= 3) {
            cout << "Case #" << casenum+1 << ": " << k << endl;
        } else {
            cout << "Case #" << casenum+1 << ": IMPOSSIBLE" << endl;
        }
    }

    return 0;
}

C. Expensive Dinner

small だけとはいえ、これが解けたのは嬉しかったですね。題意から費用そのものは単調非減少、その約数(通せる番号)の数も単調非減少になります。また最終的な費用は N 以下の全ての数字の最小公倍数になることが分かります。ということで最小回数の時はできるだけ早く最小公倍数までに増加(=約数の数を増やす)させ最大回数の時はできるだけ遅く最小公倍数までに増加させればいいわけです。こう考えると最小回数の場合は、2^l、3^m、5^n、7^o、…(l、m、n、o、… は N 以下になる最大値)という順に通していけばいいことになります。つまり N 以下の素数の個数が回数になります。一方最大回数の場合は 1、2、2^2、…、2^l、3、3^2、…、3^m、… と通していけば 1 個ずつ素因数が増えるので最も遅い場合になります。以下のコードでは 1 ~ N まで愚直に回して指数の最大値を求めていますが、素数についてループを回して N 以下になる最大指数を求めるべきですね。

large については 10^12 が厳しい条件なわけですが、sqrt(N) より大きな素数の場合、指数が 1 となり最大回数の場合でも最小回数の場合でも 1 回としか数えられないので最大回数-最小回数を求める今回の場合は完全に無視できる、つまり sqrt(10^12) = 10^6 まで調べるだけで OK ということになります。@uwitenpen さんの tweet を見て初めて気付いたので時間中には思いつけなかったと思います。

template<typename T, typename OutputIterator>
inline T pshieve(T n, OutputIterator out) // type should be changable
{
    T count = 0;
    if(n<2) return count;
    *out++=2;
    ++count;
    std::vector<bool> v(n/2);
    const T nn1 = static_cast<T>(std::sqrt(n));
    const T nn = max(nn1, n/nn1);
    T i;
    for(i=3;i<=nn;i+=2) {
        if(v[i/2-1]==false) {
            *out++=i;
            ++count;
        }
        for(T j=i+i+i;j<=n;j+=i+i) {
            v[j/2-1]=true;
        }
    }
    for(;i<=n;i+=2) {
        if(v[i/2-1]==false) {
            *out++=i;
            ++count;
        }
    }
    return count;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    vector<ULL> primes;
    pshieve(1000ULL, back_inserter(primes));

    UI cases; cin >> cases;
    REP(casenum, cases) {

        ULL n; cin >> n;
        vector<ULL> counts(primes.size());
        REPV(ULL, i, n) {
            ULL ii = i+1;
            REPV(ULL, j, primes.size()) {
                ULL count = 0;
                while(ii % primes[j] == 0ULL) {
                    ii /= primes[j];
                    ++count;
                }
                if(counts[j] < count) counts[j] = count;
            }
        }
        ULL minimum = count_if(RNG(counts), [&](ULL v) { return v > 0; });
        ULL maximum = (n>1ULL?1ULL:0ULL) + accumulate(RNG(counts), 0ULL);

        cout << "Case #" << casenum+1 << ": " << maximum - minimum << endl;
    }

    return 0;
}

D. A.I. War

時間中に書いていたコードは BFS ですがデバッグしている途中で終わりました。色々と無駄が多く直したところで結局 TLE します(上のコード)。s.c[0] = true; の代わりに s.c[0] == true; と書いていたのがバグだったのですが、これ、警告が出ません。こういう場合、大抵は式の値を使っていないとかいう警告が出るのですが、vector<bool> のため値を参照するだけで色々と処理が発生しているので警告が出ないのだと思われます。vector<bool> さんはマジ鬼門。当初 bitset 使おうかとも思ったのですが使い慣れてないので逃げました。というか、36 だから 32 ビット超えてるし、と思ってしまったのですが unsigned long long は 64 ビットなので普通にビットフラグで持てるんですよね。さらに threaten な範囲は毎回調べる必要はない、というのを修正したのが下のコードでこれで small は通ります。

struct St
{
    vector<bool> c;
    vector<bool> t;
};
bool operator<(const St& s1, const St &s2)
{
    return s1.c < s2.c || s1.c == s2.c && s1.t < s2.t;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI p, w; cin >> p >> w;
        vector<vector<char> > mat(p, vector<char>(p, 0));
        REP(i, w) {
            int x, y; char c; cin >> x >> c >> y;
            mat[x][y] = mat[y][x] = 1;
        }

        set<St> st, st_;
        St s;
        s.c = vector<bool>(p, false);
        s.t = vector<bool>(p, false);
        s.c[0] = true;
        REP(i, p) {
            if(mat[0][i]) s.t[i] = true;
        }
        auto check = [&](const St& ss)->bool { return ss.t[1]; };
        st.insert(s);

        UI c = p, t = 0; bool flag = false; UI cur = 1;
        while(1) {
            if(cur > p) break;
//cerr << st.size() << endl;
            for(auto &v : st) {
                if(check(v)) {
                    flag = true;
                    if(c > cur || c == cur && count(RNG(v.t), true) > t) {
                        c = cur;
                        t = count(RNG(v.t), true);
                    }
                } else {
//cerr << "TH1" << endl;
                    REP(i, p) {
                        if(v.c[i] == false) continue;
//cerr << "TH2" << endl;
                        REP(j, p) {
                            if(mat[i][j] && v.c[j] == false) {
//cerr << "TH3" << endl;
                                St temp = { v.c, vector<bool>(p, false) };
                                temp.c[j] = true;
                                REP(ii, p) {
                                    if(temp.c[ii]) {
                                        REP(jj, p) {
                                            if(mat[ii][jj] && temp.c[jj] == false) {
                                                temp.t[jj] = true;
                                            }
                                        }
                                    }
                                }
                                st_.insert(temp);
                            }
                        }
                    }
                }
            }
            if(flag) break;
            swap(st, st_);
            ++cur;
        }

        cout << "Case #" << casenum+1 << ": " << c-1 << ' ' << t << endl;
    }

    return 0;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI p, w; cin >> p >> w;
        vector<vector<char> > mat(p, vector<char>(p, 0));
        REP(i, w) {
            int x, y; char c; cin >> x >> c >> y;
            mat[x][y] = mat[y][x] = 1;
        }

        ULL checker = 0;
        REP(i, p) {
            if(mat[1][i]) checker |= (1ULL << i);
        }

        set<ULL> st, st_;
        ULL s = 1ULL;
        auto check = [&](ULL ss)->bool { return ss & checker; };
        auto th = [&](ULL ss)->UI {
            ULL t = 0; int count = 0;
            REP(i, p) {
                if(((ss >> i) & 1ULL) == 0) continue;
                REP(j, p) {
                    if(mat[i][j] && ((ss >> j) & 1ULL) == 0 && ((t >> j) & 1ULL) == 0) {
                        t |= (1ULL << j);
                        ++count;
                    }
                }
            }
            return count;
        };
        st.insert(s);

        UI c = p, t = 0; bool flag = false; UI cur = 1;
        while(1) {
            if(cur > p) break;
//cerr << st.size() << endl;
            for(auto &v : st) {
                if(check(v)) {
                    flag = true;
                    if(c > cur || c == cur && th(v) > t) {
                        c = cur;
                        t = th(v);
                    }
                } else {
//cerr << "TH1" << endl;
                    REP(i, p) {
                        if(((v >> i) & 1ULL) == 0) continue;
//cerr << "TH2" << endl;
                        REP(j, p) {
                            if(mat[i][j] && ((v >> j) & 1ULL) == 0) {
//cerr << "TH3" << endl;
                                ULL temp = v;
                                temp |= (1ULL << j);
                                st_.insert(temp);
                            }
                        }
                    }
                }
            }
            if(flag) break;
            swap(st, st_);
            ++cur;
        }

        cout << "Case #" << casenum+1 << ": " << c-1 << ' ' << t << endl;
    }

    return 0;
}

まとめ

2008 は Round2 661 位で通過、Round3 885 位、2009 は Round1 で落ち、2010 は Round2 1005 位と評価に困る所ではありますが 2008 はまぐれとするとちょっとずつ向上という言い方もできるかもしれません。反省的には、毎回コーディング力と練習が足りない、ばっかり言っている気がしますが、事実だからしょうがないというか。

テンプレ

// Using C++0x mode in g++ 4.6.0

#include <iostream>
#include <sstream>
#include <iomanip>

#include <iterator>

#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>

#include <string>

#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>

#include <tuple>
#include <initializer_list>

#include <cmath>

// Boost library can be retrieved from http://www.boost.org/
// I used 1.46.1

#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;

#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)

using namespace std;

template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer  last)
{ return boost::irange(first, last); }

331372 journal

Yak!の日記: Variadic な std::tuple に対する Fusion アダプタ書いてみた

日記 by Yak!

きっと誰かやってるだろうと思いつつ書いてみたら案の定 @iorate さんが直近で同様の事をやっているわけだが折角なので晒してみる。

https://gist.github.com/1000596

動作確認したのは g++ 4.3.4 と g++ 4.6.0。VC10 は Variadic templates が使えないのでパス。@iorate さんのを見ればどこ直せば対応できるかは分かるけど。違いとしては一応 CV 修飾子(要素の型だけでなく tuple 自体についてる場合についても)と参照型について手当をしているけど、参照型については C++0x で reference to reference が大丈夫になったので何も考えずに tuple_element<I, tuple_type> & で大丈夫かもしれない(左辺値参照の範囲では)。

こういうのを自分で書いてみるというのもやっぱり勉強になって、型のテスト用に MPL 使ったけどメタ関数周りが色々と理解が足りなかったのを再認識した。さらに基本中の基本だろうけど、const tuple<int&> な t があったとして get<0>(t) の型は const int& ではなく int& だというのも再認識。

int n;
struct A {
  int &r;
  int *p;
};
const A a = { n, &n };

が有った時に a.r = 5; が可能というのと同じで、一瞬あれ?っと思うのだが *(a.p) = 5; が可能であることと同じである。つまり、ポインタ自体が const なのであって指している先が const ではない。参照は指し先が変えられないので最初から const みたいなものではあるが。

329412 journal

Yak!の日記: Google Code Jam 2011 R1A, R1B

日記 by Yak!

なんとか R1B 枠で通過しました。

R1A Problem A. FreeCell Statistics

数学。結構悩んでました。辿りついた考え方は次の通り。その日の勝利数/その日の試合数=PD/100⇔100×その日の勝利数=PD×その日の試合数となるのでPD×その日の試合数は100=2^2*5^2の倍数になる必要があります。PD と 100 の公約数を調べてその数で 100 を割ってやるとその日の試合数の最低値 nn が出ます。これが n より大きい場合、条件を満たすことは不可能です。なお↓のコードだと PD = 0 のケースを特別扱いしていませんがたまたまうまく行っているだけ(ちゃんと nn = 1 になります)でそこまで考えていたわけではないです。次にその日の試合数が nn だった場合のその日の勝利数 w を求めています。PG = 100 の場合、全て勝利である必要があり、PG = 0 の場合、勝利数 0 である必要があります。PG が 0 でも 100 でもない場合、PG / 100 の分母・分子にものすごく大きい数をかけてやれば (w + k) / (nn + l) (但し 0 ≦ k ≦ l, k はその日以外の勝利数、l はその日以外の試合数) で k, l を適当に設定して合わせることが必ずできます。ということで判断しているのですが、実際には w を求めなくても、PD = 0 か PD = 100 で判断すればいいだけですね。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {
        ULL n, pd, pg; cin >> n >> pd >> pg;
        string s;

        if(pd == 0) {
            if(pg != 100) s = "Possible";
            else s = "Broken";
        } else {
            ULL d2 = 0, d5 = 0, pd_ = pd;
            if(pd_ % 2 == 0) { ++d2; pd_ /= 2; }
            if(pd_ % 2 == 0) { ++d2; pd_ /= 2; }
            if(pd_ % 5 == 0) { ++d5; pd_ /= 5; }
            if(pd_ % 5 == 0) { ++d5; pd_ /= 5; }

            ULL nn = 1 * (d2 == 2 ? 1 : d2 == 1 ? 2 : 4) * (d5 == 2 ? 1 : d5 == 1 ? 5 : 25);
//cerr << "nn: " << nn << endl;
            if(nn > n) {
                s = "Broken";
            } else {
                ULL w = pd * nn / 100;
//cerr << "w: " << w << endl;
                if(w != 0 && pg == 0) s = "Broken";
                else {
                    if(w != nn && pg == 100) { s = "Broken"; }
                    else { s = "Possible"; }
                }
            }
        }

        cout << "Case #" << casenum+1 << ": " << s << endl;
    }

    return 0;
}

R1A Problem B. The Killer Word

シミュレーション的に実装しようとしてごりごり書いていてぎりぎりの時間くらいでコンパイルが通るようにはなったのですがロジックが間違っていました。文字候補リスト上で最後に確定される単語を返すように書いていて、明らかに使われない文字候補はスキップしてポイントが入らない、という点が抜けていました。全単語についてポイントを計算して最大値になる単語を返すよう修正すると通りました。Large についても手元の環境では 4 分くらいで実行できています。

実装的にはデータ構造をどうしようかで multimap とふらついたりして時間をロスしてしまいました。基本的には区別できない単語群を set として持って区別できるようになったら分割していく、1 つになったらそこで終了、という処理になっています。contest analysis で記述されているのもこれと同じような方法のようですね。Union-find の逆、みたいなイメージなのですがこれを効率的に実装できるデータ構造とかあるんでしょうか?各単語10文字以下なので単語中の各文字の使用位置をビットフラグで持って高速化しています。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {
        UL n,m; cin >> n >> m;
        vector<string> dic(n); for(auto &v : dic) { cin >> v; }
        vector<vector<UL>> len(10);
        REP(i, n) {
            len[dic[i].size()-1].push_back(i);
        }
        vector<vector<UL>> pos(n, vector<UL>(26));
        REP(i, n) {
            REP(j, 26) {
                UL temp = 0;
                REP(k, dic[i].size()) {
                    if(dic[i][k] == 'a' + j) temp |=  (1U << k);
                }
                pos[i][j] = temp;
            }
        }

        vector<string> result;
        REP(i, m) {
            string l; cin >> l;
            vector<UL> temp(n); iota(RNG(temp), 0);
            set<UL> candidate(RNG(temp));
            map<UL, UL> group, newgroup;

            UL gidx = 0;
            for(auto &v1 : len) {
                for(auto &v2 : v1) {
                    group.insert(make_pair(v2, gidx));
                }
                ++gidx;
            }

            vector<UL> points(n);
            for(auto &ch : l) {
                map<pair<UL, UL>, set<UL> > check;
                vector<UL> gflag(gidx);
                for(auto &v : candidate) {
//cerr << v << ':' << group[v] << ':' << pos[v][ch - 'a'] << endl;
                    check[make_pair(group[v], pos[v][ch - 'a'])].insert(v);
                    gflag[group[v]] |= pos[v][ch - 'a'] != 0;
                }
                for(auto &v : candidate) {
                    if(gflag[group[v]] && pos[v][ch - 'a'] == 0) ++points[v];
                }
                gidx = 0;
                set<UL> removed;
                for(auto &v : check) {
                    if(v.second.size() == 1) {
                        removed.insert(*v.second.begin());
                    } else {
                        for(auto &v2 : v.second) {
                            newgroup.insert(make_pair(v2, gidx));
                        }
                        ++gidx;
                    }
                }
                for(auto &v : removed) { candidate.erase(v); }
                swap(group, newgroup); newgroup.clear();
            }
            result.push_back(dic[max_element(RNG(points)) - points.begin()]);
        }

        cout << "Case #" << casenum+1 << ':';
        REP(i, m) {
            cout << ' ' << result[i];
        }
        cout << endl;
    }

    return 0;
}

R1A Problem C. Pseudominion

未着手

R1A まとめ

Qualification がゆるゆるだったのでその流れで行くのかと思ったらいきなり頬はったかれたかのような感じでした。コンディション的に寝不足でへろへろのひどい状態で、B のコード書いてる間に訳が分からなくなることもしばしば。最終的には A-Small、A-Large の 20 pts 1257 位で通過ならず。ただ B の基本方針は外れておらずボーダー的にも近いところではあったので R1B で通過できるんじゃないかな、という希望は残りました。

R1B Problem A. RPI

やるだけ。OWP が正しく解釈できたかどうかにかかっている気がします。ある意味英語ゲー。Large にしても計算量的に問題になるところもないでしょう。R1A 出た人の中にはこれでいいのか、と深読みしちゃった人も居るんじゃないでしょうか。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UL n; cin >> n;
        vector<string> table(n); for(auto &v : table) { cin >> v; }
        vector<long double> wp(n), owp(n), oowp(n);
        REP(i, n) {
            int num = 0, won = 0;
            REP(j, n) {
                if(table[i][j] == '1') {
                    ++num; ++won;
                    int num2 = 0, won2 = 0;
                    REP(k, n) {
                        if(i != k) {
                            if(table[k][j] == '0') { ++num2; ++won2; }
                            else if(table[k][j] == '1') { ++num2; }
                        }
                    }
                    owp[i] += (long double)won2/num2;
                }else if(table[i][j] == '0') {
                    ++num;
                    int num2 = 0, won2 = 0;
                    REP(k, n) {
                        if(i != k) {
                            if(table[k][j] == '0') { ++num2; ++won2; }
                            else if(table[k][j] == '1') { ++num2; }
                        }
                    }
                    owp[i] += (long double)won2/num2;
                }
            }
            wp[i] = (long double)won/num;
            owp[i] /= num;
        }
        REP(i, n) {
            int num = 0;
            REP(j, n) {
                if(table[i][j] != '.') {
                    ++num;
                    oowp[i] += owp[j];
                }
            }
            oowp[i] /= num;
        }

        cout << "Case #" << casenum+1 << ":" << endl;
        REP(i, n) {
            cout << fixed << setprecision(12) << 0.25*wp[i]+0.5*owp[i]+0.25*oowp[i] << endl;
        }
    }

    return 0;
}

R1B Problem B. Revenge of the Hot Dogs

これも結構考えてました。当初はある位置での点の個数を n として必要な幅は (n-1)*d。左右に振り分けてこれがぶつからないグループに分けてグループ毎に計算すればいける?みたいなことを考えていましたが玉突き的にぶつかっていくケースがあるので独立に計算できないことに気づき考え込んでしまいました。で降ってきたのが光円錐のイメージ(光である必要は全然ないのですが)。速度は 1m/s で決まっているのである時刻 t のとき、ある位置を起点にした点群が移動可能な範囲は決まってしまいます。逆にこの範囲内なら自由に移動可能です。基本的にはこれが (n-1)*d の幅を持てばいいわけです。隣とぶつかるケースがあるのでその分だけ移動可能な範囲を制限してやるとある時刻 t で条件を満たすか判定できます。ということで二分探索で解くことが可能です。これに気付いた時にはキターって感じになりました。

実際には B-Large に落ちました。提出しようとするときに絶対誤差だけ見てループを回していて無限ループしていたのを相対誤差も見るようにして(8分以内に)直して提出したのですがそれでも落ちました。原因は check() の中の wall の初期値です。二分探索の初期値を大きくした分、この初期値も絶対値的に大きな値に変更する必要がありました。意味的には -inf なので -numeric_limits::max() にしておくべきだったかもしれません。浮動小数点に対する numeric_limits の意味ってどうだったっけ?というのがあって即値で書いてしまいました。

題意を満たすだけなら絶対誤差と相対誤差の両方が閾値を越えている(r - l > diff && (r -l) / r > diff)間 回せばいいのですが、出力結果的に切りが悪い数値が出るので固定回数回す分も入れた形になっています。こうするぐらいなら単に固定回数回してしまえばいいでしょうけど。

bool check(long double time, vector<LL> &pos, vector<LL> &num, UI d)
{
    long double wall = -1.0e+20;
    REP(i, pos.size()) {
        if(pos[i] + time - max(wall, pos[i] - time) < (num[i]-1) * d) return false;
        wall = max(wall, pos[i] - time) + num[i] * d;
    }
    return true;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI c, d; cin >> c >> d;
        vector<LL> pos(c);
        vector<LL> num(c);
        REP(i, c) {
            cin >> pos[i] >> num[i];
        }
        const long double diff = 0.000000001;
        long double l = 0, r = 1.0e+13, cent;
        int i = 0;
        while(r - l > diff && ++i < 1000) {
            cent = (l+r)/2;
//            cerr << l << ' ' << cent << ' ' << r << endl;
            if(check(cent, pos, num, d)) {
                r = cent;
            } else {
                l = cent;
            }
        }

        cout << "Case #" << casenum+1 << ": " << fixed << setprecision(8) << cent << endl;
    }

    return 0;
}

R1B Problem C. House of Kittens

分割された各部屋の最小頂点数が答えになる、というのまでは当たりづけ。ただしこれもすぐに OK という話ではなくて隣接している部屋で共有するのは 2 点のみ、隣接している部屋を辿って同じ部屋に再び戻ってくることはない(言い換えると双対グラフが閉路を持たず木になっている)ため色の塗り分けを(双対グラフの葉側で)調整できて 4 頂点なのに 3 色でしか塗れない、といった状態が発生しないから、とまで考えての結果です。実は双対グラフどうこうも後付けで最初からそう考えられていれば多角形内部に点がないから双対グラフに閉路なくて当然だよね、という話でした。

で、各部屋をどうやって確認しようかということで自前で頑張ってコードを書こうかとしたのですがそこではたと気づきました。「これ、Google Code Jam じゃん」 そう、外部ライブラリが使用可能なわけです。ということで Boost Graph を確認すると正にそういう目的の関数 planar_face_traversal() がありました。これを使って色数を出力するところまではできたのですが、色分けまでできませんでした。planar embedding とか知らなかったので最初から BGL 使おうとしても辿り着けなかった可能性は高いです。しかも色塗りのコードで色々と思い違いをして試行錯誤しました。以下のコードでは双対グラフ(前述のように木になる)上を辿りつつ、最初は出来る限り色を使いつつ全色使った後は辺の両端が異なる色になるようにして塗っています。結局 contest analysis の方法に辿り着いた、という形でしょうか。

template<typename Graph>
struct dual_graph_visitor : public planar_face_traversal_visitor
{
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename graph_traits<Graph>::edge_descriptor Edge;

    void begin_face() {
        vertices.push_back(vector<Vertex>());
        edges.push_back(vector<Edge>());
    }
    void end_face() { }

    void next_vertex(Vertex v)
    {
        vertices.back().push_back(v);
    }
    void next_edge(Edge e)
    {
        edges.back().push_back(e);
        links[e].push_back(edges.size()-1);
    }

    vector<vector<Vertex>> vertices;
    vector<vector<Edge>> edges;
    map<Edge, vector<UI>> links;
};

template<typename T>
T absdiff(T a, T b) { return a > b ? a - b : b - a; }

int main(void)
{
    ios_base::sync_with_stdio(false);

    typedef adjacency_list
        < vecS,
          vecS,
          undirectedS,
          property<vertex_index_t, int>,
          property<edge_index_t, int>
        >
        graph;
    typedef graph_traits<graph>::vertex_descriptor Vertex;
    typedef graph_traits<graph>::vertex_iterator VIterator;
    typedef graph_traits<graph>::edge_descriptor Edge;

    UI cases; cin >> cases;
    REP(casenum, cases) {
        int n, m; cin >> n >> m;

        vector<int> u(m), v(m);
        for(auto &val : u) { cin >> val; --val; }
        for(auto &val : v) { cin >> val; --val; }

        graph g(n);
        REP(i, m) {
            add_edge(u[i], v[i], g);
        }
        REP(i, n) {
            add_edge(i, (i+1)% n, g);
        }

        property_map<graph, edge_index_t>::type e_index = get(edge_index, g);
        graph_traits<graph>::edges_size_type edge_count = 0;
        graph_traits<graph>::edge_iterator ei, ei_end;
        for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
            put(e_index, *ei, edge_count++);

        typedef std::vector< Edge > vec_t;
        std::vector<vec_t> embedding(num_vertices(g));
        int idx = 0;
        VIterator vi, vi_end;
        for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
            auto p = out_edges(*vi, g);
            embedding[idx].assign(p.first, p.second);
            sort(RNG(embedding[idx]), [&](Edge e1, Edge e2) { return target(e1, g) < target(e2, g); });
            ++idx;
        }

        dual_graph_visitor<graph> v_vis;
        planar_face_traversal(g, &embedding[0], v_vis);

        auto it = find_if(RNG(v_vis.vertices), [&](vector<Vertex> &v) { return v.size() == n; });
        if(it == v_vis.vertices.end()) cerr << "Not found" << endl;
        for(auto &v : v_vis.edges[it - v_vis.vertices.begin()]) {
            v_vis.links[v].push_back(0); // 0 is dummy
        }
        for(auto it = v_vis.links.begin(); it != v_vis.links.end();) {
            if(it->second.size() == 3) {
                v_vis.links.erase(it++);
            } else ++it;
        }
        v_vis.edges.erase(v_vis.edges.begin() + (it - v_vis.vertices.begin()));
        v_vis.vertices.erase(it);

        vector<UI> sizes(v_vis.vertices.size());
        transform(RNG(v_vis.vertices), sizes.begin(), [](vector<Vertex>&s) { return s.size(); });
        int colors = *min_element(RNG(sizes));

        vector<int> color(n);
        vector<bool> visited(v_vis.edges.size());

        function<void(UI)> traverse = [&](UI face) {
            if(visited[face]) return;
            visited[face] = true;
            vector<bool> used(colors);
            auto colorize = [&](Vertex v, int idx) {
                if(color[v] != 0) return;
                REP(j, colors) {
                    if(!used[j]) {
                        color[v] = j+1;
                        used[j] = true;
                        break;
                    }
                }
                if(color[v] == 0) {
                    int vn = v_vis.vertices[face].size();
                    int c1 = color[v_vis.vertices[face][(idx+1)%vn]];
                    int c2 = color[v_vis.vertices[face][(idx+vn-1)%vn]];
                    if(c1 > c2) swap(c1, c2);
                    color[v] = c2 <= 2 ? c2 + 1 : c1 <= 1 ? 2 : 1;
                }
            };
            for(auto vertex : v_vis.vertices[face]) {
                if(color[vertex] != 0) used[color[vertex]-1] = true;
            }
         REP(i, v_vis.vertices[face].size()) {
              colorize(v_vis.vertices[face][i], i);
         }
            for(auto edge : v_vis.edges[face]) {
                if(v_vis.links.count(edge)) {
                    if(v_vis.links[edge][0] == face) {
                        traverse(v_vis.links[edge][1]);
                    } else {
                        traverse(v_vis.links[edge][0]);
                    }
                }
            }
        };
        traverse(0);

        cout << "Case #" << casenum+1 << ": " << colors << endl;
        REP(i, n) {
            if(i != 0) cout << ' ';
            cout << color[i];
        }
        cout << endl;
    }

    return 0;
}

R1B まとめ

A-Small、A-Large、B-Small の 35 pts で 828 位。B-Large も取っておきたかったところではありますが教訓を得た上で通過できたのでまぁ良しとしましょう。あれ?と引っかかったところを安易にスルーしない、といったところでしょうか。後、グラフ関連は弱いのでもう少し BGL を確認しておきたいです。

まとめ

なかなか C++0x ぽいコードが書けないですね。特に誘惑に負けて REP マクロを導入してしまったため余計にそちらに頼ってしまう感じです。Range-based for もそれなりに使えることは使えるんですが REP マクロの単純明快さには勝てないというか。型名無かったら自動的に auto とかにならないですかね。後、要素だけではなくて添字も欲しいケースが結構あるので。アダプタを噛ませるべきなのかもしれませんが。後、auto func = [&](...) {...} や function<...> func = [&](...) {...} はヘルパ関数作成用に結構有用なイディオムだと思うので今後とも使える時には使いそうです。

テンプレ

#include <iostream>
#include <sstream>

#include <iterator>

#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>

#include <string>

#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>

#include <tuple>
#include <initializer_list>
#include <functional>

#include <cmath>

// Boost library can be retrieved from http://www.boost.org/
// I uses 1.46.1

#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/ref.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;

#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)

using namespace std;
using namespace boost;

template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer  last)
{ return boost::irange(first, last); }

326377 journal

Yak!の日記: Boost.勉強会 #5 名古屋で発表してきました

日記 by Yak!

5/14(土)の Boost.勉強会 #5 名古屋で発表してきました。ぶっちゃけ GC 本勉強会の LT を入れてすら発表 2 回目という状況だったのですが、cpp_akira さんのプレッシャー背中を押して頂いて手を挙げました。Boost.勉強会でそれも Spirit テーマとか無謀だろうという感じでしたがまぁなんとか。

「春のlock free祭り」 (kumagi)

Lock-free。Java だと標準ライブラリに入ってる事もあって憧れですね。なんせ C++ にはマルチスレッドについてさえ規定がありませんでしたから。C++0x で Concurrency 周りが超強化され <atomic> も入る事で portable に lock-free  が書ける事になりある意味タイムリーとも言える訳ですが。うーん、やっぱり難しいですね。全然理解できていないのはともかく、話を聞いているのは面白いのですがやっぱりこの辺の実装は専門家に任せないと駄目だなぁという意を強くしました。ということで誰か書いてください。

「Boostで線形代数(再)入門」 (wof_moriguchi)

今のところあまり線形代数に関わらない感じではあるのですが。ただ多元連立一次方程式については結局その問題に帰着される問題も多い訳でさくっと書けるに超した事はないかも。

「Frama-Cによるソースコード検証」 (mzp)

うん、まぁ @mzp さんですね、うん。良く分かりませんが今は亡き Concept さんが居れば axiom とかと連携して良い感じになっていたかもしれません。

簡単のために端折ったのかもしれませんが min の仕様が返値が引数 x,y 以下、だけってのがちょっと気になりました。LE だけでも LE(x, \result) || LE(y, \result) で x か y のいずれかあるいは両方と等しいって規定できますよね?直接言えよって話ですが。

「C(C++)による左再帰を許すPEG」 (eldesh)

発表タイトルが告知された時から「ぐぁぁ」って感じでした。なぜなら発表では明示してなかったような気もしますが Spirit は PEG だからです。ネタ被りっていうかもっと高度じゃないですか-、やだー、みたいな。もちろん大変興味深く聞けました。

なお、Spirit は PEG で、かつ、Packrat parser を使っていません。なので左再帰は無限ループします(当日の朝に一応確認)。 ただ左再帰は文法を書き直せばいいですし計算量的に最悪指数時間と言っても無限先読みが可能という特徴から来ているものですので先読みがなければそれ程大きな影響はないはずです、多分。例えば axpdf--.spi なんかは先読みを使わずに書けています。

「Boost.Pythonの有能性」 (fate_fox)

高校生ですよ、高校生。競技コーディングもそうですけど最近の高校生ぱねぇ。

後、さらっと color f0 の助け船を出した yOU_aND_i さん、かっけぇ。

第一スクリプト言語が Perl なのでちょっと使うには敷居が高いですね。Python 以外にも対応させようという Language Binding というプロジェクトがあったはずなのですが完全に止まっちゃってますね。

「Boost.statechart / Boost.MSM」 (PG_kura)

衝撃のデモw DSEL がキモイのは、もうしょうがない気がします。基本無理矢理だし。でもきもいと言われた記法は eUML っぽいですが、UML のステートチャート図の記法が「イベント[ガード]/アクション」なので「まんまやん」って話ですよ。そうすると source + event [guard] / action == target ってのもそんなに変な感じはしません。…毒されてるんでしょうか。

「C++0x総復習」 (wraith13)

170 ページもある超大資料。carries_dependency ってのは知らなかったです。というか Concurrency 周りは良く分かってないので誰かエロイ人纏めてくれないでしょうか。まぁそれ以外にも FDIS 眺めてると結構知らない変更とかあったりします。ぶっちゃけ to_string() とか stoi() とかも知りませんでした。

「OpenCVを使った画像処理」 (miyabiarts)

やりたいんですけどね、OpenCV。本を買うだけはする自分のこと、OpenCV 本もあります。完全に積読ですが。GIL については BGL で adjacency_list とかと visitor だけがある状態みたいなイメージだと思うのでその上で走るアルゴリズムとかがないとなかなか使うメリットが見いだせないよな、という気はします。

「非実用的 Boost.Spirit.Qi 入門」 (yak_ex)

何の因果かトリになってしまいました(手を上げるのが遅かっただけ)。ネタの方向性的に Spirit に真面目に取り組んでる人ほど不興を買うような発表をしてしまったような気がします。発表が終わった後、酷評されてたらどうしようとか思いながら #boostjp 見に行ったのですが 3.3MB で全て持って行ってしまってたような。ちなみにエラー 3.3MB は本当に極端なケースです。ついでに言えば着目すべきエラーを一つ決めてしまえば後どんだけ出ようが大した問題ではありません。

反省点としてはそもそもの発表の位置づけでしょうか。Spirit で行くぜ→Tutorial あるじゃん→マニアックな方向も入れよう→非現実的、という思考回路だったのですが結局マニアックな方向を纏めきれませんでした。いっそ拡張性のところをばっさり割愛しようかとも思ったのですが(時間的にも)、せっかく書いたんだしということでスライドに残した上でスキップにしてしまいました。「Tutorila あるじゃん」に対する対応としては、カバーしきれていない落とし穴(Skipper周り)とか、いっそのこと Spirit エラーメッセージの傾向と対策とか、そういう実用方面を目指せばより有意義な発表ができたと思います。それだけの経験が貯まってなかったのも事実ですが。

ネタ的には「アーサー・C++・クラーク」とかも拾って頂いたようで無いセンス絞ったのが報われたような気がします。でも座席表で「へんたい」と書かれたのは想定外。違うよ。ボクはへんたいじゃないよ。仮にへんたいだとしてもへんたいという名の C++er 見習いだよ。

全体

Boost どころか C++ も関係ない発表が多いってどういうことなの?って感じですが、まぁ、Boost(に興味を持つような人が興味を持つようなことの)勉強会、ということにしておけば問題ないですね! Spirit における Packrat parser の実装可能性についてはちょっと考えてみたいところです。また、Boost.勉強会に限らず何らかの発表ができればいいなぁと思います。

typodupeerror

192.168.0.1は、私が使っている IPアドレスですので勝手に使わないでください --- ある通りすがり

読み込み中...