hotpepsiの練習帳

SRM 524 Div2

20:47

Easy (250) ShippingCubes

問題

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

方針

• 素因数分解して組み合わせ、と思ったが
• Nが小さいので全探索に切り替え
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_524/ShippingCubes.cpp

Medium (500) MagicDiamonds

問題

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

方針

• 合成数なら1、素数なら2 (素数の場合、偶数と1の2回に分割できる)
• ただし3の場合は3 つまりn<=3ならnを返せばよい
• 偶数をはじいてから、3から√nまでの奇数で割ってみて素数判定
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_524/MagicDiamonds.cpp

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未満までしか判定してないケースが後まで残っていて気づかなかったのは反省。