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クラス)

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