GCJ2012 Round 2

Google Code Jam 2012 Round 2 が終わりました。
Problem A. Large すら通らない惨澹たる結果…orz
一応今年（GCJ2012）の目標は Round 2 だったのでそれは達成できてるわけですが。

配点は
Problem A.（Small 5pt、Large 9pt）
Problem B.（Small 6pt、Large 15pt）
Problem C.（Small 13pt、Large 14pt）
Problem D.（Small 8pt、Large 30pt）
Round 3 への進出ボーダー（500位）は 35点（1時間49分13秒）、
Tシャツプレゼント（1000位）は 21点（2時間33分←ギリギリ提出+ペナルティ）のようです。

配点のバラつきがあるので、Problem A. Small&Large + Problem B. Small では 20点にしかならないので1000位にも入れません。難易度と好み／得意不得意もありますが、Problem B. や Problem C. の Small&Large を目指して先に解くのがよいプランなのかも。
Problem D. Large は30ptですが1人も正解者が出ていません。（まさかまた採点バグとか…ないよね^^;）

問題の英文読解だけで1時間くらいかけてる気がするのでもっと効率的に時間を使わないと。。
今回で言うと Problem D. は最初から捨てて問題はチラ見する程度で読解せず、Problem B. か Problem C. に集中するべきだったのかなと。でも問題読まないと自分が挑戦できるかどうかわからないので難しいですよねー。

ともあれ今年のチャレンジは終わりました!
来年は Round 3 を目指して（その前にTシャツ目指すのがいいのかな）、復習しておきたいと思いますﾉｼ

Problem A. Swinging Wild	未稿	未稿	N/A
Problem B. Aerobics	未稿	未稿	N/A
Problem C. Mountain View	未稿	未稿	N/A
Problem D. Descending in the Dark	未稿	未稿	N/A

GCJ2012 Round 1C Problem C. 解き方

Google Code Jam 2012 Round 1C
Problem C. Box Factory 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1C Problem B. 解き方

Google Code Jam 2012 Round 1C
Problem B. Out of Gas 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1C Problem A. 解き方

Google Code Jam 2012 Round 1C
Problem A. Diamond Inheritance 解き方

実践したソースは このあたり（再帰版） にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1C Problem C. 問題紹介

Google Code Jam 2012 Round 1C
Problem C. Box Factory 問題紹介

工場の組み立てラインが2つあります。一方は箱を、もう一方は箱に入れるおもちゃを作っています。（ベルトコンベアーをイメージすればよいかなと）

箱もおもちゃもいくつかの種類を作っていて、箱に同じ種類のおもちゃを入れて出荷します。違う種類の箱とおもちゃの組み合せの場合は、箱を捨てて次の箱にするか、おもちゃを捨てて次のおもちゃにします。（問題文では You can always throw out と言っているので同じ種類の箱やおもちゃを捨ててもかまいません）

箱もおもちゃも、ラインで作られる順に使うことしかできません。
最大いくつの箱&おもちゃペアを出荷できるでしょう、、という問題です。

例（Sample 2つめの場合）:
箱：①①①①①①①①①①②②②②②②①①①①①①①①①①

おもちゃ：①①①①①②②②①①①①①①①①①①②②②①①①①①

⇒ ①①①①① を作ったあと おもちゃ②②② を捨てて ①①①①① を作ります。その後 箱②②②②②② も捨てて ①①①①① を作り、おもちゃ②②② を捨てて残りの ①①①①① を作ることで20個出荷することができます。

例（Sample 3つめの場合）:
箱：①①①①①①①①①①②②②②②②①①①①①①①①①①

おもちゃ：①①①①①②②②②②②①①①①①①①①①①②②②②②②①①①①①

⇒ ①①①①① を作ったあと、こちらは 箱①①①①① を捨てます。②②②②②② 、 ①①①①①①①①①① を作って残りの 箱②②②②②②①①①①① を捨てて 21個出荷することができます。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行には2つの整数 N と M が書かれています。
続く行には a1 A1 a2 A2 ... aN AN という具合に 2×N 個の整数が書かれており、これは「種類 A1 の箱 a1 個、次に種類 A2 の箱 a2 個…」が流れてくることを示しています。
問題の3行目は同様に b1 B1 b2 B2 ... bM BM としておもちゃの生産数が示されています。（「種類 B1 のおもちゃ b1 個、次に種類 B2 のおもちゃ b2 個…」）

データ制限:

• 1 ≤ T ≤ 100 （問題数100問）
• Small input の場合：1 ≤ N ≤ 3、1 ≤ M ≤ 100
  Large input の場合：1 ≤ N、M ≤ 100
• 1 ≤ ai、bi ≤ 10¹⁶ （一度に流れてくる箱・おもちゃは最大10¹⁶個（超たくさん））
• 1 ≤ Ai、Bi ≤ 100 （箱もおもちゃも最大100種類（順番とは限らない））

解き方はいずれ記事にします。
解いたコードはこちらにあります。

GCJ2012 Round 1C Problem B. 問題紹介

Google Code Jam 2012 Round 1C
Problem B. Out of Gas 問題紹介

車のガソリンが無くなってしまったけれど、幸運なことに今は丘の上にいるので、坂を下ってふもとの家までなるべく早く帰り着きたい… という無茶苦茶な設定のお話w
ただし丘の途中に車（前走車）がいて追い抜くことはできません。ブレーキを使って減速することはできます。

スタート時、自車は山頂 0m地点にいて静止しています（0m/s）。その後等加速度（a m/s²）で動いていきます。初速度を v0 とした場合、t 秒後の位置は

v0 * t + 0.5 * a * t²

で求められる、、というヒントがあります。

前走車はスタートから ti 秒後に山頂から xi mの地点にいます。ti 秒から ti+1 秒の間は等速で xi mから xi+1 mまで移動します。（ti 秒のところで前走車の速度が変わります）
自車も前走車もその大きさは無視できて、「点」と考えることができます。自車は前走車を追い抜くことはできませんが、ピッタリ後ろにいる場合、前走車と同時に自車も家に着くことができます。（前走車より早く家に着くことはありません）

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行には、家までの距離 D、前走車の位置情報の数 N、加速度のパターン数 A がスペース区切りで書かれています。
その後 N行、前走車の位置情報（スタートからの時間 ti とその時点の山頂からの距離 xi）があります。
最後の行には A個の加速度が書かれています。各加速度の場合、最も早く家に着くのはスタートから何秒後か、を求めます。（回答はA個の時間を答えることになります）

データ制限:

• 1 ≤ T ≤ 20 （問題数20問。ただし各問でA個の加速度ごとの時間を求めます）
• 1.0 ≤ D ≤ 10⁴ （家までの距離は最大10,000m）
• Small input の場合：1 ≤ N ≤ 2 （前走車の位置情報は最大で2つ）
  Large input の場合：1 ≤ N ≤ 2,000 （前走車の位置情報最大2,000）
• Small input の場合：1 ≤ A ≤ 10 （加速度最大10パターン）
  Large input の場合：1 ≤ A ≤ 250 （加速度最大250パターン）
• 1.0 ≤ ai ≤ 9.81 （加速度の最大は 9.81m/s²（重力加速度））
• 0.0 ≤ ti ≤ 10⁵ （前走車の位置情報の時間は最大100,000秒）
• 0.0 ≤ xi ≤ 10⁵ （前走車の位置は最大100,000m）
• ti < ti+1 （前走車の位置情報は必ず時間昇順）
• xi < xi+1 （前走車の位置も昇順でバックして戻ったりしない）
• t0 = 0 （最初の前走車の位置情報は時間0秒）
• xN-1 ≥ D （最後の前走車の位置情報は必ず家より遠く）

解き方はいずれ記事にします。
解いたコードはこちらにあります。

GCJ2012 Round 1C Problem A. 問題紹介

Google Code Jam 2012 Round 1C
Problem A. Diamond Inheritance 問題紹介

オブジェクト指向言語の「クラス（class）」の継承関係を図にします（継承関係図みたいな）。

D は B と C を継承しています。B は A を継承しています。C も A を継承しています。
このとき、D と A の関係を見ると、2つの異なる継承経路があります。（D→B→A、D→C→A）

このような2つの異なる継承経路がある状態を Diamond Inheritance と呼び、与えられたクラスの継承関係の中に Diamond Inheritance があるかないかを調べるのが今回の問題です。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行はクラスの数 N です。
その後1行1クラスで Nクラス分のデータが続きます。1行目が クラス1、2行目が クラス2…という具合。
各行は最初に継承しているクラスの数 M があり、その後スペース区切りで M個の継承しているクラスの番号(ID)が書かれています。

データ制限:

• 1 ≤ T ≤ 50 （問題数50問）
• Small input の場合：1 ≤ N ≤ 50 （最大50クラス）
  Large input の場合：1 ≤ N ≤ 1,000 （最大1,000クラス）
• 0 ≤ Mi ≤ 10 （1つのクラスが継承するクラスは最大10クラス）

解き方はいずれ記事にします。
解いたコードはこちらにあります。

GCJ2012 Round 1B Problem C. 解き方

Google Code Jam 2012 Round 1B
Problem C. Equal Sums 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1B Problem B. 解き方

Google Code Jam 2012 Round 1B
Problem B. Tide Goes In, Tide Goes Out 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1B Problem A. 解き方

Google Code Jam 2012 Round 1B
Problem A. Safety in Numbers 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1B Problem C. 問題紹介

Google Code Jam 2012 Round 1B
Problem C. Equal Sums 問題紹介

正の整数がたくさん与えられる中から、合計が同じ値になる異なる組み合せを2つ（1組）見つける問題です。
複数のペアがある場合、どれか1組任意のペアを回答すればOKです。

入力データ:
最初の行は問題数 T。以降 T行の問題データ（1行1問）が続きます。

各行の最初の値は与えられる整数の数 N で、以後 N個の整数がスペース区切りで続きます。

データ制限:

• 1 ≤ T ≤ 10 （問題数は10問）
• Small input の場合：N = 20 （与えられる整数は20個）、各値は 10⁵ 未満
  Large input の場合：N = 500 （与えられる整数は500個）、各値は 10¹² 未満
• 与えられる整数に重複（同じ数字）はない

解き方はこちらです。

GCJ2012 Round 1B Problem B. 問題紹介

Google Code Jam 2012 Round 1B
Problem B. Tide Goes In, Tide Goes Out 問題紹介

地下の洞窟で潮が満ちてきて… みたいなストーリーがありますが、ようするにパズルゲームだと思うのが手っ取り早いです。
kayak ってナニ? と思ったら画像検索するとイメージしやすいかも。Googleさんは kayak がお好きなようです。（Googleマップで海外への経路を検索すると「カヤックで渡る」という選択肢が出てくる…という話題が一頃あったような）

ルールがたくさんあるのが面倒くさい Problem です…

• N×M マス（square）のマップを、左上（北西）から右下（南東）まで移動します。
• square ごとに床と天井の高さが指定されています。
• ある一定の高さまで水が張っていますが、10cm／秒の速さで水位が下がっていきます（潮が干く）。
• 水位が下がりはじめてからゴールに到達するまで何秒かかるか求める問題です。
• 水位が床上 20cm 以上の場合は kayak を使って隣接する square に移動することができます。この場合、移動に 1秒 かかります。床上20cm以上の水位がない場合は、 kayak を押して移動しないといけないので 10秒 かかってしまいます。
  ※移動前の square の床の高さだけで判断できます。移動先での水位は関係ありません。
• 天井と水面（または床）の間が 50cm 以上あいていないと、その square に入ることができません。別の square へ行くか、水位が下がるのを待つ必要があります。
• 今いる square の床と移動先の天井（または今いる square の天井と移動先の床）が 50cm に満たない場合、その経路は移動できません。（別の方角からは入れる可能性があります）
• 床と天井が 50cm 未満の square にはどの方角からも入ることができません。
• 50cmルールが守られていれば高度の移動は無視できます。10cmの床から9000cmの床に移動することもできます。
• 左上端からスタートしますが、水位が下がり始める前でも移動することができます。求めるのは「水位が下がりはじめてからの時間」なので、運良く水位が初期状態のままゴールまでたどり着ければ 0.0秒 が答えになります。（Sampleの #4）
• スタート（左上）からゴール（右下）まで必ず経路があります。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの最初の行は3つの整数 H、N、M です。H は初期状態の水位です。
続く N行は各 square の天井の高さ Cxy です。各行にスペース区切りで M個の値が入っています。
続く N行は各 square の床の高さ Fxy です。天井と同じフォーマットです。
スタート地点（左上）とゴール地点（右下）は必ず天井の高さと床の高さが 50cm以上離れています。また、スタート地点の天井は H（最初の水位）より 50cm以上高くにあります。（スタート地点やゴール地点が50cmルールを守っている、ということです）

データ制限（Small input の場合）:

• 1 ≤ T ≤ 50 （問題数は50問）
• 1 ≤ N,M ≤ 10 （マップは最大で10×10）
• 1 ≤ H ≤ 1000 （水位は最大1000cm）
• 1 ≤ Fxy ≤ Cxy ≤ 1000 （床、天井の高さも最大1000cm）

データ制限（Large input の場合）:

• 1 ≤ T ≤ 50 （問題数は50問）
• 1 ≤ N,M ≤ 100 （マップは最大で100×100）
• 1 ≤ H ≤ 10000 （水位は最大10000cm）
• 1 ≤ Fxy ≤ Cxy ≤ 10000 （床、天井の高さも最大10000cm）

解き方はこちら。

GCJ2012 Round 1B Problem A. 問題紹介

Google Code Jam 2012 Round 1B
Problem A. Safety in Numbers 問題紹介

あるテレビ番組で、N人の出場者が、審判の採点と観客からの投票で得点を決められています。
審判の採点の合計 X を、観客の投票の獲得割合に応じて出場者に振り分けます。（i番目の出場者の）審判からの採点を Ji、観客の投票の Yi パーセントを獲得しているとすると、各出場者の得点は Ji+X×Yi で表すことができます。
Yi は 0〜1(100%)で、全出場者の Yi の合計が100%を超えることはありません。

得点が一番低い人は失格(足切り)になります。
各出場者の審判からの採点（Ji）が与えられるとき、各出場者が失格にならないためには最低何パーセントの票を獲得すればよいかを求める問題です。
※最低得点が2人以上いる場合は誰も失格になりません。

入力データ:
最初の行は問題数 T。以降 T行の問題データが続きます。
1行1問で、最初の数字は出場者の人数 N です。
その後スペース区切りで N人の審判からの採点 si が続きます。（si は上記 Ji のこと）

データ制限:

• Small input の場合：1 ≤ T ≤ 20 （問題数は20問）
  Large input の場合：1 ≤ T ≤ 50 （問題数は50問）
• Small input の場合：2 ≤ N ≤ 10 （出場者は最大10人）
  Large input の場合：2 ≤ N ≤ 200 （出場者最大200人）
• 0 ≤ si ≤ 100 （1人の出場者が審判から得られる得点は最大100点）
• 1つ以上の si は必ず 0 より大きくなります。（少なくとも1人の出場者が1点以上獲得することを意味しています）

解き方はこちらです。

GCJ2012 Round 1C

Google Code Jam 2012 Round 1C も終わりました。
これで今回の Google Code Jam 2012、Round 1 終了です。

今回は参加資格がないので終わってから問題を見てみました。
Problem A. と Problem C. は再帰すると Large で死ぬ系かなと思います。
Problem B. はまた長文で読み切れていないのですが提出傾向的に難易度が高そうです。

Problem A.（Small 14pt、Large 14pt）
Problem B.（Small 10pt、Large 27pt）
Problem C.（Small 12pt、Large 23pt）
1000位入賞は38pt 1時間54分だったので、Problem A. Small&Large + Problem C. Small なら合格ですね。（957位なので割とギリギリですが…）
Problem A. Small&Large はなんとかいけそうですが Problem C.（または Problem B.）をSmallだけでも2時間で解くのは厳しいです＞＜

Round 2（5/26）までに今回の3問も問題紹介と解き方を記事にしたいと思います。できれば…

Problem A. Diamond Inheritance	問題紹介	解き方	ソース
Problem B. Out of Gas	問題紹介	解き方	ソース
Problem C. Box Factory	問題紹介	解き方	ソース

GCJ2012 Round 1B

今朝(昨夜)、Google Code Jam 2012 Round 1B が終わりました。
今回は運良く配点の高い Problem C. をLargeクリアすることができたので、上位1000位に入ってRound 2進出できることになりました(*´ω｀*)

Problem A. はちょっとハマって3回incorrectを出してしまいました（Problem A.のincorrectの解き方がわからなくて気分転換がてらProblem C.を先に解いたのがよかった）。 Problem B. は問題文が長くて理解するまでに時間がかかってしまった感じ… Problem A.で時間を取られたこともあってコンテスト時間内には解くことができませんでした。

配点は
Problem A.（Small 10pt、Large 11pt）
Problem B.（Small 18pt、Large 18pt）
Problem C.（Small 6pt、Large 37pt）
1000位の入賞ラインは1時間19分で27pt（= Problem A. Small&Large + Problem C. Small）。Problem B.だけ（36pt）やProblem C.だけ（43pt）でも1000位に入れたのでちょっとバランスが悪かったかもしれません。

追い追い問題紹介と私の解き方をブログ記事にするつもりですが、先行して今回の問題を解いたソースを GitHub に置きました。今夜 Round 1C に挑戦する方の復習の参考になれば幸いです。（コンテスト後に Problem B. も解けたのでそれも置いてあります）

Problem A. Safety in Numbers	問題紹介	解き方	ソース
Problem B. Tide Goes In, Tide Goes Out	問題紹介	解き方	ソース
Problem C. Equal Sums	問題紹介	解き方	ソース

GCJ2012 Round 1A Problem B. 解き方

Google Code Jam 2012 Round 1A
Problem B. Kingdom Rush 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1A Problem A. 解き方

Google Code Jam 2012 Round 1A
Problem A. Password Problem 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

GCJ2012 Round 1A Problem C. 問題紹介

Google Code Jam 2012 Round 1A
Problem C. Cruise Control 問題紹介

自動車を一定速度で走らせてくれるクルーズコントロールの問題です。

2車線の一方通行の道路を N台の車（各車は長さ5m）がクルーズコントロールを使って一定の速度で走っています。各車、隣に車がいてぶつかる状況でなければ車線変更ができます。
このとき、いずれかの車が前走車にぶつかりそうになってクルーズコントロールを解除するまでの最長時間を求めます。

• 車線変更は一瞬で行われるものとして車線変更にかかる時間は無視できますが、隣同士の車が同時に入れ替わることはできません。
• ぶつからずに全ての車がずっと走り続けられるケースもあります。

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの1行目は車の台数 N。その後N行、各車の最初の場所と速度の情報がスペース区切りで与えられます。

左車線“L” または 右車線“R” を示す Ci、速度(秒速) Si（m/sec）、開始時にいる場所（基点からの距離） Pi（m）。

データ制限:

• 1 ≤ T ≤ 30 （問題数は30問）
• Small input の場合：1 ≤ N ≤ 6 （最大6台の車）
  Large input の場合：1 ≤ N ≤ 50 （最大50台の車）
• Ci = “L” or “R” （左車線“L” または 右車線“R”）
• 1 ≤ Si ≤ 1000 （秒速1m〜1000m）
• 0 ≤ Pi ≤ 10000 （最初の位置、基準から何mか）
• 最初の位置の時点で車が衝突していることはありません。同じ車線にいる車の最初の位置は必ず5m以上離れています。

GCJ2012 Round 1A Problem B. 問題紹介

Google Code Jam 2012 Round 1A
Problem B. Kingdom Rush 問題紹介

Kingdom Rush というタワーディフェンスゲームをモチーフにしたということですが、、、あまりそんな感じはしません。もちろんゲームのことを何も知らなくても問題は解けます。

この問題に出てくる Kingdom Rush では、ステージ（level）をクリアして星（★）を集めていきます。各ステージでは最大2つまで星を獲得できます。

• 1つ星条件（星いくつ持っていること）を達成していれば星を1つ獲得します。
• 2つ星条件（星いくつ持っていること）を達成していれば星を2つ獲得します。
• 既に1つ星を獲得したステージでも2つ星条件を達成していればもう1つ星を獲得できます。（各ステージで2つまで星を獲得できます）

全ての星（ステージ数×2）を集めるのにかかる最短手数（ゲーム数）を求める問題です。

※ステージの星条件によっては解がないケースもあります。

例:

• ステージ1: 1つ星条件=星０個  2つ星条件=星1個
• ステージ2: 1つ星条件=星０個  2つ星条件=星2個

このとき、次の手順で進めると最短手数で全ての星をコンプリートすることができます。

1. ステージ1の1つ星条件（星0個）を達成しているので星1つ獲得
2. ステージ1の2つ星条件（星1個）を達成しているのでもう1つ獲得
3. ステージ2の2つ星条件（星2個）を達成しているので星2つ獲得

入力データ:

最初の行は問題数 T。以降 T問の問題データが続きます。

問題データの1行目はステージ数 N。

その後N行、各ステージの1つ星条件 ai と2つ星条件 bi がスペース区切りで続きます。

データ制限:

• 1 ≤ T ≤ 100 （問題数は100問）
• Small input の場合：1 ≤ N ≤ 10 （最大10ステージ）
  Large input の場合：1 ≤ N ≤ 1000 （最大1000ステージ）
• 0 ≤ ai ≤ bi ≤ 2001 （1つ星条件、2つ星条件）

解き方はこちら。

GCJ2012 Round 1A Problem A. 問題紹介

Google Code Jam 2012 Round 1A
Problem A. Password Problem 問題紹介

長いパスワードを途中まで入力したけれど、ミスタイプしたかもしれない。正しくパスワードを入力完了するまでにあと何回キーをタイプすればよいか、最短の期待値を求める、、という問題です。

パスワードの入力を終えたら [enter] キーを押して判定します。間違っていたら(ミスタイプがあれば)入力したパスワードが全て消えて最初から入力し直しになります。これから入力するパスワードはミスタイプしません。慎重になるんですね（棒

次の3通りのどれかを行います。

• このままパスワードの入力を続ける（入力を終えたら [enter] キーで判定し、間違いがあれば全て消えて再入力）
• [backspace] キーを数回押して入力済みパスワード(の一部)を消して入力し直す（入力を終えて [enter] キーを押したときに間違いがあれば再入力になるのは１つめと同じ）
• 一旦 [enter] キーを押してパスワードをクリアして最初から入力し直す

例:
パスワードは “guest” で、既に2文字入力しているとします。1文字目も2文字目も40%の確率で間違えている可能性があります。このとき、

• ミスせず “gu” と入力できている可能性は 0.6×0.6=0.36（36%）です。
• 最初の “g” は正しく入力できたけれど、2文字目の “u” をミスした可能性は 0.6×0.4=0.24（24%）です。これを “gX” と表現します。
• 2文字目の “u” は正しく入力したけれど1文字目をミスタイプしていた可能性は 0.4×0.6=0.24（24%）です。“Xu”  と表現します。
• 1文字目も2文字目もミスタイプしていた（“XX”）可能性は 0.4×0.4=0.16（16%）です。

正しいパスワードを入力完了するまでにあと何回キー入力が必要かを表にするとこうなります。

	“gu”	“gX”	“Xu”	“XX”	期待値
確率	36%(0.36)	24%(0.24)	24%(0.24)	16%(0.16)	-
このまま入力を続ける	4回	10回	10回	10回	7.84回
[backscape] で1文字消して入力し直す	6回	6回	12回	12回	8.4回
[backscape] で2文字消して入力し直す	8回	8回	8回	8回	8回
[enter] して最初から入力し直す	7回	7回	7回	7回	7回

このまま入力を続ける場合、36%の確率で、あと4回のキー入力（“est”+[enter]）で正しいパスワードを入力完了できます。残りの64%では [enter] してもパスワードが間違っているので最初から入力し直しとなります。“guest”+[enter] の6回余分にキー入力が必要で、全部で10回のキー入力を必要とします。
このとき期待値は、4×0.36 + 10×(0.24+0.24+0.16) = 7.84回 となります。

[backspace] で1文字消して入力し直す場合、“gu” と “gX” はそのまま正しいパスワードを入力することができます。[backspace]+“uest”+[enter] で6回のキー入力です。“Xu” と “XX” の場合はもう一度最初から入力し直す必要があるので、 [backspace]+“uest”+[enter]+“guest”+[enter] の12回のキー入力が必要です。

[backspace] で2文字消して入力し直す場合、どのパターンでも、 [backspace]+[backspace]+“guest”+[enter] の8回のキー入力です。


[enter] して最初から入力し直す場合は [enter]+“guest”+[enter] の7回のキー入力で正しいパスワードを入力完了でき、今回のケースの期待値ではこれが最小となります。

入力データ:

最初の行は問題数 T。以降 T問の問題データが続きます（各2行）。

問題の1行目には入力済みパスワード長 A とパスワード全体の長さ B がスペース区切りで記述されています。
問題の2行目はパスワードを正しく（ミスせず）入力した確率 pi がA個の並んでいます。

データ制限:

• 1 ≤ T ≤ 20 （問題数は20問）
• Small input の場合：1 ≤ A ≤ 3、A < B ≤ 100 （最長100文字のパスワードを1〜3文字入力済み）
  Large input の場合：1 ≤ A ≤ 99999、A < B ≤ 100000 （最長100000文字のパスワードを1〜99999文字入力済み）
• 0 ≤ pi ≤ 1  （正しく入力した確率は 0〜1 の間の全ての値。小数を含む）

解き方はこちら。

GCJ2012 Round 1A

Google Code Jam 2012 Round 1A が終わりました。（もう2日も前ですが…）
今回は 合同勉強会in大都会岡山 -2012 Spring- に日程がかぶっていたので最初から諦めていたのですが、一応挑戦だけはしていました。Problem A.の Small だけという残念な結果でしたが…(´･ω･`)

比較的簡単な Problem A.（Small 10pt、Large 10pt）、Problem B.（Small 15pt、Large 18pt）と、難易度の高い Problem C.（Small 17pt、Large 30pt）の3問が出題されました。

結果を見ると制限時間2時間半の中で、2:15以内で Problem A. と Problem B. の Small&Large をクリアしていれば上位1000位に入れたようです（53pt）。
集中して取り組んでいたとして、ギリギリいけたかどうかってところかなぁ…

コンテスト後に練習モードで Problem A. と Problem B. の Small&Large は解けたので、また追い追い問題紹介と解き方を書いていきます。

Problem A. Password Problem	問題紹介	解き方	ソース
Problem B. Kingdom Rush	問題紹介	解き方	ソース
Problem C. Cruise Control	問題紹介	未稿	N/A

GCJ2012 Qualification Round Problem C. 解き方

Google Code Jam 2012 Qualification Round
Problem C. Recycled Numbers 解き方

コンテストで提出したコードは ここ からダウンロードできます（Python）。
あと このへん。移動してたら探してください。
問題紹介はこちら。

以下ネタバレ

GCJ2012 Qualification Round Problem B. 解き方

Google Code Jam 2012 Qualification Round
Problem B. Dancing With the Googlers 解き方

コンテストで提出したコードは ここ からダウンロードできます（Python）。
あと このへん。移動してたら探してください。
問題紹介はこちら。

以下ネタバレ

GCJ2012 Qualification Round Problem A. 解き方

Google Code Jam 2012 Qualification Round
Problem A. Speaking in Tongues 解き方

コンテストで提出したコードは ここ からダウンロードできます（Python）。
あと このへん。移動してたら探してください。
問題紹介はこちら。

以下ネタバレ

GCJ2012 Qualification Round Problem D. 問題紹介

Google Code Jam 2012 Qualification Round
Problem D. Hall of Mirrors 問題紹介

鏡の部屋にいて、反射して映った自分をどれだけ見つけられるか…という問題です。
今回の Qualification Round の中で一番難しい問題でした。（解けませんでしたorz）

部屋は正方形のグリッド(マス)で構成されています。
各マスは四方が鏡になっているか、何もないか、中央に自分がいます。
計算上自分はとても小さくて、反射の邪魔になったり体の一部だけが反射したりしないことになっています。（数学的なお約束ですね）
部屋はもやもやしていて、D マス以内しか視界がありません。

例：

######     # 四方が鏡の壁
#..X.#     . 何もない空間
#.#..#     X 自分がいる場所
#...##
######  D=3

このとき、図の真上の方向を見ると、鏡に映った自分を見ることができます。壁（鏡）まで0.5マス、反射して自分がいるところまで0.5マスで合計1マスの距離なので、視界（D=3）の範囲内です。

同様に図の右（真横）の方向を見た場合も、壁まで1.5マス、反射して1.5マスの計3マスの距離で自分の反射を見ることができます。

下方向や左方向は反射した自分までの距離が5マスとなるので見ることができません。

光は直進し、鏡に当たると入射角と同じ角度で反射します。ごく普通の鏡と同じ光の反射をします。

壁（鏡）の角をかすめる場合、自分はとても小さいので、スルッとすり抜けることができます。

角にぶつかるとそこで光が止まってしまいます。

元々自分がいた場所（のマスの中央）に光が戻ってきたら「反射した自分を見る」ことができます。

ぐるっと見回して反射した自分をいくつ見つけられるか求める問題です。

入力データ:

最初の行は問題数 T。以降 T問のデータが続きます。

問題データの1行目はスペースで区切られた3つの整数で、部屋の幅 W、部屋の高さ H、視界 D。次に H行の部屋データが続きます。

部屋データは次の通りです。

'#' 四方が鏡の壁

'.' 何もない空間

'X' 自分がいる場所

データ制限:

• 3 ≤ H, W ≤ 30
• 1 ≤ D ≤ 50
• 部屋データには 'X' が必ず1つ含まれる
• 部屋データの1行目、最後の行、各行の最初と最後は '#' となる（部屋は鏡で囲まれている）
• Small input の場合: 部屋の内側には壁（鏡）がない（部屋の周囲を囲む壁のみ）

GCJ2012 Qualification Round Problem C. 問題紹介

Google Code Jam 2012 Qualification Round
Problem C. Recycled Numbers 問題紹介

異なる正の整数のペア (n, m) を考えます。
m が、n の後ろの数桁を順序を入れ替えずに先頭に持ってきたものであるとき、このペアを リサイクルされたペア と呼びます。
例えば 12345 の後半 345 を先頭に移動した (12345, 34512) は リサイクルされたペア です。

n と m は同じ桁数です。どちらも 0 で始まることはありません。

2つの同じ桁数の整数 A B が与えられたとき、リサイクルされたペア (n, m) が何種類あるかを求めます。（A ≤ n < m ≤ B）

入力データ:

最初の行は問題数 T。以降1行1問のデータが T行続きます。

問題の各行はスペース区切りの2つの整数値 A と B です。

データ制限:

• 1 ≤ T ≤ 50 （問題数は50問）
• Small input の場合: 1 ≤ A ≤ B ≤ 1000
  Large input の場合: 1 ≤ A ≤ B ≤ 2000000
• A と B は同じ桁数

解き方はこちら。

GCJ2012 Qualification Round Problem B. 問題紹介

Google Code Jam 2012 Qualification Round
Problem B. Dancing With the Googlers 問題紹介

Googler（Google社員）のダンスを見ていて、3人の審判がスコアを付ける…というストーリー。
問題には Googler とかダンスとか関係ありませんw

スコアは 0点〜10点 で、3人の審判が付けるスコアは通常1点差以内に収まります。
(3, 3, 3) や (7, 8, 7) のような形です。
ときどき意外な結果(surprising)になることがあって、2点差のスコアが付けられる場合があります。
(6, 7, 8) や (4, 4, 6) のような形です。
3点差以上のスコアが付けられることはありません。

ダンスした Googler 1人1人について

合計スコア … 3人の審判が付けたスコアの合計

最高スコア … 3人の審判が付けたスコアのうちの最高点

を考えます。

問題では

• 各Googlerの合計スコア
• 意外な結果(surprising)の出た回数
• 目標最高スコア

が与えられるので、目標最高スコアを達成したGooglerが最大何人いるかを求めます。

例:

• 6人の Googler がダンスをして、各々の合計スコアは 29, 20, 8, 18, 18, 21
• 意外な結果(surprising)は 2回
• 目標最高スコア 8点

この場合、6人のスコアの内訳は例えば次のようになっていたと考えられます。

• 29 = (9, 10, 10)
• 20 = (6, 6, 8) ← 意外な結果(surprising)
• 8 = (2, 3, 3)
• 18 = (6, 6, 6)
• 18 = (6, 6, 6)
• 21 = (6, 7, 8) ← 意外な結果(surprising)

最高スコアで 8点以上を取っている Googler は3人なので、この答えは 3 です。

入力データ:

最初の行は問題数 T。以降1行1問のデータが T行続きます。

各行はスペース区切りで複数の整数値を持っています。

最初の値はダンスしたGooglerの人数 N。

次の値は意外な結果(surprising)の出た回数 S。

3つめの値は目標最高スコア p。

その後N個の値がN人のGooglerの合計スコア ti です。

データ制限:

• 1 ≤ T ≤ 100 （問題数は100問、と考えればよいでしょう）
• Small input の場合：1 ≤ N ≤ 3 （ダンスしたGooglerは最大3人）
  Large input の場合：1 ≤ N ≤ 100 （ダンスしたGooglerは最大100人）
• 0 ≤ S ≤ N （意外な結果(surprising)は0回〜最大で全部）
• 0 ≤ p ≤ 10 （目標最高スコアは0点〜10点）
• 0 ≤ ti ≤ 30 （各合計スコアは0点〜30点）
• 少なくともS個の合計スコアは 2点〜28点 の間

解き方はこちら。

GCJ2012 Qualification Round Problem A. 問題紹介

Google Code Jam 2012 Qualification Round
Problem A. Speaking in Tongues 問題紹介

通常CodeJamでは問題ごとに Small input と Large input の2つの入力データがありますが、この問題は Small input しかない特別編成になっています。

“Googlerese” という言語の翻訳(変換)をする、という課題です。

Googlerese には次のルールがあります。

• 各英文字（アルファベット）を別の文字で置き換える。
• 変換マップは1対1になっている。同じ文字は常に一定の文字に変換されるし、違う文字が同じ文字に変換されることはない。
• 変換されない（同じ文字に置き換えられる）場合もある。スペースはスペースのままになる。
• 変換マップは常に一定で入力データごとに変わったりしない。

Sample で Googlerese と英文の対応が示されているので、これを元に変換マップを構築します。（全ての対応が示されているわけではありませんが、不足分を補うのは簡単でしょう、、みたいなヒントが書かれているのに気付かず2〜3回 incorrect を出しちゃいましたorz）

解き方はこちら。

Google Code Jam 2012

本大会は年一度開催されていて、その2012年版です。
（この他に特定の国や地域を対象にした特別版が年数回開催されることがあるようです）

• 登録受付(Registration) 3月13日〜4月15日
• Qualification Round 4月14日(土) 8:00〜 25時間
• Round 1-A 4月28日(土) 10:00〜 2時間半
• Round 1-B 5月6日(日) 1:00〜 2時間半
• Round 1-C 5月6日(日) 18:00〜 2時間半
• Round 2 5月26日(土) 23:00〜 2時間半
• Round 3 6月9日(土) 23:00〜 2時間半
• Final Round (於ニューヨーク) 7月27日(現地時間)

Qualification Round の日は岡山でお花見。

Round 1-A の日は岡山で勉強会と、スケジュールがことごとく岡山の予定とかぶってる…orz

ちゃんとCodeJamの予定を見ておいてスケジュールを立てましょう、という教訓を得ました(｡･ω･｡)

Qualification Round は25時間ありますが、世界中どの地域からでも参加しやすいように、、という配慮だと思います。今回は4問出題されていて、事前に「20pt獲得すればクリア」ということがわかっていたのでハードルは低めです。

Round 1 は時間の異なる Sub-Round が3回あります。これも時差への配慮と思われます。

3回の Sub-Round のうちどれか1つで上位1000位に入ると Round 2 へ進むことができます。

Round 2 は（Round 1 を勝ち抜けた）3000人で競うことになります。上位500位に入ると Round 3 へ進むことができます。

Round 3 で上位25位に入ると Onsite Final Round へ進出となります。

Onsite Final Round はニューヨークで行われ、旅費はGoogleさんが出してくれるそうです。

Round 2 の500位は難しそうだけど、なんとか Round 1 は突破したい（3000人に入りたい）なぁ…と思ってマス。

CodeJamってナニ？

CodeJam… 正確には Google Code Jam は、Googleが主催しているプログラミングコンテストです。

• Web上で問題が出題され、それを解くプログラムを作ります。言語は何でもかまいません。*1
• 問題に対して2種類の入力データがあります。データの範囲が小さくて難易度が低めのSmallと、データ範囲が大きくて難しいLargeです。
• 入力データをダウンロードして、自分で作ったプログラムにかけて結果（回答）を出力します。その結果をサーバにアップロードすることで、サーバで正誤判定が行われます。

これがCodeJamの基本ルールです。

Practice and Learn のページ に過去問が練習モードで掲載されているので、お好みの問題を楽しむことができます(((o(*ﾟ▽ﾟ*)o)))

本戦にはコンテスト期間が決まっていて、練習モードでは割愛されているルールがあります。

• 世界中で同時にコンテストが始まります。UTCで表示された日時は日本時間にすると +9:00 なのでスケジュール調整に注意しましょう…
• 問題ごとにスコアが決まっており、正しい回答を提出するとそのスコアを獲得します。コンテスト期間中に獲得したスコアが多い順にランキングされます。同じスコアの場合は最後に正しい回答を提出した時間が早い順となります。（後述のペナルティを加算した時間で判定されます）
• Small input は、入力データをダウンロードしてから4分以内に回答を提出する必要があります。回答を提出するとすぐに正誤判定され、間違えたら何度でも（正解するまで）再提出することができます。4分の制限時間に間に合わなかったり、間違った回答を提出すると、1回につき4分のペナルティが課されます。（正しい回答を提出した時時に 4分×間違えた回数 を加算して順位判定される）*2
• Small input を正解するまで Large input には挑戦できません。
• Large input は同様に8分の制限時間があります。制限時間内であれば何度でも再提出することができます。こちらはコンテストが終了するまで正誤判定は「おあずけ」で、コンテスト終了と同時に採点されて最終順位が確定します。（回答を提出した時点で暫定スコアが入りますが、正解していない場合はその分が無くなるので順位が下がります）
• 回答提出時に、その出力を得るのに使ったプログラムのソースコードを提出する必要があります。コンテスト終了後、正しい回答と一緒に提出されたソースコードは公開されます。正しいソースコードが提出されていない場合、失格になる（その問題で獲得したスコアを失う）ことがあります。
• 優秀賞（ランキング上位）の特典はコンテストによって異なります。（本戦Final Round 1位で $10,000 USD とか、Round 2 上位1000位以内で Google Tシャツとか）

コンテストごとに細かいルールが異なる場合がありますが、Google Code Jam Japan 2011のルール が日本語で詳細に書かれているので参考にしてください。

*1:言語は何でもOKですが、コンパイラやインタプリタを無償で入手できる必要があります。Visual Studio Express があるので Visual Studio でもOKらしいです。

*2:間違った回答を提出したり時間切れになったSmall問題をコンテスト期間中に最後まで答えられなかった場合、その問題についてはペナルティは課されません。

なんとなく

CodeJamの問題紹介と自分なりの解き方メモを飽きるまで書いてみようかなと。
ときどきCodeJamの紹介や問題の解説をしたりするけど、ブログにまとめておけばいいんでない？的な。（Googleサイトでもよいけれど新しいコンテストの話題も書いていきたいので）

ソースはGitHubにでも置いておきます。コンテストが終わったあとでも書き直すことあるし。当然ながらコンテスト中はソース公開しません。
コンテスト終了後は他の人のSolutionもダウンロードできるので、解き方解説やソースの公開は問題ないと思っています。
「自分で解くんだ。お前の解説なんか見たくない」て方はどうぞお引き取りくださいm(_ _)m

問題紹介 … どういう問題か、の紹介。ただの翻訳ではなく補足を入れる、、つもり(^^ゞ 少しでも CodeJam に興味を持ってくれる人が増えるといいなって。

解き方 … 自分がどう解いたか、の解説。ネタバレ編。自力で解いてからにしたい、という場合もあると思うので問題紹介とは記事を分けます。