443.1

なんとなく解き方が分かったので色々。

300

N個の円があって、いずれも点を共有しない。指定された二点間を移動するとき、跨ぐ必要のある円弧の最小数を答えよ、という問題。

開始点と終了点で円の内外判定が異なるものは絶対跨ぐし、そうでないのは避けられる。

600

A個の0とB個の1からK個フリップする操作で全部1にするのにかかる最小ステップ数を求めよ、という問題。

BFSするだけ。ただしN^2を全部計算するとTLEするので、各点から次に遷移できる点を考慮する際に枝を狩る必要がある。できるだけ0を減らすのと増やすのの0の数が分かれば、0の取り得る範囲はその間の1個置きの値すべて。(実はこれを覚えておいて収束するまで繰り返した方がいいのかも？)両端と現在の0の数を除いたとき、P個の0とQ個の0が既に達成できたなら、その間はすべて達成できていることが言える。P->QならばQ->Pだし、P->Q->RならP->Rは成り立たない(そうじゃないとQの時点では探索済みになっているはず)とかそういうことから言える。

ソースが汚いので、多分各ステップで達成できる0の個数を覚えておいて頑張る方がいいのかなぁ、という感じ。(ちょっと考えたら相当面倒だったけれど。)

1000

問題は略して...。

要は行列乗算に落とすための行列を作りましょうという問題なので、行列を作る作業。ある曲Gの長さがNだったら、Hは次に可能な曲として、(G,0)->(H,N)という遷移が起そうなのだけれど、行列乗算を一回適用すると1ステップ経過するので、行列的には(G,0)->(H,N-1)に遷移することになる。後、あらかじめ計算しておいた未来の値が1ステップ経過することで降りてくるので、(G,P)->(G,P-1)な遷移が必要。カウンタについては(C,0)->(C,0)を入れておくことで蓄積されるし、ある曲が達成できた時点で(G,0)->(C,N-1)をちゃんと入れておく必要がある。後はカウンタの値をちゃんと拾ってあげるだけ。

で、実は行列乗算がかなりしんどいというオチつき。行列は90x90で、2^30乗くらいしてあげる必要があるので、下手にやると90回くらい乗算が必要。削ると60回。実際にやってみたら倍くらいにしないと間に合わないという結論だったので、途中経過を計算するときのmod演算を極力削る方向で努力して解決。modのうまいやり方を工夫するのは非常に重要らしいので、行列乗算を書くときは常にそれに注意しないとダメそう。