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 に興味を持ってくれる人が増えるといいなって。

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