子供の落書き帳 Remix

15/4/13:ひと月に一度更新するブログになってしまっている

スポンサーサイト
--/--/--(--) --:--:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

勉強法を学ぶオンライン講義 「Learning How to Learn」が気になる
2016/11/10(木) 00:05:51

タイトルだけで言いたいことはだいたい言ってしまったw。でも中身の話も書いておこう。

見つけたきっかけは、Couseraのコースの受講感想スライドだった



先日、speakerdeckのスライドを色々見ていて、以下のスライドを見つけた。
日本で働きながら海外名門大学で学べる!そう Coursera ならね! / Coursera is Awesome ! // Speaker Deck
CourseraというのはMOOC(Massive Open Online Course)の一つである。MOOCとは、インターネットを使って無料で受講できる講義である。オンラインで授業を受けて勉強をできるわけだ。

このページについたはてブのコメントに以下のものがあった。


時間の確保が課題ですよねー。コースの平均修了率は1桁台らしいし。MOOCに慣れるためのコースとして、負荷の低い"Learning How to Learn"はおすすめです。
はてなブックマーク - 日本で働きながら海外名門大学で学べる!そう Coursera ならね! / Coursera is Awesome ! // Speaker Deck


で、このタイトルが気になったので、調べた。
「効率の良い勉強方法」のようなトピックには関心があるので。上手い勉強のしかたがあるなら知っておきたいと思う。

うまい勉強のしかたの秘訣とは……「学び方を学ぶ」講座の概要


公式ページは以下である。
Learning How to Learn: Powerful mental tools to help you master tough subjects - University of California, San Diego | Coursera
Learning How to Learn: Powerful mental tools to help you master tough subjects
タイトルは「学び方を学ぶ」という意味である。サイトcouseraの中の1つの講座である。

日本語のページを講義の名前で検索すると、以下の2件だけが出てくる。
Learning How to Learn の日本語まとめ
内容をまとめて紹介してるスライド。

全ての学ぶ人へ―学び方を学ぶ講義『Learning How to Learn』 - It's okay to be weird
先のブコメを書いた人によるブログ記事。

これらの情報を参考にしながら、講義についてまとめてみる。

4週間のコースであり、他のコースに比べると短めである。
学問分野としては、脳科学ということになるだろうか。


各回の中身は?

1:学習とは何か (思考のモード、先延ばし対策、記憶について、学習と睡眠)
2:チャンク (情報のかたまり。チャンクにすると記憶しやすくなる)
3:先延ばしと記憶 (長期記憶と短期記憶)
4:学習の復活と、潜在能力の発揮(自分の強みの認識、チェックリストの活用、など)

好きなタイミングでやり始められる……みたいだが、いまいちよく分からん。



おまけ:他にも色々な講座が受講できるみたいだ



Reviews for Learning How to Learn: Powerful mental tools to help you master tough subjects from Coursera | Class Central
色々と調べてみると、Class Centralというのが「MOOCのまとめレビューサイト」であるようだ。講義を受けた人が、食べログのように講座に点数をつけている。講座を受けるときにどれくらい時間をかけたかを書いてある場合もあるので、参考になるだろう。

Class Centralには、人気講座の一覧のページがある。
Top 50 Free Online Courses | Class Central

そこを見ていたら、「幸福と達成について」の話もある。こっちも大好きな題材なので気になる。
Reviews for A Life of Happiness and Fulfillment from Coursera | Class Central


「Learning How to Learn」は人気の高い講座のようだが、日本語の情報を探してもあまり見つからなかった。
受講してる人が少ないのだろう。日本ではまだまだMOOCが広まってないんだろうね。俺も全然受けたことないし。
これを受けたら効率よく勉強できるようになるのかなー。でも結構な時間を割いて英語で授業を受けるのは、二の足を踏むなぁ。

それでは。
  1. 2016/11/10(木) 00:05:51|
  2. 雑記
  3. | トラックバック:0
  4. | コメント:0

マジカルミライ ライブの予習法 ~当日楽しんで聴くために~
2016/10/09(日) 20:02:54

この間、初音ミク「マジカルミライ」のライブの感想を書いた。
マジカルミライ2016 ライブレポート & セットリスト感想 子供の落書き帳 Remix
「公演で流れるセットリストの曲を予習する方法」について書き忘れたので、備忘のためにまとめておく。
(マジカルミライに限らず、MIKU EXPOなど、VOCALOIDの公式ライブでも同様である)

予習するなら、オフィシャルアルバムの収録曲から始めよう


特定の曲が演奏されるかどうかは本番になるまで分からない。しかし、演奏されると唯一確実に言えるのは、公式アルバムの収録曲である。
今年の場合はこれ。初音ミク「マジカルミライ 2016」
公演日が9月10日と11日なのに対して発売日は8月3日。アルバムの曲目を紹介する動画が上がったのがさらに遡って7月20日なので、1ヶ月以上前には曲は確定している。
全曲ではなく一部の曲、今回は9曲のみ。
これらの曲は確実に演奏されるので、不確かな予想に基づいて色々聴くよりは、これらを早めに聴いて予習しておくと良さそうだ。


初音ミク -Project DIVA- シリーズの収録曲を聴き込む


で、ここから先は不確実な予想になる。
とはいえ、手がかりはある。作曲者から許可を取って、振り付けを作った曲しか上演できない。したがって、SEGAが出している「初音ミク -Project DIVA-」シリーズの収録曲の中から演奏されることになる。
(ここらへん、イマイチ分かっていない気がする。マジカルミライのライブの主催がSEGAだってわけじゃないよね……?)
初音ミク -Project DIVA- wiki - トップページ
ここから各ゲームの収録曲一覧に飛んで、自分が知らない曲があったら聴いておけばよい。予習するには曲数が多すぎるのが難点。


他の人が予想してるのを読む


あとはライブ名と「セットリスト」「予想」あたりで検索して、ブログなどに個人が予想を書いているのを読むのも一興。
でもあくまで予想なので、当たっても外れても仕方ない。

公演が始まってからはTwitterで検索


公演が複数回あって、自分が行くのが2回目以降の場合、1回目の公演が終わったあたりでセットリストが上がる。
といっても公式発表ではない。公演を聴いた人がTwitterなどでつぶやくのである。
だから、Twitter上で「マジカルミライ セットリスト」で検索して、誰かがセットリストを上げるのを待つ。
2回目以降の公演しか使えず、また直前になるが、全曲のリストが確実に分かるのはこの方法である。


それでは。
  1. 2016/10/09(日) 20:02:54|
  2. 雑記
  3. | トラックバック:0
  4. | コメント:0

マジカルミライ2016 ライブレポート & セットリスト感想
2016/10/03(月) 01:25:36



3日間で25000人が参加した「初音ミク マジカルミライ2016」。
そのライブに行ってきたので感想を書く。

・前提
・前日~本番前まで
・曲ごとの感想
・選曲(セットリスト)について
という構成でお送りします。


前提


前提……というのも変だけど、自分のVOCALOIDの詳しさについて。

ボカロ曲は、各種音ゲーをきっかけに知ったものが多い。
Project DIVA arcadeは一時期やりこんでいたが、2014年初頭に離れたのでそれ以降の追加曲は知らない。
よほど好きな作曲者でもない限り、自分からニコニコで曲を漁りはしない。ランキングとかも別に見ない。
「好きな曲は好きだけど、それ以外は割とどうでもいい」と思っている。したがって、ニコ動で再生数が多くても知らない曲は結構ある。

前日~本番前まで



俺が行ったのは日曜の昼の公演である。
前日の土曜日。「マジカルミライ セットリスト」でTwitterを検索して、初回の公演を終えた人が曲目を上げているのを見る。
……知らない曲ばっかりじゃないか。どうしよう。5曲しか知らない。やばい。
「すろぉもぉしょん」「タイムマシン」「ウミユリ海底譚」「リモコン」「39」
しかも、その中で「すろぉもぉしょん」もチュウニズムで2回やっただけだったと思う。

というわけで前日と当日に大急ぎで予習をして曲を詰め込んだ。それでも何曲か、本番までに一度も聞かなかった曲もある。


曲ごとの感想



セットリストは↓を参考にした。
まさかのコラボ、待望の新曲も!初音ミク「マジカルミライ 2016」ライブ・セットリスト解禁 - Character JAPAN

1 39みゅーじっく!/みきとP/初音ミク
事前に聞いてるときはいつも「曲は良いんだけどもう少し速いほうがノリが良くて好きだなぁ」と思っていた。今テンポを測ったら130ぐらいだったので、1割くらい上げて良いと思う。
もう一度名前呼んで! 「初音ミク!」 のコールが楽しかった。

2 ゴーストルール/DECO*27/初音ミク
アップテンポで勢いがある。終盤に二回続けざまに転調するのが好き。サビ後のバックコーラス「あーあーあーあーあーあーああー」がコール部分になる。

3 ヒビカセ/GigaReol/初音ミク
この曲だけは上部スクリーンに歌詞が出てた。元の動画でも字幕の入り方が特徴的だったからだろう。
2014年に「VOCALOIDとしての初音ミク」を歌う曲ってかなり珍しくない? 「あなたの歌姫」「ハジメテノオト」など、初期の曲に多い印象。

4 Strangers/Heavenz/初音ミク
付点4分音符メインで展開する前奏は好きだけど、あんまりサビは印象に残ってない。

5 すろぉもぉしょん/ピノキオピー/初音ミク


このツイート見て気になっていたが、その通りの髪がボサボサなミクでした。可愛い。
ピノキオピー大好きなのに、この曲をちゃんと聞いたことがなかったから、行きの電車で必死こいてコールのタイミング覚えた。「ソレソレ」「ア、ドシタ」とかの部分ね。
でもBメロのところでコールが出てきたのは曲を聞いても分からなかったな……「うぉーー、(4拍目で)はい」の繰り返し。

6 独りんぼエンヴィー/koyori(電ポルP) /初音ミク
この曲のようにだらっと歌う曲は珍しいな。
サビのところで唯一16分が入るし、音程も他の部分に比べて大きく動く。よくよく聞いてみると、終始だらっとしているわけではなく、ちゃんと考えて緩急をつけているのが分かる。その16分の「歩け らったった」のリズム好き。

7 タイムマシン/1640mP/初音ミク
まぁ普通。

8 Hello, Worker/KEI/巡音ルカ
有名曲らしいけど知らなかったのであんまり印象にない。

9 どりーみんチュチュ/emon/巡音ルカ
まぁ普通。

10 愛Dee/Mitchie M/初音ミク・巡音ルカ
コーラスが綺麗。
登場人数が2人になったぶん、ステージが華やかだった。

11 ドクター=ファンクビート/nyanyannya/KAITO


このツイートをみてコール覚えた。
「イエスマイドクター!」「(ラストの)大天才!」あたりが言えてよかった。
アップテンポでスウィング気味だからライブで引き立つな。


12 Nostalogic (MEIKO-SAN mix)/yuukiss/MEIKO
曲をあんまり知らなかったのでMEIKOの胸部しか見てなかったと思う。

13 どうぶつ占い/すこっぷ/初音ミク
この曲では初音ミクがショートヘアーになり、一気に子供っぽい印象になった。
「あ、モーション動画を作った人は分かってますね」と思った。

14 Calc./ジミーサムP/初音ミク
予習0だったので特に無し。

15 ウミユリ海底譚/n-buna/初音ミク
歌詞を楽曲に乗せるのがとても上手いと思う。
サビの出だしの「●_●●●_●●」というリズムに「待って わかってよ」とか「もっと縋ってよ」とか「泣いて笑ってよ」とかを乗せるのがとても上手い。常人にはできないセンスだなぁ。

16 テレカクシ思春期/HoneyWorks/鏡音レン
PV中にVOCALOIDのキャラが出ずに他のキャラが出る曲なのに、よく収録したなぁ。

17 スイートマジック/Junky/鏡音リン
歌い手が歌ってるバージョンより、リンが歌ってる方が好き。
「ぱっぱっぱらっぱっぱっぱらっぱっ……」で大合唱。

18 リモコン/じーざす(ワンダフル☆オポチュニティ!)/鏡音リン・鏡音レン
MIKU EXPOと被ってる曲。だから曲を分かってると油断して予習しなかったから、あんまりコール入れられなかったよ……不覚。

19 Baby Maniacs -Eight Mix-/八王子P/初音ミク
バンドメンバー紹介の直後の曲で、バンドの人達が前に出てきて歌ってた。
曲の途中で振り返って初音ミクのほうを見ながら演奏してたので、「なんかオタサーの姫を崇める男たちみたいな構図……」と思ってしまったw
予習0だったので特に無し。

20 ラズベリー*モンスター/HoneyWorks/初音ミク
「えーえむしっくす!」「ぴーえむしっくす!」が言えたので満足です。
サビで「ラズベリーモンスター」って部分の直後、付点8分のリズムなのね。みんな合わせてサイリウム振ってたね。

21 39/sasakure.UK×DECO*27/初音ミク
すみませんこれも知ってると思って予習しなかったら
「39(サンキュー)!」の合いの手、入れられなかったわ……
(1番でタイミングを学習して2番ではコールできた)

これは上側のスクリーンの使い方がとても良かった。感動的な映像だった。
たくさんの人が書いたVOCALOIDのイラストがどんどん流れてくる。一部のイラストは「最初は線画が出てきて、カメラがパンしてるうちに色がついて完成図になる」っていう形式だった。
文章だと上手く伝わらないのでもどかしいのだが、すごい感動的だった。

22 shake it!/emon/初音ミク・鏡音リン・鏡音レン
予習0だったので特に無し。
なんか以前からよく出てくる曲らしいけど。

23 ray/BUMP OF CHICKEN/初音ミク
何も知らずに聞いたらビックリするんだろうけど、予習済みなので驚きも特に無し。
メロディはいかにもバンプの曲という印象で、その旋律を初音ミクが歌い上げるのはなんだか不思議な感じだったが、なかなか合っていたと思う。

【アンコール】
24 Satisfaction/livetune/初音ミク
あれ、ミク? 鏡音レンじゃないの? ってなった。
http://www.nicovideo.jp/watch/sm28609108を見て予習してたせいだった。
元々はミク曲で、この動画はレンによるカバーだったのね。


25 なりすましゲンガー/KulfiQ/鏡音リン・初音ミク
最初のAメロの歌詞がなかなか印象的。けっこう好き。

26 Hand in Hand/livetune/初音ミク
先述の通り、マジカルミライ2015には行っていないのでこの曲に特別な思い入れはないのだが、それでもとても良い曲だった。

これの曲は先の「39」と並んで、上部スクリーンの使い方が非常に上手かった。
一部では手をつなぐ写真のスライドショー。この画像は去年にもあったことが、去年の動画では分かる。
https://www.youtube.com/watch?time_continue=116&v=s7h9tkfc7Eg

ただ去年と違うのは、マジカルミライ2016で撮った写真が登場したことだ。来場者やスタッフの人たちが手を繋いで笑っている写真が、スライドショー形式で流れた。
おそらく、ライブ前日の金曜日に撮影したものだろう。
想像力が並外れて優れた人なら、「手を繋いでいる写真」を集めていることから推測して、金曜日の時点でこの選曲を予想できたのかもしれない、



選曲(セットリスト)について



選曲は……うーん。微妙。
単純に、俺が知らない曲が多すぎてノリきれないってだけだが。
昔の曲を押しのけて最近の曲を大量に入れる必要あったかなぁ、という感は拭えない。

初めてライブを聞いた前回(MIKU EXPO 2016)との差分が激しすぎるからかもしれない。
MIKU EXPO 2016のセットリストは、なぜか知らんが往年の名曲ばっかりだったからなぁ。
今回はryo(supercell)もwowokaもNeruも居なかったな。


前回までのセットリストはどうだったんだろう?
今年のライブ前日の段階で知っていた曲が何曲あったか見てみよう。

2015年だと
「Tell Your World」「はじめまして地球人さん」「ロストワンの号哭」「リモコン」「スノーマン」「深海少女」「Sweet Devil」「アンハッピーリフレイン」「ロミオとシンデレラ」「Just Be Friends」「Packaged」「ワールドイズマイン」「ODDS&ENDS」「39」「ハジメテノオト」
で、27曲中15曲。

2014年だと
「ありふれたせかいせいふく」「Weekender Girl」「FREELY TOMORROW」「深海少女」「ワンダーランドと羊の歌」「Tell your world」「東京テディベア」「Last Night, Good Night」「ゆめゆめ」「ODDS&ENDS」で、22曲中10曲。

参考にしたのは以下のページ。
「マジカルミライ 2015」初日ライブのセットリストをお届け | インサイド
#マジカルミライ 2014 セットリストはこんな感じでした ~ ミクストリーム

うーん。26曲中5曲ってのはこれまでとくらべても特に少ないんだな。

twitterの中で、選曲について賛否を明言してない分析的な発言を集めてみた。











最後に



大したこと無いことだけど、覚えて書き残しておきたいので。

友達と二人でいって俺が右側に座ったから、俺の右隣が知らない人だった。
ライブの最中には身体が触れたりして「おいおいメッチャ汗かいてるじゃん……」と思った。
だけど、最後に全部の曲が終わったときに、隣の人がその右隣の連れとハイタッチして、それから俺と俺の友人にもハイタッチを求めてきたので
「いぇーいww」って感じで応じた。気分良かった。

色々書くとキリが無くなりそうなので、このへんで。
それでは。
  1. 2016/10/03(月) 01:25:36|
  2. 雑記
  3. | トラックバック:0
  4. | コメント:0

たこつぼと視野狭窄の恐ろしさ 「サイロ・エフェクト 高度専門化社会の罠」
2016/08/19(金) 23:40:27

たこつぼと視野狭窄の恐ろしさ 「サイロ・エフェクト 高度専門化社会の罠」


ジリアン・テットの「サイロ・エフェクト 高度専門化社会の罠」を読んだ。


どんな本?


「なぜ現代の組織で働く人々はときとして、愚かとしか言いようのない集団行動をとるのか」「なぜわれわれはときとして自分に何も見えていないことに気づかないのか」という問題を論じている。


サイロとは何か


で、筆者が言うには問題の原因は「サイロ」であるという。
サイロとは何か。俺もこの本を読むまで知らなかった。
情報システム用語事典:サイロ(さいろ) - ITmedia エンタープライズによれば、元々は「家畜の飼料や穀物などの貯蔵庫ないしは弾道ミサイルの地下格納庫のことで、英語では『窓がなく周囲が見えない』という意味がある。」そこから、他部門と連絡せずに視野狭窄に陥ってしまう状態を指している。
本の帯にも登場するが、日本語だと「たこつぼ」という概念がかなり近いだろう。

職業の世界は専門化が進み、隣の部署が何をやっているのかよくわからない。他のチームとは協力しないどころか、下手な場合には敵対する。自分と似たような人々とだけ交際する。視野が狭くなり、全体を俯瞰的に見ようとしない……という罠にはまるそうだ。


ソニーのウォークマンはなぜiPodに負けたのか


この本では、「サイロ」という視点から、8つの事例を分析している。
興味深かったのはソニーのウォークマンと、アップルのiPodの話である。
物語は1999年11月のラスベガスから始まる。コンピュータ業界の見本市「コムテックス」でソニーの出井伸之が新製品を発表した場面だ。

この時、出井は2つの同じような新製品を発表した。これが失敗の表れだったと筆者は言う。

1999年にソニーが一つではなく二つのまったく異なるデジタル・ウォークマンを発表した理由は、社内が完全に分裂していたためである。巨大なソニー帝国の異なる部門が、(中略)まったく異なるデジタル音楽プレーヤーを開発したのだ。 (p.78)



検索してみると、確かにその通りの発言が残っていた。

「開発部署の違いが製品に反映された。バイオミュージッククリップは名前のとおりパソコンの担当部署が開発したもの。一方のメモリースティック ウォークマンはオーディオ担当部署の開発品」(ソニーの説明員)。
ソニー,バイオミュージッククリップをメモリースティック ウォークマンと並べて展示 - 日経テクノロジーオンライン



1994年からソニーはカンパニー制を開始した。カンパニーどうしの間には厚い壁が出来てしまい、協力も意見交換もしなくなっていった。そういう文化が染み付いていたのだ。

その一方で、アップルは会社全体でアイディアを出し、iPodを発表した。ウォークマンはiPodにすっかり駆逐されてしまった。


おまけ。ウォークマンvs.iPodの話は「ワイドレンズ」にも書いてあったので、あとで比較してみたい。色々な本が何が敗因だと分析しているのか気になる。
ワイドレンズ―イノベーションを成功に導くエコシステム戦略


サイロ破壊に立ちはだかる抵抗勢力


この章の後半では、サイロの破壊に対し、それに抵抗する勢力の話を描いている。ハワード・ストリンガーに直接インタビューしたため、とてもリアル。当時の様子が生々しく綴られている。正直、後半のほうが印象に残った。

落ち目となったソニーはハワード・ストリンガーをCEOにした。ストリンガーは就任演説で「ソニーにはサイロが多すぎる!」と訴えた。サイロを破壊しようと、ルイス・ガースナーとIBMの取り組みを参考にした。

しかし思うように行かない。指示を出してもその通りに進んでいかない。ストリンガーは日本語が一切喋れない。そのため、自分の指示したとおりに進んでいるかをつぶさに確認することができなかったのだ。

ストリンガーは苦闘を続けた。しかし指示を出しても、あとになってそれがまったく無視されていたことが発覚するという状況が幾度も繰り返された。(中略)「私が東京本社に来て、一万人規模の人員削減か何かを発表したとする。でも次に戻ってくると、なぜか社員数はまったく変わっていないんだ」 (p.102,104)



衝撃だったのは、電子書籍リーダーの話。アマゾンが最初に発売する2年以上も前に、ストリンガーは本を読むための端末を作るように命じていた。しかし、収益を他部門と分け合わなければならないため、開発側は進んでやろうとしなかった。プロジェクトは遅れに遅れ、何も起こらなかった。それで今はどの会社が覇権を握っているかは、言うまでもないだろう。


まとめ



著者は経済誌の編集長だが、その前は文化人類学者という異色の経歴を持つ。第1章では人類学者ブルデューを主人公にして、文化人類学の成り立ちを説明する。
私たちは、今まで生きてきた文化、ものの見方に慣れ切っている。色眼鏡をずっとかけていれば、本来と違う色であることが気にならなくなる。同じく、ずっとある文化に浸っていると、それが当たり前になってしまい、それ以外の考え方なんてできなくなってしまうのだ。
この本は組織論にとどまらず、文化という視点から物事を論じているのが面白かった。

それほど人気があって売れているわけじゃないけど、とても良いビジネス書だった。今年を代表する傑作だと思う。もしビジネス書大賞にノミネートされたら嬉しいなぁ。

それでは。
  1. 2016/08/19(金) 23:40:27|
  2. 本・漫画
  3. | トラックバック:0
  4. | コメント:0

AtCoder Beginner Contest 036 木の独立集合の個数を求める
2016/06/11(土) 17:48:42

珍しく技術系っぽい記事を書く。

AtCoder Beginner Contest 036のD問題について。
D: 塗り絵 - AtCoder Beginner Contest 036 | AtCoder

問題の内容



グラフ理論の言葉で言い換えると
「与えられた木に対して、独立集合(independent set)の個数を求めよ。」となる。
独立集合 - Wikipedia

一般のグラフに対して、最大独立集合を求める問題はNP完全問題らしい。
そして独立集合の個数を数えるのも難しいらしい。↓の資料に書いてあった。
PowerPoint資料:木分解とグラフ・アルゴリズム(最適化と数え上げ)


ということは、グラフが「木であること」を利用しないと上手く解けないはずだ。
資料の中にも根付き木を利用して考える方法があったし、適当な頂点を根として計算するんだろう。

逐次的に(DPを用いて)処理するんだろうなぁ……
f(G)を与えられたグラフに対する独立集合の総数とすると、
・一点からなるグラフから始めて頂点を次々と追加し、f(G)を求めていく
・根付き木の部分木から順に、f(G)を求めていく
の2通りが思いつく。

競技時間中は前者かと思っていたけど、正解は後者。

AtCoder解説(※pdf)を見ると「根から遠い順に求めていけば良い」と書いてある。

プログラミング


なるほど、アルゴリズムとしては理解できた。
でもコードにできそうに無い。

深さ優先探索か何かをして、木の構造を入力する……??
各頂点に対して「この頂点の親はコレで、子はコレとコレです」みたいなデータを用意するの??
……?????

と、ワケが分からなくなったので皆の提出したコードを見ることにした。
言語はRuby。
Rubyで書かれた正答のソースコード一覧は以下から見られる。
All submissions - AtCoder Beginner Contest 036 | AtCoder

Rubyは初心者なので、読むのにだいぶ苦労したが、正解のコードは以下の2つの段階からなっている。

(1) 頂点どうしの関係性を配列に入力する
(2) 配列を元に、再帰的にf(x), g(x)を計算する

f,gは以下の通り。解説文から引用。
・f(x):頂点 x を親とする部分木に含まれる頂点をすべて白または黒で塗り,両端が黒で塗られた辺が存在しないようにする方法は何通りか?
・g(x): 頂点 x を親とする部分木に含まれる頂点をすべて白または黒で塗り,両端が黒で塗られた辺が存在しないようにする方法は何通りか?ただし,頂点 x は必ず白で塗らなければならない.


(1) 頂点どうしの関係性を配列に入力する



これは例を用いたほうが分かりやすいだろう。問題に載っていた入力例で考える。

5
2 5
1 5
2 4
3 2


5つの頂点からなるグラフである。

頂点1と繋がっているのは頂点5、頂点2と繋がっているのは頂点3,4,5、……という情報を順に配列に入れて
[[5], [3, 4, 5], [2], [2], [1, 2]]
というデータを作る。
ただし、実装する際はインデックスが0から始まるので、全ての要素から1を引いて
[[4], [2, 3, 4], [1], [1], [0, 1]]
という結果にする必要がある。

このデータの作り方はそんなに難しくない。枝のデータを1行ずつ読み込みながら配列に要素を追加すれば良い。

(2) 配列を元に、再帰的にf(x), g(x)を計算する



問題の解説文では、関数を定義するときはf(x)と書いてあり、xを引数にしていた。
しかし、実際のコードではf(x,p)と書かれているので「xとp」が引数である。
ではpとは何か。皆のコードを見てもしばらく分からずに悩んでいて、やっと分かった。
pは、xの親のノードである。
頂点xと繋がっている頂点の一覧は(1)の段階で作成した。
根ではない頂点を考えると、繋がっている頂点のうち1つは親、残りは子である。
関数の再帰では「頂点xの子それぞれに対して、値を求める」という操作をする。
これを言い換えると「xの隣接点の全てに対して、値を求める。ただし親pに対しては無視する」となる。

こうすると、各頂点に対して「頂点xの親は頂点pです」というデータを(例えば連想配列で)用意する必要はない。関数を呼び出す段階で、pを引数に入れればよい!
yをxの子とすると、f(x,p)を計算するにはf(y,yの親)が必要である。ここでyの親はxなので、関数呼び出しの際にはf(y,x)とすればよい。


アルゴリズムとコードの間のギャップ



解説文のアルゴリズムを読んで「納得した、確かにそのとおりだ」と思った。
しかし、コードを書こうとしても、どうすれば良いのか全然分からなくなってしまった。
つまり、解説文とソースコードとの間にギャップがあり、それを越えられなかったと言える。理論から実践までは案外遠いものである。
解説文とソースコードとのギャップは、まとめると次の2点だろう。

・「根から遠い頂点から順に求めていけばよい」と言っても、末端(グラフ理論では「葉」)を実際に指定する必要はない。根を指定して、子に対して再帰的に関数を呼び出せばよい
・そして「この点の親はどれか」という情報も明示的に保持しなくて良い。関数の引数に親の情報を入れ、子に対して呼び出す際にその点自身をパラメータに入れる

分かれば納得するけど、言われなきゃ気づかないぞ、これ。このギャップをどう埋めていけば良いんだろう。

ソースコード


そして俺が書いたコードがこちらです。
Submission #761133 - AtCoder Beginner Contest 036 | AtCoder
後学のために色々コメント書いといた。変数名もちゃんとしたものにした。時間制限があったらもっと適当な名前にすると思うw

あー。もっとrubyかけるようになろう。
それでは。
  1. 2016/06/11(土) 17:48:42|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0
前のページ 次のページ

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。