こんにちは。rogy競プロ部の森田(@yosupot)です。
たまにはブログを書きます。今回はGoogle Code Jam(以下GCJ)という大会についてです。
これは、名前の通りGoogleが主催しているプログラミングコンテストです。競技プログラミングの大会の中では、ICPCと並び、最大の規模を誇るんじゃないかと思います。
システムとしては、何回かに分けて予選があり、人が 沢山(今年は27169人)->3000->500->25と減っていきます。これは全部オンラインの大会で、最後の25人に残ればニューヨークのgoogleオフィスにいって決勝をします。
そして僕は、最後の25人に残った(https://code.google.com/codejam/contest/3224486/scoreboard 7位,日本人最高位)ので、無事ニューヨークに行きます。やり遂げたぜ。
…というだけでは面白みにかけるので、今回は今年のGCJに出題された問題のうち、高度なアルゴリズムを必要としない問題を2題紹介します。興味を持ったらぜひ来年参加してみてください(といっても丸一年後だけど…)
Round2 A問題 Rather Perplexing Showdown
https://code.google.com/codejam/contest/10224486/dashboard#s=p0
あなたは、グー、チョキ、パーの書かれた紙をA, B, C枚持っています。A+B+Cは2の累乗、つまり1,2,4,8,16,...のうちどれかになっています。ただし、最大でも1024枚です。
あなたは、この紙たちからトーナメントを作りたいです。(A+B+Cが2の累乗なので、シードとかは当然無いです。)。紙たちはじゃんけんをして、勝利したほうが勝ち抜きます。そして、トーナメントのどの試合でも、引き分けが起きてはいけません。
このようなトーナメント表を作れますか？POSSIBLEかIMPOSSIBLEで答えてください。(元問題だと、POSSIBLEだったらグー=R, パー=P, チョキ=Sとしてトーナメント表を左から見た時の辞書順最小の文字列を求めないといけないですが、これはもうすこし難しいです。)
Round3(=最終予選) A問題 Teaching Assistant
https://code.google.com/codejam/contest/3224486/dashboard
あなたは、空のスタックと、'A', 'B'からなる長さNの文字列を持っています。スタックの容量は無限です。文字列の長さ、つまりNは100000以下で、しかも偶数です。
そして、文字列の先頭から順番に文字を見ていって、1文字見るごとに次のうちどちらかの操作ができます。
- その文字をスタックに積む。
- スタックから文字を1個取りだす。そしてこの時、取り出した文字と今見てる文字が同じなら5円、違うなら10円貰える。
文字列を最後まで見た時の、もらえるお金の合計を最大化してください。
例えば文字列がAABBなら、push-pop-push-popとすれば20円貰えます。
文字列がABBAなら、push-push-pop-popで20円貰えます。
でも、ABABなら10円しか貰えません。
ほかにも、ABBBとかだったら15円貰えます。
たまにはブログを書きます。今回はGoogle Code Jam(以下GCJ)という大会についてです。
これは、名前の通りGoogleが主催しているプログラミングコンテストです。競技プログラミングの大会の中では、ICPCと並び、最大の規模を誇るんじゃないかと思います。
システムとしては、何回かに分けて予選があり、人が 沢山(今年は27169人)->3000->500->25と減っていきます。これは全部オンラインの大会で、最後の25人に残ればニューヨークのgoogleオフィスにいって決勝をします。
そして僕は、最後の25人に残った(https://code.google.com/codejam/contest/3224486/scoreboard 7位,日本人最高位)ので、無事ニューヨークに行きます。やり遂げたぜ。
…というだけでは面白みにかけるので、今回は今年のGCJに出題された問題のうち、高度なアルゴリズムを必要としない問題を2題紹介します。興味を持ったらぜひ来年参加してみてください(といっても丸一年後だけど…)
Round2 A問題 Rather Perplexing Showdown
https://code.google.com/codejam/contest/10224486/dashboard#s=p0
あなたは、グー、チョキ、パーの書かれた紙をA, B, C枚持っています。A+B+Cは2の累乗、つまり1,2,4,8,16,...のうちどれかになっています。ただし、最大でも1024枚です。
あなたは、この紙たちからトーナメントを作りたいです。(A+B+Cが2の累乗なので、シードとかは当然無いです。)。紙たちはじゃんけんをして、勝利したほうが勝ち抜きます。そして、トーナメントのどの試合でも、引き分けが起きてはいけません。
このようなトーナメント表を作れますか？POSSIBLEかIMPOSSIBLEで答えてください。(元問題だと、POSSIBLEだったらグー=R, パー=P, チョキ=Sとしてトーナメント表を左から見た時の辞書順最小の文字列を求めないといけないですが、これはもうすこし難しいです。)
Round3(=最終予選) A問題 Teaching Assistant
https://code.google.com/codejam/contest/3224486/dashboard
あなたは、空のスタックと、'A', 'B'からなる長さNの文字列を持っています。スタックの容量は無限です。文字列の長さ、つまりNは100000以下で、しかも偶数です。
そして、文字列の先頭から順番に文字を見ていって、1文字見るごとに次のうちどちらかの操作ができます。
- その文字をスタックに積む。
- スタックから文字を1個取りだす。そしてこの時、取り出した文字と今見てる文字が同じなら5円、違うなら10円貰える。
文字列を最後まで見た時の、もらえるお金の合計を最大化してください。
例えば文字列がAABBなら、push-pop-push-popとすれば20円貰えます。
文字列がABBAなら、push-push-pop-popで20円貰えます。
でも、ABABなら10円しか貰えません。
ほかにも、ABBBとかだったら15円貰えます。
