Top > GoogleCodeJam

GoogleCodeJam

Google主催のコンテスト 大会ページGCJ

GCJ2015

スケジュール
April 10, 2015 Qualification Round
April 18, 2015 Online Round 1: Sub-Round A
May 2, 2015 Online Round 1: Sub-Round B
May 10, 2015 Online Round 1: Sub-Round C
May 30, 2015 Online Round 2
June 13, 2015 Online Round 3
June 14, 2015 Distributed Code Jam Online Round~ August 14, 2015 Onsite Finals
August 15, 2015 Distributed Code Jam Onsite Finals

Qualification Round

足切りラウンドとか言われている。
4問あって、100点中20点以上取れば全員次のRound1に進めた。

問題に関して


問題A:Standing Ovation
small7pt,large10pt
友人が大きな会場で歌うが、スタンディングオベーションさせるためには何人のサクラが必要かというような問題。
特にひねりなどはないと思われる。


問題B:Infinite House of Pancakes
small9pt,large12pt
Aだけだと17ptなので、通過にはsmallだけでも通しておく必要がある。
英語が難しかったせいか、嵌ったという人がいたので解説を書いておく。
どういう問題かというと
有限のパンケーキと無限の「食事をする人」(diners)があって、D人の皿には既にP(i)個のパンケーキが入っている。
朝食が始まると、皿にパンケーキが乗っている人は全員一斉に食べ始め、
◆全員がそれぞれ一分間に一枚ずつ食べていく。 (皿にパンケーキが10枚乗っている人は10分で完食する。)
◆店員はスペシャルタイムを宣言することができ、この一分間は誰もパンケーキを食べず、店員は誰か一人の皿から他の一人の皿に一部を分けて移せる。

店員はできるだけ早く全てのパンケーキを処理したい。
最短では何分で全ての皿を空にできるかを計算する。

解法
朝食が始まってすぐにまとめてスペシャルタイム(分割)を実行したほうが速くなるのは明らか。
ある皿にパンケーキが例えば10個乗っていた場合、分割を一回するときは5+5の二皿にすると6分で食べ終わるので、二等分これが最適。
やっぱり後からもう一回分割をしようとなった時、分割を二回するわけだが、最初から3+7にしておいた後に3+3+4にすると最適。(4枚+2回分割で6分かかる)
二回分割するなら最初から三等分にしようと思って分割するのが最適になる。

10枚の場合、分割回数毎に分割後の最大枚数、パンケーキの処理にかかる時間は
0回  1回 2回 3回 4回 5回
10枚 5枚 4枚 3枚 3枚 2枚
10分 6分 6分 6分 7分 7分
というふうになります。

要するに何をしたかというと
まず、全てのパンケーキが乗ってる皿に対して2枚になるまでn等分(切り上げ)して、その結果をArrayList(vector)などに突っ込みます。
これを大きいものから順番になるようにソートします。
ソートした結果に前から順番に0,1,2…を足していきます。
すると全ての分割回数での最短時間が求まっているので、これを小さいものから順番になるようにソートすると、一番前が最適な分割回数での最短時間になってます。


問題C:Dijkstra
small11pt,large17pt


問題D:Ominous Omino
small8pt,large26pt

Online Round 1: Sub-Round A