cafelier@SRM

TCO09 Round1

SRM | 04:13 |

TCO09 Round1 の成績・ソース (要ログイン) : AC/-/- : もう通ればいいんだ…

250開く

• Round1は250をじっくり解きさえすれば通るだろーと甘く見て、普段の500から開きをやめて250に集中することにした。日和ってます。
• 『L個以上100個以下の連続する自然数の和でNになるもののうち一番短い列を求めよ』

• 最初「L個の」と読んでた
  • 和の公式を考えると、先頭をaとすると (a+a+L-1)*L/2 = N になるので
  • そういう a を求めればよい

• 求めた。答え合わない。
  • 「L個以上100個以下」って書いてあるじゃん！
  • 急遽引数名をLLに変え for(int L=LL; L<=100; ++L){...} で周りを囲う。
  • よし答え合った。submit。

• Lは2以上と書いてあるので、変なコーナーケースもないと思う…

500開く

• 『区間 [lower,upper] から独立に M 回自然数を取ってくるとき、sortしてK番目の数がNになる確率は？』

• えーとえーと。
• for(a,b,c) if(a<K<=a+b) p += "N未満がa個、Nがb個、Nより大きいのがc個になる確率" だよね</li>
• "..." の部分は
  • (N-lo)/(up-lo+1)のa乗 × 1/(up-lo+1)のb乗 × (残り)/(up-lo+1)のc乗 × C(M,a)×C(b+c,b)
  • とかだ

• (1/1000)の100乗とか、とてもワイドレンジな浮動小数点数が大量に混ざるんだけどこれ、これだと精度足りなそうな気がする

• うーむ。DPで綺麗に行ったりするかなあ

• M個中K番目がNになる確率 ==
  • 1個目がN未満な確率 × M-1個中K-1番目がNになる確率
  • ＋ 1個目がNより大きい確率 × M-1個中K番目がNになる確率
  • ＋ 1個目がNになる確率 × M-1個中...何？
    • K-1番目かK番目がNになる確率、とか？

• とりあえずそれでプログラム書いてみた。
  • K-1<1になったりK>M-1になったりするパターンのクリップがめんどいなー
• 書けた。全然合わない。
• えー。
  • 「K-1番目かK番目がNになる確率」って嘘じゃん！一個Nが奇譚だから左右上手く分かれればあとはひとつもN要らないよ
  • だめだわからん

• うううう残り20分…あきらめて1000やろう

1000開く

• 『300×300のチェス盤のそれぞれのマスにA～Zの文字が振ってあります。それとは別にA～Zからなる50文字の文字列wordがあたえられます。wordに書いてある文字を順番に踏むように"Unicorn"という駒を動かす動かし方は何通り？ mod 100..07 で』
  • Unicornは、「3マス以上前後左右に進む→垂直に曲がって2マス以上進む」という動きが出来るナイトが飛びすぎた感じのもの

• 行列乗算…だと90000×90000の行列だ。それはない

• いやしかし、Unicornは実はほとんどのマスに行けるので、各ステップで全マスたどって動き方を足し算する必要はなくて、
  • 全マス to 全マス行けると仮定していったん総和を足して、あとで行けないマスからの動き方を引くと速い
  • 1800 マスくらいしか行けないマスはないので。

• 90000*18000*50ってきついか。
  • O(RC(R+C)|word|)
  • しかし時間がない
  • 入力はランダムデータのみだから、多少いい具合にバラけると思うんだよ、たぶん。やってみよう
    • （あとで思うに全部A一色のデータは作れるのでそれだと全然困りますね）

• 書けた。サンプル通った！
• しかし同時にタイムアップ。うわあああもう数分早く500をあきらめていれば！
  • しかし、休憩時間中に300×300のデータを入れてみたら5秒前後。こりゃ無理だ。

感想

• うーむ500全然わからないぞ…まずい
• 1000はそうか、行けないゾーンはあらかじめ各行と列の和を計算しておけばあとは定数時間か。なるほど。