Hatena::Grouptopcoder

hotpepsiの練習帳

2011-11-19

SRM 524 Div2

20:47

Easy (250) ShippingCubes

問題

  • N個の立方体をa x b x cの形で隙間なく詰めたい。
  • a+b+cの最小値を求める。

方針

Medium (500) MagicDiamonds

問題

  • 距離nだけ移動したい
  • 素数の移動は不可

方針

Hard (1000) MultiplesWithLimit

問題

  • 0から9のうち、0から9個だけ禁止されている
  • 禁止文字を使わずに、与えられたnの倍数の最小値を求める

方針

  • 本番で解けず、解きなおし
  • 下の桁からBFS
  • 1度処理した余りは、2度目は無視してよい
  • ただし、見つかったものが最小値か不明なので、解が見つかったら、キューへの追加をやめて、残りのキュー(同じ桁数のキュー)を全て処理する。
  • ためしにpriority_queueを使ってみたが遅くて断念
  • https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_524/MultiplesWithLimit.cpp

結果

oo- 224.71+439.48-25.0=639.19 rating 1179 -> 1190

easyは途中で方針を変えた割にはそこそこの時間で書けた。

これは郵便物の送料を最小化する問題ということだろうか。球に近づければ良いのだと思われる。

mediumは前回範囲の判定が甘かったので、今回は1~5くらいまで個別に代入してじっくり見た。

除算での判定もそれなりに速いのはSRM 508のときに調べていたので同じように書いた。一応、submitしてから最大値より少しだけ大きい素数1000000000039でも一瞬で終わることは確かめておいた。ループ判定で乗算しているが、乗算命令は速いのでここが定数でもあまり速度は変わらない。

hardはださい全探索を書いてみたが全く終わらないので諦めた。AnalysisによるとDFAとのこと。

challengeはmediumの3のケースだろうな、と思っていたが開始5秒とかで最初の一人が落とされたのはまいった。√n未満までしか判定してないケースが後まで残っていて気づかなかったのは反省。

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20111119