cafelier@SRM

SRM478

SRM | 21:34 |

SRM478 の成績・ソース (要ログイン) : AC/AC/- : だめだー

500開く

• 『Taro 』はい
  • Taroさんにきうぃさんがすり潰されている…
• 『容量CのボトルがN本あります。最初にそれぞれいくらかずつキウィジュースが入ってます。ジュースがx入ってるボトルはP[x]円で売れます。2本選んでどっちかをどっちかに限界まで注ぐ(片方が満タンになるか空になるまで注ぐ)を飽きるまで繰り返してよいので、できる限りお金稼げる状態にしてください』
  • C≦50, N≦15, P[x]≦100万

• テストデータ作ろうとしたけど、サンプル見てみると既に親切だ。じゃあいいや。

• N 小さいな。O(2^N) か O(3^N) か。
• P[x]が小さくはないけど大きくもないのが気になるな。CP≦5000万とかいう解があったり…？ないか。

• まず、注ぎかえ操作を１回やるとどう状態が変わるか考えてみよう。
  • (a,b) → (0, a+b)
  • (a,b) → (a+b-C, C)
• のどっちか。どっちをどっちに注ぐか、は区別しなくていいな。結果を入れ替えれば同じ事だから。
• a か b が 0 だったら状態変化しない
• a か b が C の時も状態変化しない
• それ以外で１回操作すると0かCが1個増える

• ということは、最大14回注ぎ変えしたらそこで試合終了！
• いやーうまくできているもんだ。

• でもまだ何も解けてない
• 14回の注ぎ変えを全探索すると 14! なので無理。

• これを減らすには…うむむ…
• さらに何かやっても意味ない操作があってそれを考えないようにするとか…

• 「aからbに注ぐ、bからcに注ぐ」みたいに「注がれたのを注ぐ」は意味ない仮説！
• というのはどうだ。
• 「aからcに注ぐ、bからcに注ぐ」でも同じことになりそうだし
• 溢れるケースがちょっと不安だけど…いや、これは大丈夫

• てことは、「注がれた」フラグをそれそれのビンに立てておいて、それは他に動かす探索は禁止
• とすると状態どれくらい減るかな。
• 注ぎ移動が起きるのがだいたい半分くらいにならないか
• そして 14! が半分の 14*13*...*8 になったり
• したら 10! * 14*13*12*11 / 5040 はなんか間に合いそう。

• やってみよう。
• 実装
• 実装
• 実装
• できた

• おそっ

• 最大ケースで全然帰ってこないなー。
• 小さいので答えは合うんだけど。

• てかこれ速度以前に、本当に正しいのかな
• 「どっちをどっちに注ぐか、は区別しなくていい」と「一度注がれたらフラグ立てといて二度と注がない」は両立しない仮定のような気がする…
• やめよう
• フラグなし

• ううむ
• メモ化したらどうですかね。
• ビンに入っている容量をソートした配列をkeyに、同じ状態に来たらメモ化した結果を即返す

• やってみた
• 遅い。だめだ。

• ggg
• わからん。他行こう

250開く

• スコア表見ると240点台かなり少ないので250も難問
• 早めに取りかかっておかないと解けなそう…
• ということで、早めに500を離脱
• 『Rabbit 』ちょww
• 『兎さんが 1≦init≦10億6 にいます。ひとっ跳びでxから 4x+3 か 8x+7 に行けます。最短で10億7の倍数のマスに行くには何跳び？10万ピョンを超えるようなら-1を返してね』

• ええと mod 10億7 の世界で考えればよくて。
• 単純にBFSすると、2^10万 はもちろん状態空間ないけど、それだけ分岐してたら10億7の状態空間ほとんど埋め尽くしそうだし、それは探索できないなあ。

• もっと賢く

• 最初ひたすら 4x+3、あとはひたすら 8x+7 、みたいに、最適解は常に混ぜないで作れる、ってことはないかな？
• それが可能であるためには、操作4x+3と8x+7が可換ならよい
  • 4(8x+7)+3 = 32x+31
  • 8(4x+3)+7 = 32x+31
• おお可換だ。よし。

• じゃあ、4x+3を10万跳びためしてみて、そこそれぞれから8x+7を10万跳び…
• それは 10万^2 の計算は無理だ…

• どうするんだこれ。

• ううむ。
• 4x+3 も 8x+7 も 32x+31 も 2^n x + 2^n - 1 の形
• これは気になるな。偶然か？

• いやいや
  • 2^q(2^p x + 2^p - 1) + 2^q - 1
  • = 2^{p+q} x + 2^{p+q} - 1
• だ
• この形のジャンプは常に合成してもこの形

• ということは
  • 4x+3 を a 回
  • 8x+7 を b 回
• やると
  • 2^{2a+3b} init + 2^{2a+3b} - 1
• に居ることになる。

• ということは
  • 2^{2a+3b} init + 2^{2a+3b} - 1 == 0 mod 10億7
• となるような最小の 2≦2a+3b≦30万 を探せばいい！
• これは単に30万回 x2 して0になるか調べるだけ。

• 2a+3b = p で ==0 になったとすると、
• だいたい b≒p/3 で余りを a で調整すればいいから
• 適当にaとbが求まる

• できた
• 解けた。submit！

500に戻る

• 今回難しいから、500解けなくても順位悪くないだろ…
• と思ったら、結構みんな解いてる…なにー！

• でもわからない。
• やっぱり 2^N とかそういうビットDPしかないと思うんですよ
• 他では計算量がおかしい

• 「注ぎ注がれ関係の強連結成分分解」を考えると、連結成分内でどう注ごうがスコアは一致したりしないだろうか
  • そうすれば、N本をどういう部分集合に分解するかの探索なので、2^N 状態の部分集合探す奴だからたぶん間に合う

• やってみるか。
• 答え合えばsubmitする。
• 「aをbに、bをcに」は「aをcに、bをcに」としても同じ
• の繰り返しと考えれば成り立ちそうな気もする

• というわけで、部分集合に分解→各集合の中ではできるだけ少ない本数のビンにまとめたときのお値段を返す

• とやってビットDP
• あ、答え合った
• 最大ケースローカルで10秒…

• このDP表のmapをvectorに
• 2.5秒
• 行ける。submit！

撃墜タイム

• 250…ふつうにBFSしてる人がいる！これはTLEだろ～
• いやまて
• 結局 2^{2a+3b} x + ... の形のところしか行けないのだから30万個しか探索される空間がない！
• これ普通にBFSしても解けちゃうじゃん。ひえー

• 500は、自分以外にsubmitしてる人が二人
  • １人はビットDPしてる。まあ同じ解でしょう
  • １人は…おいrand()とか見えるんですけど…
    • 乱数解にChallengeは怖いなあ
    • ええと、どうやって乱数使ってるんだろう
    • 「greedyに、儲けが増える方向に注ぎかえる。儲けが変わらない場合は50%の確率で注ぎかえる。」
    • という使い方だった
    • それはダメだ。一次的に儲けが減る状態へ移る場合が簡単につくれる。
    • +50

感想

• チャレンジ成功すると、本編gdgdでもなんだか満足してしまう