2011年12月3日土曜日

第11回中国GTUG勉強会

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

DevQuizへの参加

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

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

  • スライドパズル
    • 解決するための定石
    • 幅優先探索
      • 1手後、2手後の状態を保持して、ゴールの状態になるかを調べる
    • 双方向探索
      • スタートとゴールから幅優先探索
    • でも、最短経路を見つけるのは無理!という結論
      • 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問の問題
        • 予選で1問以上の問題で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のサイトで公開します。