TopCoder SRM 466 DIV1

Programming Algorithm TopCoder SRM

Overview

145.00 + 235.33 + 0(Unopened) + 0 = 380.33

283rd

SRM Rating: 1648 → 1698(+50)

とりあえずyellow残留やたー…

250 Easy

0、または約数を奇数個もつような数(leading zeroもあり)が当選ナンバーである。今あるナンバーの桁を書き換えて当選ナンバーにしたい。最小手数を求めよ。

当選ナンバーは平方数である(簡単な算数)。ナンバーの桁数が10桁以内ということは5桁以内の数の2乗のみ考えればよい。書き換えコストは単に桁ごとに調べればよい。

500 Medium

5N個の異なる数字が5個ずつセットになっている。これらの数字のうち5個が選ばれる。3個が同じセットの中にある確率を求めよ。

Combinationを用いて適当な確率漸化を立ててDPしたけど、おそらくもっと簡単な方法がある。簡単な算数。

1000 Hard

将棋型の盤面があり、白か黒である。初期盤面は黒は8個以下である。白を選んで、そこを中心とした十字を全て黒にする。全体を黒にするための手順は何通りか(modulo)。

まだ解いてない。

補足

250の平方数証明は素数とか使わなくてできるよ

正整数nの正の約数が奇数個⇔nは平方数

nの√n未満の約数の集合を考える。約数はab=nなるaと表現でき、a<√nならばb>√nであるので、この集合は√nより大きい約数と1対1対応する。

約数が奇数個あるとすると、√n未満の約数と√nより大きい約数のペアを取り除いていっても1つ残るはずであるが、それは√n以外ありえない。

同じように考えると逆もまた示せる。

まとめ

  • ○250で平方数に気付くこと。
  • ○250でleading zeroケースに気付くこと。
  • ×250で脊髄反射で編集距離を実装しないこと。
  • ×500で脊髄反射でDPを実装しないこと。

結果的には正答したけど、脊髄反射でコーディングしたせいで時間食った。

眠気のせいにせず次からは1分くらい考えてからコーディングしよう。

あとid:semiexpさん2回で2245さすがです。金おめでとうとしか言えない。