Browse Month: September 2005

Google Code Jam 2005

ここまで Google Code Jam 2005 の Qulification Round の問題をすべて解説してきました。僕はこの Round でダメだったわけですが、練習問題で Round 1 の問題を挑戦してみましたが、250 点問題しか解くことが出来ませんでした。

というわけで、僕にはこれ以上解説する実力がないということで Google Code Jam 2005 の解説は終了したいと思います。最後の Round に残った人の中には、なんと[女性](http://www.siliconvalleysleuth.com/2005/09/what_women_can_.html)もいたそうなので驚きです。

また、[この記事](http://www.siliconvalleysleuth.com/2005/09/google_code_jam.html)も参考になります。

Google Code Jam 2005 Qualification 750 II

Qualification Round 750 点問題の最後の問題です。問題のタイトルは、NewStation です。

この問題は、理解するのみとても時間がかかりました。というか、この問題に挑戦した人から問題の意味をきいてやっと理解できた問題です。英語の読解力は、ないとやっていけませんね。

この問題では、ある都市の1ブロックの人口比率が次のような形であらわされています。

{"111", "111", "111"}

この都市は、平均して同じ数の人が住んでいることがなります。

このデータに加えて、この都市にあるすべての消防署のデータが存在している位置として与えられます。例えば、

{"1 1"}

となります。

このデータをもとに、この都市に対してもう一カ所消防署を設置する必要がある場合は設置する消防署の位置を返しなさいというものです。消防署を設置する条件というのは、すべての人々に対してバランスのとれた消防署を配置する必要があるというのが、前提条件になっています。

問題の意味がまったく解説できていないと思いますが、回答コードは次のようになりました。

Continue Reading

Google Code Jam 2005 Qualification 750

750 点問題を紹介します。750 点問題は二種類ありますが、最初に紹介するのは ImageLayer です。僕は、この問題にあたりましたが時間以内に回答することができませんでした。原因は、問題文の量に圧倒されてしまったからです。

この問題はよくよく考えてみると、問題文をよく読む前に例題をみた方が問題の意味がすぐに分かりますので例題から紹介します。

この問題は、引数 macro のみをもち、例題ではデータになっています。

{"OPEN background", "OPEN aone", "OPEN atwo", "OPEN foreground", "MERGE 0-2", "OPEN border"}

引数 macro は、最初の OPEN や MERGE によってフォーマットが異なっていますが、OPEN の場合は “OPEN レイヤー名”、MERGE の場合は “MERGE レイヤー名1-レイヤー名2″というフォーマットになっています。

この問題は、Photoshop にあるレイヤーの機能を想像してもらうと分かりやすいと思いますが、引数 macro を順番に処理をしていって、最後の結果を返す問題です。

OPEN という macro は、レイヤーに単純に積み重ねるという意味で、MERGE はレイヤー名1からレイヤー名2までを、一つのレイヤーに結合させるという意味になります。また、MERGE は個別のレイヤー名をアルファベット順にしないといけません。

上の例だと、次のように解析されます。

  1. 0.background 1. aone 2. atwo 3. foreground
  2. 0.background aone atwo 1. foreground
  3. 0. aone atwo background 1. foreground 2. border

この例だと答えは、

{"aone atwo background", "foreground", "border" }

となります。すこしめんどうですが、回答コードは次のようになりました。

※共通コードは省略しています。

Continue Reading

Google Code Jam 2005 Qualification V 250

最後の 250 点問題の紹介です。問題のタイトルは、SalesFigure です。この問題が、今まで紹介してきた 250 点問題の中で一番時間がかかったと思います。

問題の内容は、ある会社の売り上げデータが、次のようなフォーマットになっています。

CLIENT_ID CNT_1 PRODUCT_1 CNT_2 PRODUCT_2 …

CLIENT_ID は顧客の名前、CNT_x は売り上げた製品の数量、PRODUCT_x は売り上げた製品の名称です。CNT_x と PRODUCT_x は、常にセットで最大 10 までデータがある可能性があります。

また、ある一つの顧客と製品の名称が与えられて、売り上げデータから顧客に対して製品を売り上げた製品の数量を返しなさいという問題です。

例題をみてみると、売り上げデータは次のようになっています。

{"BOB 1 SHOE", "JOHN 2 SHOE", "BOB 3 SHOE 1 HORSE"}

この売り上げデータに対して、顧客名 BOB、製品名 SHOE、が与えられます。この例では、1 + 3 で 4 つ顧客 BOB に 製品 SHOE を売ったことになります。

回答コードは、次のようになりました。このコードも同様に、共通部分のコードは省略しています。

Continue Reading

Google Code Jam 2005 Qualification IV 250

時間がかなり空きましたが、引き続き解説です。もうすぐ、Code Jam のサイトへはログインできなくなってしまうと思います。

問題のタイトルは、SongFilter です。SongRename と問題の内容が似ています。

ソング情報が、ジャングル-アーティスト-タイトル-アルバムのような形で引数で入ってきます。また、Filter の情報も引数に入ってきます。Filter は、例えばジャングルを jazz でフィルターする場合には genre=jazz となります。

歌とフィルターの情報は、それぞれ複数入ってきますが、フィルター後のソング情報を返しなさいという問題です。

この問題もとても簡単ですが、回答コードは次のようになりました。

前に紹介した共通コードは、省略しています。

Continue Reading

iPod nano Protection Sheet

iPod nano は、Apple Store Shibuya で買いますが、その前に iPod nano 用の保護シートを購入してみました。[Micro Solution iPod nano Film Kit #04](http://www.micro-solution.com/pd/ipod/inanofk04.html)です。

iPod nano

よくここまで我慢しましたが、初の iPod nano を購入しようと思います。

狙いは、iPod nano 4GB Black です。

Google Code Jam 2005 Winner

Google Code Jam 2005 の Championship Round が行われました。アナウンスは、[こちら](http://www.google.com/press/pressrel/codejamwinners_2005.html) ですが、優勝者は Marek Cygan さんでした。 Marek Cygan さんは、Warsaw University の学生だそうです。なお、上位3名すべてが学生という昨年とほぼ同じ結果になりました。

Google Code Jam 2005 は、今年で 3 年目で今年は 32 ヶ国、7500 人ものプログラマーが参加したそうです。

さっき、すこし Championship Round の問題をみてみましたが、とても難しそうな問題でした。もうすぐ、練習問題のサイトも閉じてしまうので駆け足で練習してみたいと思います。

GSA

すでに知っている人もいると思いますが、Google より [GSA : Google Secure Access ](http://wifi.google.com/download.html) がリリースされました。

これは、VPN (vpn.google.comを経由) して、安全なインターネットができるというフリーソフトです。それになんと、サンフランシスコ限定で無料の WiFi アクセスポイントも提供しているようです。

さっそく会社に後輩に教えたところ、がんばって使ってくれました! [詳細はこちら](http://kiui.dyndns.org/archives/2005/09/google_secure_a.html)。

プロバイダによって、PPP 接続を通さないとダメなようです。

GSA 経由でインターネットアクセスしている状態で、[確認君](http://www.uptop.com) でアクセス元の IP アドレスを確認してみたところ、ワシントンの [Cogent Communications](http://www.cogentco.com/) の所持している IP Address でした。

Google は、このフリーソフトを通じてアクセスログを収集することが目的のようですが、ビジネスにどうやって展開していくのか、とても興味があります。

  • 1
  • 2