cafelier@SRM

SRM458

SRM | 01:40 |

SRM458 の成績・ソース (要ログイン) : AC/AC/- : 落ち着け自分

450開く

• 『1円, a円, ab円, abc円, ... のように倍数倍数の関係の種類の硬貨があるシステムを作ります。price[0]円のものを１個、price[1]円のものを１個、…price[N-1]円のものを１個、それぞれ別々に買うときに払うコインの枚数が最小になるようにしてください』
  • 1≦N≦50
  • price[i]≦100000

• そういえば、今使っているTZTester改では、データを埋めてないテストケースを２個生成するようにしてます。まずそのケースを埋めないとコンパイルが通らない。最初に必ずコーナーケースを作る習慣をつけようということで。
  • 今回から作ったケースもメモっておくことに。
    • price = {1} (最小)
    • price = {1,2,3,4,...,39,99940,99941,...,99949,100000} (最大)

• さて。
• 最高で100000円なら、それより大きい額面の硬貨を作っても意味ないよね。それ以下。
• 倍数倍数で硬貨の値段を決めるってことは、最大でも 1,2,4,8,.. の17種類しか硬貨は使わない

• てことは、可能なパターン数実は少ないんじゃないかなあ。
  • 硬貨の値段をfixしちゃえば、払う枚数の最小化は普通に解けるはずだし
  • 全パターン生成して試してみればよいとみた
  • 450点ということはそれくらい簡単だろう、きっと！

• [1,2,...], ..., [1,3,...], ..., [1,4,...] 的なものを全生成するルーチン書く
• 書けた。
• 最大priceが100000のケースで全然終わりません。
• あれー？
• メモリ不足で落ちた
• なんか考えてみると、1,a,ab の作り方だけで10万×√10万くらいありそうな気がするな

• 考え直し。ええとええと…
• 下から考えるからパターン数多いんだ。上から考えると
• 最高額の硬貨をPとすると、Pの下はPの約数、その約数、…に限るので自由度があまりないはず

• 全生成するルーチン書く
• 書いた
• はい終わりません
• …
• いや、だって、うん、上から数えても下から数えてもパターン数は同じなんだから全生成したら同じくらい時間かかるよね…

• 全生成してはだめだ
• 硬貨の使い方も考えて生成するパターンを絞る。

• そもそも「払う枚数の最小化は普通に解けるはずだし」とかいっちゃって全然考えてなかったけど、こっちを具体的に考えてみよう
  • 倍数倍数ということは、最高額がP円玉としたとき、n円を払うためには、greedyに、n/P枚のP円玉を使っていい
    • それより安い硬貨も全部Pの約数なのでn/P*P円の部分を余計に枚数費やして払うだけだから
    • という感じで、最高額硬貨から順に使ってgreedyに割っていけば求まる

• で、さて、それを踏まえて。
• 上から全生成するときに、
  • 最高額 P が max(price)の場合、max(price)-1の場合…
    • それぞれについて2番目に高い額QがP/2の場合P/3の場合…
  • ってループしてたけど、
  • Pを一個決めたらすぐΣprice[i]/Pを求めてprice[i]%=Pしてからその先に進む
  • Qはmax(%Pされたprice)よりも小さくないと意味ない、とかで探索範囲を狭められる
  • あとpriceが全部0になったらそこで終わり、打ち切れる

• ということをコードで書きながら考えていました
  • 動かしてみた。50商品の最悪ケースが20秒くらいで一応終わる
  • 20秒…
  • やっぱりこんないい加減な枝刈りは違うよなあ。
  • というかヒューリスティックな枝刈りで通しましょうというのは、問題として美しくないので違う。こんな方針はダメだ。

• うーむ。
• 倍数倍数という縛りはかなり異様にキツい縛りだよねえ。
  • 日本の硬貨は「N円玉/札があればそれより安い硬貨/お札は全てNの約数」が成り立ってるけど
  • 1, 2, 5, ... なので倍数倍数にはなってない。
  • けどさっきまでの自分の解法は、前者の性質しかつかってない。
  • だから間違ってる。後者の性質をちゃんと考慮しなければ

• 1円、a円、{aの倍数...}
• ！！
• 1円は無視して
  • a円、{aの倍数...}
• だったとすると、全部aの倍数の世界だから、これは硬貨の額面とpriceを全部aで割ってしまって
  • 1円、{aの倍数...}/a
• の世界と思っても答えがまったく同じになる
• 元の問題と同じ形になった。これだ！この再帰だ！

• 一番額面の小さい硬貨を a (in 2 .. max(price)) 円とする。
  • {1円、a円、...} のシステムの最適解は、
  • a円の倍数では払えない分を1円玉で払う分 Σprice[i]%a
  • と、これに加えて price/a 円の商品を {1円、...} のシステムで買う場合の最適解
    • これは再帰で求める

• 実装した。実行
• まだ時間がかかる…
• そうか、メモ化しないと。1,2,6,... の場合と1,3,6,...の場合の6を別々に計算しちゃダメだ。
• 面倒くさかったので vector<int> price をキーにメモ化
  • 最悪ケースが10秒くらい
• 面倒くさかったじゃないよ俺。ちゃんと今考えている最小額面(さっきの例だと6とか)をキーにメモ化
  • 最悪ケースが4秒くらい
  • arenaで動かしたら1.4秒
  • 行けるか…？ギリギリだなあ…

• 最初に自分が作ったケースは本当に最悪例か？
• 今のアルゴリズムだと、price配列のサイズだけでなく、price[i]の値が大きいほど時間がかかる
  • 0になるまで割っていってるので。
  • ということは、{100000}*50 みたいなのの方が最悪
  • 10万弱の値をランダムに50個入れたケース
  • 遅い
  • arenaで2秒タイムアウト…

• むむむ…これ考え方はあってると思うんだけど…
• どっか無駄をやってるんだよな。えーと
  • メモをmapからvectorにしてみる
  • 大差なし
  • price/aを求める→再帰呼び出し→メモされてたら即return
  • というのは無駄があるな。「price/aを求める」はメモ済みの場合には不要
  • さきにメモ済みチェックを入れることにした

• よし！最悪ケース通るようになった！
• submit！

250開く

• 『N個の(大きさのない)ボールが数直線上の相異なる整数座標に置いてあります。それぞれ左向きか右向きかランダムに決めて、速度1で転がし始めます。T秒間のあいだに何回の衝突がおこりますか。期待値を求めてね。衝突したら完全弾性衝突で同じ速度で反対に跳ね返ります』
  • N≦12
  • T≦10^9
  • ボールの座標も≦10^9
  • 作ったテストケース
    • {1}
    • {1, 10, 100, ..., 10^8, 2*10^8, 3*10^8, 10^9}

• とりあえず反射的に思い出す考え方として
  • 「大きさもない区別もない点が完全弾性衝突」 == 「衝突して跳ね返ると考えないで、お互いなんの影響もなくすり抜ける、と考えて差し支えない」
  • 公式です。センター試験にでます。

• というわけで、
  • 2^12通りの初期向きを全部生成
  • それぞれシミュレーションして何回衝突するか数える。
  • 跳ね返りは考えないですり抜けると思っていいので、
  • 進行方向が向かい合っていて、距離が2T以内のペアは衝突、他は衝突しません。
  • 数えるだけ。

• できた。submit。

900開く

• あと17分…
• 900ということは簡単なのだろうから、450にあんなに手間取らなければ解ける問題だったかな…
• いやいや諦めるのはまだ早い

• 『4で割って0余る約数の個数がa個、同1余るのがb個、2余りc個、3余りd個、となるような数が存在するとき、組(a,b,c,d)のことをdivisor quadrapletといいます。配列A,B,C,Dのそれぞれから要素a,b,c,dを取り出してdivisor quadrapletを作る作り方は何通り？』
  • A,B,C,Dのサイズは50以下
  • それぞれの要素はlong longには入るくらい

• 手製テストケースは…
• の前に、用意されてるサンプルは…
  • {{1},{1},{1},{0}} と {{0}, {0}, {0}, {0}} と {{0}, {0,1}, {0}, {0}}
• うわ、情報量ない！
• これは逆に、サンプルをちょっとリッチにするとすぐ答えのパターンが見えてしまうので出題者がそれを怖れた系ではないか。

• パターンを見出してみる作業
  • 1から100までの数の約数を数えてdivisor quadrapletを生成してみる
  • それを並べてみる
  • うーん？
  • なんか規則あるかこれ…？
  • ううむ…
  • わからん…

• タイムアウト

撃墜タイム

• 250を素直に1秒1秒シミュレーションしてる人がいたら最大ケース投げつけてタイムアウトを狙う
  • そんな人はいなかった…

感想

• ちゃんと完全に計算量を見切らずにコードを書き始めるのはやめよう。
• ちゃんと完全に計算量を見切らずにコードを書き始めるのはやめよう。
• ちゃんと完全に計算量を見切らずにコードを書き始めるのはやめよう。
• ちゃんと完全に計算量を見切らずにコードを書き始めるのはやめよう。

• 450みたいなのは、↑これを守っていれば何の問題もなく解けるはずなんですよ。落ち着け俺。