人気ブログランキング |

体重と今日食べたもの

k1segawa.exblog.jp

ダイエット

ブログトップ

数学ゲーム Google Code Jam (10/13)

code jam 練習問題
リンク先

この問題はGoogle Code Jam Japan 2011によるもので、
クリエイティブ・コモンズ表示ライセンスに従う。

Small条件とLarge条件のどちらかを選んで回答する。
===============================================
問題
みんな大好きジェットコースター! この遊園地に来た人はみんなこれがお目当てさ。 1 人で来る人もいるし、グループで来る人もいる。グループで来たからにはやっぱりみんなで一緒じゃないと乗りたくないよね。楽しい楽しいジェットコースター! このジェットコースター、乗った人はみんなもう一度乗りたがるんだ。
乗車料は一回一人当たり 1 ユーロ。このジェットコースターの今日の売上を予測するのが君のお仕事さ!

このジェットコースターは同時に k 人乗ることができて、グループが列を作って待っています。グループは順番にジェットコースターに乗り込み、全部のグループが乗ったか、次に待っているグループ全員が乗れるだけの席が無くなった時点で、空席が残っていたとしても出発します。ジェットコースターを降りた後、グループは乗り込んだ順番と同じ順番で列の後ろに並びします。ジェットコースターは 1 日に R 回発車します。

例えば R=4, k=6 の場合に、1 人, 4 人, 2 人, 1 人の 4 つのグループがこの順番に並んでいたとしましょう。 1 回目の出発は 1 人, 4 人の 2 つのグループが乗り込んで、残りひとつの席は空けたまま出発します(次の 2 人のグループは座りきれず、 最後の 1 人のグループは前のグループを抜かすことはできません)。
1 回目が終わった後、彼らは列の後ろに並びなおし、列は 2 人, 1 人, 1 人, 4 人となります。 2 回目は 2 人, 1 人, 1 人の計 4 人が乗り、終わった後の列は 4 人, 2 人, 1 人, 1 人となります。 3 回目は 4 人, 2 人 の計 6 人が乗り、終わった後の列は 1 人, 1 人, 4 人, 2 人となり、最後に 1 人, 1 人, 4 人の計 6 人が乗るので、合計 21 ユーロの売上になります。

入力
1 行目にはテストケースの数 T が含まれており、次の行から T 個のテストケースが後に続きます。各テストケースは 2 行からなり、始めの行にはスペースで区切られた 3 つの整数 R, k, Nが含まれています。次の行には N 個のスペースで区切られた整数 gi が含まれています。 gi は列に並んでいる各グループの人数を表しており、 g0 は 1 番目のグループの人数、g1 は 2 番目のグループの人数、... となっています。

出力
各テストケースにつき 1 行、 "Case #X: Y" と出力してください。ただし、X は 1 から始まるテストケースの番号、Y はジェットコースターのその日の売上です。

制約
1 ≤ T ≤ 50
gi ≤ k

Small
1 ≤ R ≤ 1000
1 ≤ k ≤ 100
1 ≤ N ≤ 10
1 ≤ gi ≤ 10

Large
1 ≤ R ≤ 108
1 ≤ k ≤ 109
1 ≤ N ≤ 1000
1 ≤ gi ≤ 107

サンプル

入力
3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3

出力
Case #1: 21
Case #2: 100
Case #3: 20
===============================================
回答できそうな問題Cを選んでみた。コードの練習にいいかも。

面白いなと思ったのは、入力フォーマット。
可変長でプログラムで読み込みやすいフォーマットだと思う。
MAC>IP>TCPのパケットのヘッダに通じる感じ?
後ろが読み込めるとは限らない通信データと同じで、
わからないIDやらへんちくりんな用語がないシンプルなもの。
業界標準仕様を決めるどこかの会社には参考にしてもらいたい。

*(追記)
なんで読み込みやすいのか、考えてみた。
ぱっとみでは、いったいどういうフォーマットなのかわからないけど、
説明を読めば簡単にわかる。(上記の入力データ)
逆に、ぱっと見てわかりやすい業界のよくあるフォーマット。(たとえば放送関係)
あれは2次元的に情報がまとまっていて、Excelとかで出来ていそう。
人間の目はパターン認識が出来るから、どこに必要なデータがあるかすぐわかる。
でもコンピュータでExcelの表を読み込もうとすると、とたんに関係ない表のタイトルや、
2行にわたっているセルや、一つ飛ばしのデータセル(空白セルをはさむ-人間には見やすいけどこれがルール無用なんだ)とか、どうやってもOA化の妨げにしかならない。
一旦データ移行工程をかまさないと、システム化は無理な電子データ。
これでデータ管理してるって言う「情報システム」管理者がいたらちゃんちゃらおかしい。
キーワード:2次元
シンプルと言ったが、コンピュータが読み込みやすいのは、1次元で、
人間から見ればかえってわかりにくいひと手間かかるフォーマットがいいのだ。
*(追記終わり)

Google Code Jamも面白いよ。

(もちろん適材適所、ケースバイケースであり、人間視点かシステム中心か、コンピュータリソースなどの局所的な問題であって、ユーザは最も適切なフォーマットで接するべきである。ただプログラマーやシステム設計者がこんなことを言ってると笑われる。データベースもリクエストを返すサーバが居るからあれでいいのであって、あくまでもデータのやり取りをシリアルにするので、データの持ち方は自由)
by k1segawa | 2011-10-13 18:04 | Comments(0)