第１１回中国GTUG勉強会

第１１回勉強会を開催しました。内容のメモを残しておきます。

DevQuizへの参加

• Googleの開発者向けイベント
• できるだけ能力の高い人に参加してもらうため
• より多くの開発者に参加してもらう
• 公平な選抜方式
• イベントの前に開発者に楽しんでもらう
• ウォームアップ問題
• Google技術のトリビア
• 分野別問題
• Web Game
• JavaScriptを使った神経衰弱
• Go
• PNG画像を与えられて、何色の画像があるかを調べる
• Android
• AIDLを使ってデータを抜き出す。
• Google Apps Script
• 一人ゲーム
• スライドパズル

• 参加者：3000人
• 通過者：1000人
• ボーダー：100.56点／150点
• スライドパズルは、結果を探索するコードをバグ無くかければ。。
• スコア分布
• 100〜110点のところに大半の方が分布
• 問題作成チームのコメント
• みんな頑張りすぎ。
• 30人も満点を取るとは思っていなかった。

• スライドパズル
• 解決するための定石
• 幅優先探索
• １手後、２手後の状態を保持して、ゴールの状態になるかを調べる
• 双方向探索
• スタートとゴールから幅優先探索
• でも、最短経路を見つけるのは無理！という結論
• 20Byteぐらい保持して、2億通りなので、4GBぐらいになる。PCではこれが限界。
• ゴールに近づいたかどうかを評価する関数を準備。
• 当然、壁の有無も考慮しなければならない。
• この時点で844問／5000問
• 評価関数に一工夫をする。
• 先に盤面の真ん中を揃えると、左上を揃えに行く時に乱される。
• 無駄が多くなる。
• 人間だと左上から揃えるようにする。
• 人間が解決する方法を考えると解決策が思いつく場合がある。
• メモリの省力化
• 経路を1byte保持→2bit保持へ。
• intをint8_tへ。
• 4000問ぐらいまでは結構行ける。
• 難しいケースの対策
• 通路のようになっているケース
• 4966問／5000問
• もっと難しいケース
• 結局、手動で解いた。
• 5000問／5000問
• 手数は12426手余った。
• 最長手数は303手
• 思考・コーディングは40時間
• 計算時間は40時間
• 最後の手動の問題を解くのに10時間位
• 言語はC++で。
• 処理速度が重要
• 寝るときに計算し始めて…
• 起きた時に終わる or 丸一日
• C++11は便利
• 拡張for
• 型推論のauto
• ラムダ式
• サイズを指定できる整数型
• 実装上のほそぼそとしたこと。
• 盤面サイズをテンプレートパラメータ化
• 1.5倍ぐらいの速度向上
• ただし、コンパイル時間は16倍…
• Samurai Coding
• TopCoder
• Code VS
• AI Challenge Ants（スポンサーがGoogle）

• 近似解を求めるプログラムの重要性
• 「アルゴリズムイントロダクション」の練習問題より。

• NASA TopCoder Challenge
• NASAがスポンサー

• 身につく能力
• ボトルネック以外を最適化する無意味さ
• 面白いぐらい無意味なんだそうです。手を付けやすい所からやってしまうという人間の性も。
• 実装の難しさと効果を天秤に掛ける感覚
• コードを綺麗に保つことの大事さ
• 後で改造が難しくなる
• 作業管理
• バージョン管理は大事！

• EXP-Hackathon
• WebIntents、GITKitを使って簡易画像ピッカー
• 自動飲み会幹事システム
• Hangoutsを自分のガジェットに埋め込む
• etc

Google Code Jam Japanに参加した

• TopCoderは言語の縛りがあるが、Google Code Jamについては、縛りはない。
• TopCoderはAppletか何かで動作しなければNGとなるかも？
• Google Code Jam Japan
• 問題は3〜6問
• SmallとLarge
• Smallは制限時間4分（再挑戦可能、即答される）
• Largeは制限時間8分（時間内に限り、再挑戦可能）
• テストケースの入ったファイルをダウンロードし、実行結果をソースコードと一緒に提出
• 各問題の得点と回答した時間で順位が付く
• 競技の流れ
• 参加登録（2月中旬登録開始）予選終了前なら登録可能
• 練習問題
• 予選（10/1 13:00〜19:00）
• 6時間で3問の問題
• 予選で１問以上の問題でSmall、Largeの両方を解いた人のみ
• 600人程度
• 決勝（10/8 13:00〜16:00）
• 3時間で5問の問題
• 戦略
• 言語：Java（Eclipse）
• 予めプロジェクトを作成しておく
• ファイルを読み込み、出力するというテンプレート的なコード等
• 先に問題を全部読んで、解けそうなものから解く
• サンプルの入力・結果で確認
• 問題にサンプルの入力、結果がある。
• 予選
• B問題はコーヒーの幸福度、賞味期限を扱う
• C問題はビット数を数える
• 決勝
• 手も足も出ず
• 長さを持つアンテナのエレメントを並べて、感度が良くなるパターンを算出。みたいな問題など

Google Developer Day 2011のフィードバック

• 技術的な情報を紹介するイベント
• OAuth1.0→OAuth2.0へ！
• OAuth2.0とOpenID Connectによる認証
• Google Identity Toolkit
• Account Chooser

• Google APIs Consoleで登録
• OAuth2.0のaccess_tokenを取得
• Scope　https://www.googleapis.com/auth/userinfo.mailなどを指定。
• Account Chooser
• https://account-chooser.appspot.com
• 認証で使うウィジェット
• 認証はGoogleなどのクラウド側に任せてしまって、アプリケーションの開発に力を注いだほうがいいのでは？

• Chromeのデベロッパーツールについて
• HTML/CSSの編集・更新、差分履歴、バージョン管理
• スタイルシートの変更をリアルタイムに反映
• 定義を追加も可能
• 補完機能
• 差分履歴、バージョン管理
• 変更履歴が残る
• 指定するバージョンに戻すことも可能
• Firebug CommandLine APIとの互換もある。
• リモートデバッグ

• HTML5のオフライン機能
• バイナリデータの保存
• File System API

と、言う感じで、タイムアップ

資料は、公開されたら中国GTUGのサイトで公開します。