___82連鎖

2/18/2013

SRM569 Div1 Medium

500

O(n) の貪欲で解ける。
操作は、"Kの倍数を作る"、"全部上の階へ渡す"、"(倍数にならなくても)とにかく上の階から持ってくる"、の3パターンがある。
倍数を作れるなら極力そうした方が良いのは直感的に明らか。
m 階に注目しているとして、m 階に m - 1 階から幾人か上がってきている場合、彼らはその階で消費する必要がある。
その際、上の階からKの倍数にならないとしても全員を持ってきた方が、それより上の階で消費されるべき人数を減らせる。

苦戦した。貪欲は難しいと再認識した。

2/14/2013

SRM570 Div1 Easy

250

プログラムを何週か実行してこれまでと同じ向きで停止できれば、以降はそれの繰り返しになる。
実行回数 T を割り切れない様な周期での繰り返しになる場合は、残りを普通に実行してしまえばいい。

2/07/2013

SRM569 Div1 Easy

250

各桁に関して、1が2個、0が1個必要。

1/30/2013

SRM568 Div1 Easy

250

赤緑青のボールを入れる箱をそれぞれ少なくとも1つは選ばなくてはいけない。
その1つを選び、残りは最も手数の少なくて済む色にしてしまう。

1/16/2013

SRM566 Div1 Medium

500

行列の累乗で計算する。
1 日目と n + 1 日目は同じ移動パターンは同じになるので、(1〜ｎ日目の繰り返し) * (1〜ｍ日まで)を計算すればいい。
繰り返し部分は累乗で計算し、残りを掛け算すれば答えになる。
ただ、愚直に行列の計算をやるとTLEは必至だが、行列が巡回行列なので、最初の1行だけあれば計算できる。

巡回行列なんて初めて聞いた単語だったけど、
c[ i ][ j ] += a[ i ][ k ] * b[ k ][ j ] の i を 0 にして置き換えたら式が分かった。

しかし、以下の実装だとそれなりに遅い。
累乗の計算を再帰せずにやったとしても、行列の掛け算を(0〜n-1)、(0〜m-1)の2つに分けると間に合わない。

(0〜m-1)の時点で別の変数を使って残りを計算する、としている人がいたので真似てみた。
そしたら間に合った。