cafelier@SRM

SRM 475

SRM | 23:51 |

SRM 474 の成績・ソース (要ログイン) : AC/AC/- : 久々に良い順位

300開く

• 300-600-900 セットだったので警戒して300から。
• 『Rabbits ...』
  • うさぎさん…！
• 『0からN-1までのNマスが横に並んでて、うさぎさんr匹が別々のマスにいます。ある規則にしたがって各兎は毎ターン左か右に１マス動くんですが、同じマスに複数匹入ったら退場。あと、毎ターン最右のマスは消えていくので、最後２マス残った状態で残ってる兎の数の期待値は？』
  • 規則は：
    • 左端なら常に右へ
    • 右端かその一個右なら常に左へ
    • マスの色が白なら左へ
    • 黒なら右へ
    • 赤なら１ターン前にいたマスに戻る
    • r≦N≦17

• 問題文長いぞ…
• ええと、でもこれ、
• 兎の動き方に確率要素はないから、確率がからむのは初期配置の選び方だけ
  • NCr 通り
  • 思いっきり大雑把に見積もってもせいぜい2^N
  • N-2 ターンでかならず終了するから
  • 毎ターン r 匹のうさぎの動きをシミュレートしても
  • O( 2^N N^2 ) で、N=17 なら終わるんじゃないかなあ。

• ううむしかし、そんな問題文にあるとおりに書くだけの問題はTopCoderらしからぬ…
• きっと綺麗な解法あるんだろうけど…
• でも愚直なシミュレーションで間に合うと信じられるものを書かないという手もあるまい
  • 下手な考えで休むよりとりあえず組んだ方が速い。

• まずテストケース作成
• 小さいケースは…
  • N=2 のときは常に全部生き残るのか。とりあえず全通り作って置こう
  • N=3 のときは、兎消えるパターンと消えないパターンだけ入れておく
  • 最大ケースは適当にランダムに17文字いれておく

• 書き書き
  • r匹の兎の位置を vector<int> rs; に入れて
  • 毎ターンforeach(rabbit in rs) シミュレート
  • あ、直前の位置情報も要るんだった。vector< pair<int,int> > でいいや。
• できた

• サンプル通る。
• 17文字のケースも問題ないなあ。
• なにか酷い最悪ケースがあるのだろうか。
• ええと…どういうケースが一番この実装にとって遅いか…
• いや、逆に考えるんだ
• 「兎が重なったら消える」とか
• 「兎がゼロ匹になったら即座にreturn」とか
• そういう、データによって処理時間が変わるような要因を全部コメントアウトして、
• 答えは変わるかもしれないけど、とにかくr匹全員N-2ターン最後までシミュレートさせてみる。さっきの17マスデータで。
• どんな入力でもこれよりは時間掛からないはず
• うん、これでも速度問題なし。
• submit！

600開く

• またややこしい規則が長い問題文が…
  • パラメタは 1 ≦ k ≦ 1000万 と
  • 1≦leave[0]＜leave[1]＜...＜leave[N-1]≦k
  • N≦50
• 『初めに兎さんのカップルがおられた。一年目である。二年目には何事もなかった。それから兎カップルは言われた「子供あれ」と。すると二匹の子兎があるようになった。そののち一月後、子兎たちはカップルとなった。こうして兎は４匹となり、２組のカップルとなった。三年目である。』
  • そんな文章ではなかったけど、とにかく
    • 最初に１組のカップルがいる。各カップルは、２年後から、毎年１組のカップルを生むようになる
  • というウサギ算式に増えていく。ただし
• 『兎さんはお造りになったすべてのものをご覧になった。見よ、それは極めて良かった。この年に兎さんカップルの半数は繁殖の仕事を離れ、安息なさったので、第leave[0]年目を祝福し、聖別された。』
  • じゃなくてとにかく、leave[i] 年目の終わりには、兎カップルの半分（奇数の場合は切り上げ）がこの地を去っていきます。
  • 年老いた兎カップルから順に去っていくらしい
  • さて、k 年目の終わりに残っている兎は何組？mod 1000000009 で。

• leave が50個しかないことを利用して、そこだけ複雑に計算して、あとの単調な区間は行列ベキ乗の高速化とかでスキップする系かな…？
• ん？でもk≦1000万？
• 線形時間で愚直にシミュレートしても間に合うのでは…
  • 300点問題もそうだけど、
  • それを許さない問題にするつもりなら1億か10億にするだろうしなあ。
  • 大丈夫なのかも

• の前にテストケース作成
• 最大と最小を適当に

• とりあえずmodのことは忘れて計算規則をつかもう
  • 0年目カップル、1年目カップル、2年目(以降)カップル、の数を数える

1 0 0

• これが最初

0 1 0

• 次、子供はまだ生まれない

1 0 1

• 2年目カップルになりつつ子供カップル

1 1 1
2 1 2
3 2 3

• 以下こんな感じ。ええと、要はこうか。

a b c
b+c a b+c

• 0年目は1年目に、1年目以上は子供カップルを生みつつ2年目組に。

• てことは、１年経つと0年組と2年組の数がつねに等しくなるから、
• 年期の入ったカップル側半分を除く、というのは

b+c a b+c
b+c a/2 0

• こういうことか。巧くできてるなあ。

• これはmodを考えなければやはり線形で回せるなあ。
• すぐできそうなので、一応書いてみる。
• うん、これでデカいケース以外は答えがあった。理解間違ってないっぽい。

• さて…
• 単純に mod をとってしまうと、足し算はいいけど、割り算が辛い。
• 本当の割り算ならmod素数なので可能だけど、奇数なら切り捨てる整数除算をしなければいけないので、これは…

• mod 1000000009 の値に加えて、「偶数か奇数か」だけ覚えておくのはどうだろう？
  • そうすれば、偶数ならmod素数の2割りをすればいいし、奇数なら、1引いてから2で割ればいい
  • 偶数かどうかは、偶数+偶数=偶数的な規則で、別途並行して計算しておく。要は mod 2 の情報を別に持っておく。

• これ…じゃない！
• 書き始めちゃったけど、だめじゃん
• 偶数かどうかフラグは、2で割るところでやっぱりどうすればいいのか。
• 「偶数を2でわったら偶数になるか」とか、わかりませんよ。

• ううむ…

• むむ？
• mod 4 の情報をとっておくとどうだ？
  • 0 mod 4 なら、2で割ったら偶数とわかる
  • 2 mod 4 なら、2で割ると奇数になる
  • 1 mod 4 なら、2で割ると偶数
  • 3 mod 4 なら、2で割ると奇数
• この情報があれば、２回までは半分にする演算が実行できるようになる！

• 同様に mod 2^50 の情報をとっておけば？
• 50回まで半分にする演算が実行できるように！

• よっし解けた
• mod 10000000009 と mod 2^55 (念のため) の両方でさっきの b+c a b+c の遷移表を実装
• 半分にする部分も、この情報があれば実装できる。
  • mod 10000000009 での /2 は、偶数なら普通に割る、奇数なら普通に割ってから5億ちょい足す、でいいと思うけど、自信ないからマイライブラリの汎用除算コピペ。

• できた！
• 時間も1000万でも十分いける。submit

900開く

• 『ウサグラミングコンテストの採点の途中です。nチームがm問で競っています。各問題の配点p[i]と、採点済みかどうかフラグと、採点済みなら各チームが正答したかどうかフラグと、採点前ならサブミットしたかどうかフラグが入力されます。トップ q チームから、適当に s チーム選んでチームを作ることになってるのですが、チームの作り方の可能性は何通り？』
  • 問題サイズは50 x 50まで
  • 点数は各問100万点まで

• 全然わからん
• なんか問題とチームの間の二部グラフになったり…
• 全然わからん

• s=2 なら解けるかなあ。
• 50x50のループで2チーム選んで、この2チームを上位qチームに押し上げることができるか？
• は、この2チームのsubmitを全部正解、他は全部WAとなった場合に上位qチームに入るかだから
• そう書くだけ
• でもsが大きいとこれ無理だしなあ

• わからん

撃墜タイム

• 300あんまり間違えどころないだろうし
• 900は一人出してるけどtargetだから合ってるだろうし
• 600かなあ。自分以外に一人いる
  • BigInteger 使って mod 2**50 * 1000000009 で計算している
  • そうか！mod 2**50 と mod 1000000009 を両方持つというのは掛け算で持つのと同じか。

• と感心していたら終了間際にBigInteger解落とされてた
• TLEらしい。この方法にするなら行列ベキ乗をマジメに書かないと間に合わないとか。
• へー。

感想

• 300はよく考えてみると、マスの色は完全に無視して良くて、
• 常に左右に１動くんだからパリティは一定なので、偶奇だけ考えればよいことに終了直後に気づいた
• なるほどなあ。