hotpepsiの練習帳

Code Jam Sprint

00:06

A. Android Figurines

問題

• M種類のアンドロイドのミニフィギュアが発売になった。
• それぞれの種類を少なくともK1, K2, ... KM個入手する衝動に駆られた。
• 店にはそれぞれの種類の在庫がL個ずつある。
• 望みの数だけ入手するために最悪何個買う必要があるか求める。

方針

• 最悪ケースでは、同じのばっかり掴むことになる
• ということは、(M-1)種類までは全部買うことになる
• 最後の種類は、M種類のうち最大の個数だけ
• Lより多いものがあれば不可能(-1)
• 全種類とも必要数が0なら0
• https://github.com/firewood/topcoder/blob/master/gcj_2012/CJS_A_AndroidFigurines.cpp

B. Repeated Numbers

問題

• 鴨にゼッケンをつける。
• 書き留める数字の数を節約するために、K桁の数を1ずつオーバーラップして
• 記録することにした。
• 重複している数を昇順に求める。

方針

• 1ずつずらしながらstd::set<int>に突っ込む
• 重複していれば記録しておく
• 最後に昇順に連結
• Nが小さいので特に問題なし
• https://github.com/firewood/topcoder/blob/master/gcj_2012/CJS_B_RepeatedNumbers.cpp

結果

Aのジャッジ解が間違っていて紛糾。それはさておき、普通に3回間違えたので反省しなければならない。4回目には正解を送ったがWAとなった。見直しても合ってそうだったのでもう一度送ったら通った。どうも60分経過時点くらいにジャッジ解を修正したようである。(送信履歴を確認した)

Bは普通に解けた。

一応79位だったのだけど、ジャッジ解が合っていたらたぶん100位に入れなかったので、これはラッキーというしかない。狙った運営ならすごすぎる。

両方ともSRMだとdiv1easyに出てきそうな問題。Aが出てたら死んでたと思う。コーナーケースの注意力が足りない。

ということでGoogle I/Oのチケット買えたのでアメリカ行ってきます。