Maximum-Cup 2010

埼玉大学主催のプログラミングコンテストMaximum-Cupに参加して来ました．

Maximum-Cup 2010

問題はM-Judgeから閲覧できます．

■Problem A さいたまトラップ
幾つかのトラップがある．Sくんはトラップを除去する事にしたが，除去には決められた時間がかかる．更に，除去作業を1時間行うごとに10分間の休憩が必要である．Sくんは24時間未満に全てのトラップを除去出来るか．出来る場合は除去終了までの時間を求めよ．

サクサクッと実装したのですがWA．
ずいぶん後になって，1時間丁度で終わる場合の休憩時間の処理を間違えていたことに気付きました…．

01:39 AC

■Problem D 北海道のレストラン
幾つかのレストランに社員がいる．勤続年数100年のオーナーは接客研修会を開くため，ある1つのレストランをその会場とし，社員全員をそこに集めたい．
社員一人一人の移動コストは(勤務先のレストランと会場のレストランとの距離)x(勤続年数)で定義される．
移動コストの総和が最も小さくなるのはどのレストランか．

距離はFloyd-Warshallで求められますし，どのレストランを選ぶかも全探索で可能そうでしたのでサクサクッと組みましたがWA．
□トラップその1…オーナーも含む
オーナーは店番号1である，勤続年数100年の社員として計算の考慮に入ればければなりませんでした．
□トラップその2…レストランiとレストランjの距離は複数与えられる
これはコンテスト終了まで気付きませんでした．

■Problem G Arithmetic Geometric Sequence
http://m-judge.maximum.vc/problem.cgi?pid=10174参照．

最初は無理ゲーだと思ったのですが，数列Qにおいて，ある数k以下となる項の個数n(k)は容易に求められることが分かりました．
具体的には，
n(k)=[k/1]+[k/m]+[k/m²]+[k/m³]+[k/m⁴]+…
ですので，m=0,1の時だけ注意して，n(k)=xとなるkを二分探索で求めれば完了です．

03:22 AC

結局解けたのは，AとGだけという散々な結果でした．
まだまだ詰めが甘く，実装力が高いとは言えない，ということを思い知らされたコンテストでした．