SRM568 Div1 Easy

250

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

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)の時点で別の変数を使って残りを計算する、としている人がいたので真似てみた。
そしたら間に合った。

SRM566 Div1 Easy

250

ある1頂点だけから複数本の辺が出ている
辺が1つしかない
辺が1つもない
ある3頂点が3辺で結ばれている。

の4パターンを数える。

SRM565 Div1 Medium

500

約数でニムをやる。

しかし、ニムに関してより約数を求めるところでつまずく。
区間篩なるモノがあるそうなので、それを模倣してある区間の約数を計算した。ありがとうスパソ。

SRM565 Div1 Easy

250

DP[どこまで見た][いくら使った] = 合計

SRM564 Div1 Medium

500

DP[何個目][どの色が残っている][次に消すべき色] = パターン数
k が 1-based ということを見落として数時間を浪費して悲しい。

SRM564 Div1 Easy

250

小さい場合はBFS。大きい場合は全て到達可能。
縦か横の長さが4以上だと全て到達可能になるらしい。