子供の落書き帳 Remix

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

GMOエンジニアトーク -先端IT技術を学ぶ会- 深層学習、ブロックチェーン、AR/VR 参加レポート
2017/05/13(土) 14:56:23


2017年5月11日GMOエンジニアトーク -先端IT技術を学ぶ会- 深層学習、ブロックチェーン、AR/VR
にブログ執筆枠で参加してきたので、記事を書きます。

資料は後日公開される予定です。
(講演のうち一つはスライド見つけたのでリンクを貼りました)

会場はこんなところ。(講演終了後の写真です)
GMO170511.jpg

IoT領域でのブロックチェーン実践



ブロックチェーン技術の実用例として色々なアプリケーションを開発している。
そのサンプルアプリの1つが、今回紹介するスマート宅配ボックスである。
受け取り本人だけが解錠できる。

紹介動画:「本人のみが受け取れる宅配ボックス」の実証実験 - YouTube
プレスリリース:
GMOインターネット・GMOグローバルサイン・セゾン情報システムズの3社の共同実験。
セゾン情報システムズって、小野和俊さんがCTOをしている会社で、モダンなSIerになろうとしているというイメージだった。ブロックチェーンの実証実験に協力しているとは知らなかった。

ブロックチェーンの最大の特徴は、
ただそこにデータが記録されてるだけで「いつ・誰が・何を記録したか」が、第三者による証明なしに記録される
ということである。
なぜ客観的な事実の証明ができるのか?

技術としては、ハッシュ関数、公開鍵と秘密鍵を使っている。

例えば仮想通貨のやり取りの場合、Aさんは「私はBさんに100コイン渡す」という内容を自分の秘密鍵で暗号化する。
他の人は誰でもAさんの公開鍵を用いて暗号を復号することができる。
このとき「Aさんの秘密鍵で暗号化したものである」ことが確認できるので、内容が間違いなくAさんの書いたものであると確認できる。

前のブロックのハッシュ値が、次のブロックの入力に含まれている。
もしも内容を改竄すると、後続のブロックのハッシュが一致しなくなり整合性が崩れるので、改竄ほぼ不可能。

スマートコントラクトとは
ソースコードそのものを暗号化して通信する……らしいが、ちょっとついて行けなかった。
詳しくはブロックチェーンサービス利用ガイド · ブロックチェーンサービス(Ethereum)利用ガイドを見てくれと言っていたので、リンクを貼ってごまかすことにする。

■世界の事例
ゲームのカードの所有権を管理する
「ujo music」音楽の直接販売

不動産登記 新興国だと土地の登記が信用できないから、ブロックチェーンで正しさを担保する。
議決権の行使

ドバイはブロックチェーンのナンバーワンになろうとして、開発に多額の金を投じている。

■GMOの取り組み
やってみたこと
(1)ゲームのコンテンツ管理
そこまで厳密な所有権管理は必要ないのでは。やめた。

(2)個人所有データを管理する
→今ある共有サービスで良いと感じた。
「ブロックチェーンじゃないとできない」ではない。

(3)GMOポイントをブロックチェーン管理?
一企業の責任範囲ならでーびーでいいや

(4)KYC (Know Your Customer:顧客確認)
銀行に口座を開設するときに必要な書類手続きのこと。
金融の口座開設ては本人確認に数千円のコストがかかる。
検索したところ、2016年8月に楽天証券が開発開始してるな。これから競争激化するのだろうか。
日本初!ブロックチェーン技術を利用した本人確認(KYC)システム共同開発開始|楽天証券のプレスリリース

検討中:
特許のアイデア保管
内容を誰にも伝えずにアイデア発生日時を保証する

■Q&A

Ethereum使用で使用料金かかるけど、ほかのブロックチェーンにすることで手数料が無料にできないか?
お金かからない設定もできる、が、金がかかるようにしてある
DDoS攻撃をしようにも、お金を払わないと攻撃できないので、攻撃されづらいという利点がある。

国を動かすことについて?
スマートコントラクトは色々な企業を巻き込むので、必然的に国レベルの話になります
国のほうも、アイデア募集してる場面があるので(詳細は言えないけど)、意見を言えば国は聞いてくれると思う

モバイルAR技術の最先端 Google Tangoを活用してバーチャル道案内スタッフを実現してみた



発表資料
モバイルAR技術の最先端 Google Tangoを活用してバーチャル案内スタッフを実現してみた from bmkhuong


■概要
スマホのカメラ画面の上に道案内スタッフ(ユニティちゃん)を登場させる。
でユニティちゃんが画面内で歩いて、目的地までの誘導をしてみる。
スマホの画面の向きや位置を変えると、それに応じてユニティちゃんの映り方が変わる。

ショッピングモール……行きたい店は?美味しいご飯は? 行き方がわからない
地下鉄や駅……道がわからない

■内容
GoogleTangoとは
AR(Augmented Reality : 拡張現実)/MR(Mixed Reality : 複合現実)のプラットフォーム。
奥行き知覚、モーショントラッキング、領域学習という3つのコア技術を持つ。

スマホはLenovo phab 2 proを使った。
(現在、Tangoに対応している唯一の端末。ASUSが「ZenFone AR(ZS571KL)」を日本で2017年夏に発売予定。)

ランドマーク=特徴的な物体をいくつか記憶する
カメラの視野が広ければたくさんのランドマークを取得できて認識精度があがる。

■Q&A
空港だと広くて通路が取りづらく、人が通ることで学習したときと環境が変わって難しいのではないか?
変わりやすい環境だと学習や認識は難しい。Tangoの弱点

ビーコンによる誘導はできたりする?
現手法であまり頻繁に変わらない環境なら認識は簡単。ビーコンより経済的なのでは

目的地までプロットするの大変だから、目的地指定したら経路案内するようにできるか?
先にマーカーを付与しておけば経路探索アルゴリズムを適用することは可能。

■感想
案内の前に一度対象となる空間を歩き回って認識させ、経路案内用のマーカーを(スマホ上で)配置する必要があるのがちょっと面倒そうに感じた。
Tango自体は近未来感があって楽しそう。

高橋ゆうこう

深層学習は金融市場をシミュレーションすることができるか?



■イントロ
2016年のヘッジファンドの成績を見ると、AIを使ったファンドだけ利益を上げている
最終的な目標は人工知能による資産運用を確立すること
今回はそのためのシミュレーション方法の開発、環境の構築を取り上げる
シミュレーション用のデータを増やしたいので、GANを用いて為替(ドル円)のデータを生成する。

イントロ、がんとは何か、実験計画、シツケン、まとめ、

■GANとは何か
Generative Adversarial Network
generator(データを生成するもの)とdiscriminator(真贋を見分けるもの)を同時に学習させる手法。
詳しい解説を見つけたので参照。はじめてのGAN
今回は深層学習のDCGAN(Deep Convolutional GAN)を使った。

CelebA という、世界のセレブの写真20万枚のデータセットを使って、新たな顔を生成するデモ。
Large-scale CelebFaces Attributes (CelebA) Dataset
フレームワークはTensorFlow。

■実験

2001~2015年のドル円相場のグラフから連続する100日分を切り出し、
100×100のpng画像に直す。合計3000枚程度のデータでDCGANを実行した

人工的なデータ(一直線のグラフとか、明らかに違うもの)をdiscriminator(判別器)に入れた
→判別成功

もう少しホンモノに近いデータを、モンテカルロ・シミュレーションで人工的に生成する
日々の差分がガウス分布(?)に従うように生成した? データをdiscriminator(判別器)に入れた
→判別成功


■Q&A
シミュレーションでデータ増やそう、という動機は何か? 値動きのシグナルを学習させる手法で上手くいくので、データを増やす必要はないのではないか?
根本にあるのは「値動きを的確に当てて大儲けするというよりは、環境の変化に強い安定したロジックを開発したい」というもの。
最終的にはほったらかしでAIに任せるやつを作りたい


画像でやる動機は? 最初に数値データがあるので数値のほうが扱いやすいし、画像にするとデータ量が増えるのでは?
(私の質問。100日分の終値の数値は100次元だが、100×100のpngだと10000次元データなのでわざわざデータの次元を上げる理由が気になった)
人間の視覚的な見た目による直感を取り入れるとどうなるのかを見てみたかった
ある程度ギャンブルで、試しにやってみた感じ。上手く行ったので結果オーライ。

2001年より前のデータでテストしたか?
今回はデータを入手できなかった。


以上。GMOの皆さんありがとうございました。

  1. 2017/05/13(土) 14:56:23|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0

ザ・黒帯 ~ Yahoo! JAPANのエンジニアの働き方とキャリアを語る 内容メモ #devsumi
2017/02/24(金) 01:14:52

Developers Summit 2017に初参加してきたのでレポートなど。この記事では下記のカンファレンスの内容をまとめています。
【16-A-7】 ザ・黒帯 ~ Yahoo! JAPANのエンジニアの働き方とキャリアを語る | Developers Summit 2017
システム上は満員になっていたけど、実際の会場では結構空席があった。申し込んだけど聞きに行かなかった人が多いのかな。

注意事項
聞きながらガーッとメモを書いたので、内容が完璧に正しい保証はありません。

登壇者 (詳しい経歴はdevsumiの公式ページを参照)
楠 正憲 (黒帯 プライバシー・セキュリティ @masanork)
伊藤 宏幸 (黒帯 アジャイル開発プロセス @hageyahhoo)
倉林 雅 (黒帯 認証技術(ID連携) @kura_lab )
里山 南人 (黒帯 Androidアプリ )
司会者:斉木 崇 (CodeZine編集長 斉木 崇(編集部)について:CodeZine(コードジン))

黒帯制度:実績を上げている優秀な人材を正しく評価するという目的で設立された。約50人が任命されている。Yahooのエンジニアの中の、トップ2%に位置する。6代目が21人。今日登壇しているのはそのうちの4人である。

【 】の中は、斉木さんの質問文の要約である。


【事前に話を聞くと、現在のIT業界に対して懸念があるということだったが?】
ある業務を電子化しようとする際、昔はできる技術が限られてたから、仕様は決まっていた。しかし、今では技術が進歩したし、ユーザーもHTML5の新しい技術をFacebookやTwitterなどで普通に使っている。技術が複雑化している。それを言葉に表して仕様に落とすのが難しくなってきている。結果として、受託開発で回せる難易度と内製で回せる難易度の差が広がっている。
また、事前に仕様を決めきれないシステムは、ビッグデータ解析に関係するシステムなどでますます増えるだろう。そのようなシステムは、内製じゃないと構築できないと思う。Yahooはエンジニアをたくさん抱えているから良いが、日本全体で見ると内製で全部できる会社は多くないだろう。

【黒帯との関係は?】
困りましたね。そこまで関係ないかな。ただ、いろいろな人に会い、国際会議に出たりできると、日本のやり方が必ずしも当たり前じゃないことが分かる。日本の社会構造の中で何ができるんだろう、ということは、外での活動の中で発見できるかと思う。


里山
【プロダクトのスピード感、意志決定の速度について】
2010年以降、CyberAgentやDeNAなどを経由して今に至る。Yahoo!はこれらの企業に比べると、職務の階層が多い。SIerほどとは言わないが、それに近いかな。ボトムアップで変えていきたいという現場の思いが上に届きづらい。どこかでトップダウンの話に変換できないといけない。トップダウンに変換するためには、大義名分が必要になる。大義名分を持っていて、ちゃんと背景が分かる人が介入していく必要がある。

【今後はどういう活動がしたい?】
弊社はアプリ開発数が多い。小規模で開発運用してるアプリが多い。リソースのバランスが上手く行ってない部分がある。人を採用できるように、Yahoo社として技術のブランディングをしていきたい。


伊藤
【組織横断的なことをしたいという話だが?】
アジャイルは「アジャイル開発」という名前で呼ばれることが多い。そのため、開発だけに閉じたものではないかと思われがちである。しかし、開発が上手くいっても、マネジメント層や経営層に否定されれば、そこで終わってしまう。以前の経験で、取締役にアジャイルOKのゴーサインをもらって、それを受けてアジャイルを推進した経験がある。だからYahoo!でも同様に、アジャイルな考え方を社内に浸透させていきたい。

【黒帯は単なる認定制度なのか、権限があるのか?】
活動資金は年100万円支給される。上司の決裁も不要なので裁量がある。
その他、書籍執筆、対外講演など、外で活動する機会を多めに与えてもらえる。


倉林
【担当業務とのしがらみとか】
黒帯になると、社内外の人が課題を抱えていていろいろと相談されることが増えた。
技術の導入にはハードルがあって、ID技術はYahoo!のいろいろなサービスにつながるから、社内調整が大変。コスト面、ビジネスのメリットを全社に説明できれば社内導入できるので、そういうやりがいを感じて取り組んでいる。


伊藤
【プレイヤーとして輝き続けたい。マネジメントにいくラットレースからの脱却】
前職では、アジャイルのコーチとして4年ほど活動してきて、現場に入って一緒に仕事をして改善活動をする、を続けてきた。しかし、前職でそれができなくなった。なぜならアジャイルの施策をやる自分の部署が廃止されたから。それと、技術者で上に行くキャリアパスがなかった。マネージャーの狭き門を目指して他の人と競争しなければいけない。社内改善活動で貢献したいのに、マネージャーに行かなきゃいけない。それはやだなといって転職した。Yahoo!ではエンジニアのまま技術を極めて、黒帯を取ることも可能。

【居心地は?】
良いところ:
黒帯だから、といろいろな人からコンタクトをもらえる。取締役まわりとのコネクションも増える
悪いところ:
自分の言動に対して、周りがしっかり注目しているので厳しい。有名税みたいな感じかな。


倉林
【プレイヤーとして黒帯】
新卒で入社して丸6年たつ。チームの中でも中堅、ベテランに近い立場になり、マネジメントも求められる。マネージャーとしてではなく、黒帯として技術を追求している。現場で実際に開発をして気づけることがたくさんあるので、経験値を貯めて次に向けて充電している感じ。

里山
【企業の対外的なブランディング】
Yahoo!って、企業ブランディングではWEBの会社という印象が強く、アプリを作っている会社という印象は薄い。渋谷や六本木の会社がアプリエンジニアをブラックホールみたいに吸い込んでるけどw、アプリの技術に関しても発信していって、Yahooのブランドを確立していけたらと思う。

【紀尾井町に本社が移転して、良かったという話を聞いたが?】
17階にコワーキングスペース「LODGE」ができました。
外部の人を招いて勉強会を開催して、弊社との交流を進めていこうとしている



【ブランディング】
会社のブランドとしては、自分はとてもリスキーな行動をしていると思う。会社に言われないのに勝手にビットコイン調べまくってるし。国の立場かYahoo!の立場なのかよく分からなくなってくる。
標準化も含めて国際会議に出ていったりとか、Yahoo!としての場をつくっていこうとしている。

【黒帯について英語で説明するの?】
おまえ空手やるのか? とか言われたw 海外企業にもdistinguished engineerという制度があるのだろうが、黒帯制度について海外勢に伝えるのが大変だったりする。


里山
【コミュニティ】
以前、Android黒帯の全員で書籍を出したんだけど、そこでの話として、エンジニアの中級者以降って本を買わないよね、というのがあった。
初心者向けの本は売れるけど、中級者以上の人は、本を買わずにQiitaとかWEBを見て情報を得る。
参考:「黒帯エンジニアが教えるプロの技術 Android開発の教科書」を執筆しました - Yahoo! JAPAN Tech Blog
コミュニティ運営に関与する中で色んなエンジニアと出会うことがあって、自分の状況を見たときに会社に対してどういう風に貢献できるのか、どんなノウハウを伝えられるのか、ということを考えさせられた。


倉林
【OpenIDのほうとの関係は?】
黒帯の前は OpenID ファウンデーション・ジャパンのエバンジェリストだった。
黒帯になってからはYahoo!内の専門家として発信する機会も増えた。もともとYahoo!は社外の技術を吸収しやすい文化。黒帯のおかげで社外発信の機会は増えてきて、活動しやすくなってきた。
後継者をどう育成していくかは課題だと思う。活動自体はやりやすいので、自分の得意技術についてがんがん発信したい人はYahoo!に来るといいと思う。


伊藤
アジャイルというのは、教育方法として優秀だなと思っている。アジャイルだと、メンバーにすごく高速に失敗を経験させて、問題発見・解決・改善を積み重ねていく。その結果、メンバーが自分で動いて考えていく。自走性が育めるいい手段だと思う。
黒帯をうまく利用して、多くのプロダクトチームに、よりよく失敗を経験させて成長をさせていこうとしている。気づかせるために厳しく当たることもある。
【厳しく当たった例などある?】
何でも他人に丸投げしてしまう人の集団がいた。彼らが丸投げをしたら、投げた先にたくさん仕事を振って、仕事をパンクさせて「丸投げしたら仕事が立ち行かなくなる」という状態にした。リリースが遅れそうになる程度まで、それをやったことはある。それでも結果的にはうまく行った。
  1. 2017/02/24(金) 01:14:52|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0

LPIC レベル1 101試験にボーダーギリギリで合格。勉強方法と反省を書くよ
2017/01/24(火) 00:55:17

1/22(日)に受けて、1回目で合格しました。

勉強の方法と内容 問題集は専らPing-tに頼った


勉強方法について。
参考書(問題集)は、定評のある「Linux教科書 LPICレベル1 Version4.0対応(中島 能和)」の紙版を購入した。
通称、あずき本(小豆本)。カバーがあずき色をしているからこのあだ名になったんだろうが、誰がこの名前をつけたんだろうw


問題を解いて覚えていかなければいけない。しかし、Ping-tという素晴らしいサイトがあるので使い倒すと良い。
101試験の問題は会員登録すれば無料で使えるので、これを使った。
(102試験の問題は有料)

仕事後や休日にPing-tの問題をチョコチョコ解いていって、分からないところは適宜あずき本で勉強した。
あずき本の章末練習問題・模擬試験は、パラパラ眺めることはあったが、解かなかった。

Ping-tの問題集のうち、銅を20%、銀を70%、金を10%くらいにしたところで試験日を迎えた。
Ping-tでは、問題ごとの回答状況に応じて「この問題は銅」「この問題は銀」などと自動的に分類される。
「銅」は未出題もしくは直前不正解の問題である。

あずき本によれば、合格ラインの正答率は65%(非公式)である。
80%の問題は一度正解できているから、少し間違えても65%は解けて、合格できるだろう。
俺はそう楽観的に考えていたが、その考えがロイヤルミルクティーなみに甘すぎたことを思い知ることになる。


試験感想 ギリギリで合格、試験最中にかなり焦った


試験開始。
あれ、見たことの無い問題があるぞ。それもかなりたくさんあるぞ。
ヤバい!! これは落ちるかもしれない!!
と思いながら、無理矢理全部の問題に解答した。

解答を終えるとすぐに採点され、自分の得点と合否が画面に表示される。
ボーダーラインちょうどの500点で合格した。
あずき本によれば合格ラインは約65%(非公式)らしい。
俺の正答率もその程度だろう。

受験料は15000円 + 消費税8% = 16200円。今まで受けてきた情報技術者試験(5700円)と比べても3倍近い値段である。あと1問でもミスってたら、高い金を払って不合格になっていただろう。危ない危ない。


反省点 なぜこんなに危ない成績だったのか?


なぜこんなに危ない成績だったのか?

■選択式の問題ばかり解いていた
Ping-tの問題集は、条件に当てはまる項目を選ぶ選択式問題であった。
俺はひたすらPing-tをやり続けていたので、選択式問題ばかり解いて勉強していたことになる。
しかし、あずき本の最初のほうをみると、択一式(1つの答えを選ぶ)・複数選択式(複数の答えを選ぶ)の
ほかにも入力式問題があることが分かる。
この本の練習問題には、コマンド名・オプション・ディレクトリ名などを答えさせる問題がある。
これらの問題に対処できなかったのが原因だろう。

なお、Ping-tにはコマ問という、「正しいコマンドを入力させる」問題がある。
これは入力式問題の対策になるだろう。
コマ問をさっき試しにやってみたらボロボロだった。コマ問もやる必要があったんだ……

■実機で練習しなかった
家で使っているのはWindows 7だが、それにLinuxを入れず、ネットと本だけで勉強してしまった。
早いところ仮想化を使ってLinuxを入れておこう。
LPICの試験は実機を触って確かめておけば慣れて覚えやすくなると思うし、
また、合格できても実機で実際に使えるようになっておかないとダメだろう。


102試験に向けて 合格のための勉強方法を考えた


■Ping-tで有料会員の申し込み
■参考書(問題集)のあずき本の102試験範囲を一度軽く流し読みして、「だいたいどんなことが聞かれるの?」を把握する
■Ping-tの問題集を解いていく
■Ping-tのコマ問を解いていく
■仕上げにあずき本の章末問題・模擬試験を解く
■特に覚えられない問題は、Ankiにも入力し、解いていく

Ankiは暗記用のソフト & Androidアプリ。現在はLPICの問題を一部Ankiに入れている。


目的 そもそも何のために受けたのか


試験でLinuxサーバ使うし、Linuxの知識を深めて行ければ良いと思って受験を決意したのだが。
いざ勉強すると、コマンド覚えたりオプション覚えたりと、細かい知識が多い。
「nlコマンドはデフォルトだと空白行にも行番号をつけます、空白でない行だけに行番号をつけるには
何のオプションが必要でしょうか? (答え:-bt)」みたいな問題が出てくると
「いやnlとか使わんし、それ調べたくなったらmanを見ればいいじゃん。覚える必要ないじゃん」と思ってしまう。
もうちょいLinuxの全体像みたいのを習得したいんだけど、いい方法無いかなぁ。

102試験だとネットワーク系のコマンドも出てくるし、
将来「あれ、なんかサーバのネットワークが不調だぞ」ってときに役立つかな。
役立つといいな。

それでは。
  1. 2017/01/24(火) 00:55:17|
  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

「プログラマー”まだまだ”現役続行」をプログラマーになる前に読んだ。
2012/12/07(金) 00:54:13

今日の出来事。
・ロフトにて花津ハナヨの『ただいま「かくれ人見知り」が平静を装って生活しております。』をしばし立ち読み。で、いま朝日新聞の今日の夕刊を見たけど、雑誌STORYの広告漫画、これ同じ花津ハナヨの絵じゃないかなー。違うかなー。口の下側に一本線を描くところとか、女性の割に妙に凛々しい(男っぽい)顔になってるあたりとか。どうかなー。
・たかまつやよい「流されて八丈島 マンガ家、島にゆく 5年め!」もしばし立ち読み。藤島じゅんのtwitterで見たのでした。この手のエッセイ系漫画って、いつ頃から世に出たのだろうか。2chにある「××だけど質問ある?」とも似てるよね。

……さて、以下は10月に書きかけていた記事を焼き直し。

プログラマー”まだまだ”現役続行 (技評SE選書)
プログラマー”まだまだ”現役続行 (技評SE選書)



2年半務めたSIerを退職しプログラマとして再スタートを切ることにしました - seri::Programing Diary
このエントリーで「就職活動を始めた頃に読んで衝撃を受けた」と書いてあって気になっていたのだが、
図書館でたまたま見つけたので借りてきた。


プログラミングの技術を磨くために必読の本を具体的に挙げていて参考になる。
(amazonレビューでも、その本の一覧を見られる)

色々なブログなどで
「プログラマーになったら絶えず勉強し続けなければいけません。
プログラマーとはそういう職業ですよ」と書かれてあったが、
あらためて本当にその通りだと実感した。


あと、p62~63で
「大学で、データ構造とアルゴリズムやその他の基礎技術を、プログラミングの演習を通してきちんと学習していれば、卒業するまでにかなりの量のプログラミングを行っていることになると思います。
そして、大学でのプログラミングを通して、自分自身がソフトウェア開発に向いているかいないかも、ある程度判断できるはずです。」
と書いてあってギクリとした。
自分は「かなりの量のプログラミングを行っている」だろうか? と。
そして、「自分自身がソフトウェア開発に向いているか」? と。

当然ではあるが、学校・学部(研究科)・学科(専攻)であっても、プログラムをどれだけやっているかは個々人によって異なる。
ウチの専攻にも情報という単語は入るが、あくまで基本は数学である。
数学まわりで研究するためプログラミングは最小限、という人もいれば、研究でガンガンコード書いて、さらに研究外(趣味orアルバイト)でもプログラミングしてます、という人もいるわけで。
ええ、俺は前者です。プログラミングはあまり経験を積んだわけではありません。
……学校外で一回やろうとしたけど思いっきり頓挫したんだったわ……
んで、向いているか、というと……こっちも怪しいよなぁ。


あとがきの
「避雷針の発明で知られるベンジャミン・フランクリンは、『知識への投資は常に最高の利息がついてくる』と述べていますが、本書は、私が自分自身への投資として何を行ってきたかをまとめたものであるかもしれません。」が
興味深かったので抜き出しておく。
現状ではなにぶん金がないので、読みたい本もこうして図書館で借りてこなければならないし、
なかなか読みたいと思った本をすぐに買うことは出来ない。
技術書にせよ一般書籍にせよ。
しかし、社会人になったら(なれたら)今よりはずっと多い給料が入ってくるので、
その中でちゃんと一定量の金を充てて『知識への投資』を行いたいと思う次第である。

それでは。
  1. 2012/12/07(金) 00:54:13|
  2. プログラミング
  3. | トラックバック:1
  4. | コメント:0
次のページ

FC2Ad