cafelier@SRM

SRM466

SRM | 13:12 |

SRM466 の成績・ソース (要ログイン) : AC/AC/- : 最近このゾーンで安定してしまっている

500開く

• 『横5縦Nの5Nマスに、1～5Nまでの数字を全部使ってランダムに書き込みます。すると5個の数字がランダムにアナウンスされて、そのうち3個以上を含んでいる横の行があれば当たり、なければ外れです。当たる確率は？』
  • 1≦N≦100

• テストケース作成
  • 小さい方の例は…N=1,2,3 はサンプルに元々入ってるな
  • じゃあ大きい方だけ、N=98,99,100 を追加。

• で、
• え？これ簡単じゃないの？
  • 最初にどう数字を埋めるかはまったく確率に影響しないので、1～5Nまで左上から順に書いたとしてよい
  • すると、5個の数字がランダムにコールされる場合の数は C(5N,5) 通り。
  • そのうち当たりになる場合は
    • 5個全部同じ行に来るケース。N行あるのでN通り
    • 4個同じ行に来て残り1個別の所。
      • 4個がくるところの選び方N通り
      • その行の5個から4カ所選ぶ選び方が C(5,4)通り
      • 残り1個がくる行の選び方はN-1通り
      • その行の5個から1カ所選ぶ選び方が C(5,1)通り
    • 3個同じ行に来て残り2個別の行。
      • おなじく N*C(5,3)*(N-1)*C(5,2)通り
    • 3個同じ行に来て残り1個と1個が別の行。
      • 同様に N*C(5,3)*C(N-1,2)*5*5通り

• ということで、全部足し算して C(5N,5) で割るだけ…
• これ別にオーバーフロー起きないよね。
  • 出てくる最大の数はせいぜい500**5だし、64bit整数で十分。

• 書いている
  • C関数わざわざ書くの面倒いなー。手計算でいいや
    • C(5,4)=10
    • C(5,3)=20
    • などの間違いを連発する
    • あとC(5N,5)のつもりで(N-1)*(N-2)*.../120
• 答えあわない
• あれ？
• あれれ？
• うわー色々変だ
• なおし直し
• よし、サンプルと答えあった
• しかしN=100の場合、0.04%くらいあるけど、そんな確率高い物…？
  • でもN=6でサンプルとあってて100で間違えるとは考えづらい…
• いいや、出しちゃえ

250開く

• 部屋のスコア見ると、トップの人も210点台。これは難しいか面倒な問題の予感
• 『N桁の数字(leading 0もありうる)が入力されます。これを何文字か書き換えて、「0、もしくは約数の数が奇数個」となるようにしたい。最低何文字書き換えればいいですか』
  • 1≦N≦10

• テストケース追加
  • "0"から"9"までは手で考えていれておく
  • あとは最大ケース"1111111111"～"9999999999"あたり。

• 10ということは10!くらいでnext_permutationという脊髄反射…
• いや、別に並び替える物ないし…
• 書き換え方を全探索するとどんなもんだろう？
• 全ての桁について、書き換えないという選択も含めて10通りの変化があるから、10^N。
• これ全探索は無理だな。

• すると、「0、もしくは約数の個数が奇数個」という性質を見れば書き換え方が明らかだったりするのか
• 考えよう。

• （※最初なぜか、偶数の約数の個数が奇数個、と勘違いしていた）
  • ええと奇数なら偶数の約数は0個だからダメなので、必ず下一桁を偶数に書き換える必要がある…
  • 2にするか4にするか6にするか8にするか0にするか
  • そしたら、それを2でわった数の「約数の個数が奇数個」という条件になる

• 約数の個数が奇数個、ってなんだろう。
• 2^a 3^b 5^c 7^d ... という数の約数の個数は
  • (1+a)(1+b)(1+c)(1+d)...
• だから、これが奇数ということは、a,b,c,d,...が全て偶数と言うこと。
• ということは、全部の素因数の係数に2が入ってる
  • 2^2a 3^2b 5^2c 7^2d ...
• わけだから
  • (2^a 3^b 5^c 7^d ...)^2
• だ。

• おお、つまり平方数なら約数の個数は奇数だし、逆にそうでなければ奇数でない。
• そういえばそんな性質、聞き覚えがある。

• てことは、平方数（※まだ勘違いしている）の２倍の数を全列挙して、それとのdiffの最小値が答え。
• 10^10までの平方数は5^10個くらいしかないから、
• 全列挙しても十分間に合う。

• 書いた。
• あれ答えが合わない。
• いや、でも自分の手計算とプログラムはあってるのだが…
• 問題勘違いしているかなー。
• は！
• どこにも偶数の約数の個数が奇数個なんて書いてないぞ！
• 普通に約数の個数じゃん！
• "～ divides evenly" は単にピッタリ割り切れるという意味だよなー微妙に英語力を要求してしまって良くないのでは…とかお節介なことまで考えていたはずなのに普通に自分が引っかかってる！アホか！

• 直した。あった。submit。

1000開く

• 『最大20*20のマス目のうち最大8個が黒く塗られてます。「白いマスを選んで、そことx or y座標が同じ所を全部十字に塗る」を繰り返して全部を黒に塗る手順の個数を数えてね。mod 1000000007で。』

• 左上から順に塗れるところを塗っていって、q回で塗れたらq!をかえす、で、総和を取る
• でどうだろう。各列の塗り具合2^20と行番号20でメモ化すれば　2^20*20 = 2000万くらいで。
• これだと初期黒マスが8個しかないことが何も効いてこないか。
• まあ気にせず実装してればわかるのでは

• 実装
• 実装
• 実装
• できた。
  • むう。小さいので答えはあうけど大きいのだと余裕のTLE。

• 初期8マスの意味が…
• わからない…
• うむむ…

撃墜タイム

• C(500,5) が int を溢れる対策してない人がいるだろ、と思って準備
• doubleにもlong longにもキャストしてない(5*N)*(5*N-1)*...
• という式が見えたので即チャレンジ！
• あ、double N=n; とか上の方に書いてあった！うわーしまった。-25。

• leading zeroをうまく扱えてない人を一人見つけて+50。
  • "2321" を入力すると "02321" に拡張してしまってから "12321"を作ってしまうコードだった

感想

• 500は一発でバグなく打ち込めなきゃいけないレベルだった…
• とかいう段階で戦うのではなくて、今回くらいの難易度なら1000を解けるようにならないとなあ。やっぱり。
• 初期8マスしか黒がないと、たかだか8行/列しかパターンの違いがないので、同じパターンのところは全部同じ状態と思ってつぶせるらしい。なるほどなー。