2012年5月27日日曜日

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

2012年5月17日木曜日

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 解き方

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

以下ネタバレ

2012年5月16日水曜日

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つの整数 NM が書かれています。
続く行には 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 ≤ NM ≤ 100
  • 1 ≤ aibi ≤ 1016 (一度に流れてくる箱・おもちゃは最大1016個(超たくさん))
  • 1 ≤ AiBi ≤ 100 (箱もおもちゃも最大100種類(順番とは限らない))

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

2012年5月12日土曜日

GCJ2012 Round 1C Problem B. 問題紹介

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

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

スタート時、自車は山頂 0m地点にいて静止しています(0m/s)。その後等加速度(a m/s2)で動いていきます。初速度を v0 とした場合、t 秒後の位置
v0 * t + 0.5 * a * t2
で求められる、、というヒントがあります。

前走車はスタートから 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 104 (家までの距離は最大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/s2(重力加速度))
  • 0.0 ≤ ti ≤ 105 (前走車の位置情報の時間は最大100,000秒)
  • 0.0 ≤ xi ≤ 105 (前走車の位置は最大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)」の継承関係を図にします(継承関係図みたいな)。
DBC を継承しています。BA を継承しています。CA を継承しています。
このとき、DA の関係を見ると、2つの異なる継承経路があります。(DBADCA

このような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クラス)

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

2012年5月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 解き方

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

以下ネタバレ

2012年5月9日水曜日

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個)、各値は 105 未
    Large input の場合:N = 500 (与えられる整数は500個)、各値は 1012 未満
  • 与えられる整数に重複(同じ数字)はない

解き方はこちらです。

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つの整数 HNM です。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)

解き方はこちら

2012年5月7日月曜日

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問題紹介解き方ソース

2012年5月6日日曜日

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. も解けたのでそれも置いてあります)

2012年5月2日水曜日

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つ星条件=星0個  2つ星条件=星1個
    • ステージ2: 1つ星条件=星0個  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] キーを押したときに間違いがあれば再入力になるのは1つめと同じ)
    • 一旦 [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%)です。

    正しいパスワードを入力完了するまでにあと何回キー入力が必要かを表にするとこうなります。
    gugXXuXX期待値
    確率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 の間の全ての値。小数を含む)

    解き方はこちら

    2012年5月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)。
    あと このへん。移動してたら探してください。
    問題紹介はこちら

    以下ネタバレ