TopCoder SRM498

こんなの絶対おかしいよ

250

与えられた数列が「等差数列＋等差数列＋定数列＋等差数列＋等差数列」という形の数列になってるかを求めよ。

やるだけ。

450

長方形のマス目があり、基準マスがいくつかある。マス目にそれぞれ石を置く。「石と基準マスの間の距離」が、どの組み合わせについても等しいような置き方は、各置き方について何通りあるか。

各マスについて、各基準マスからの距離をvectorで持ったものを用意して、全く同じvectorがあったらその2マスは互換。nマスが互換であるとき、n!通りが発生するので掛け算するだけ。

1000

きつねが原点にいる。今、(Tx, Ty)に移動しようとしている。きつねは、1回のジャンプで、x方向の正方向に0マスからMxマス、y方向の正方向に0マスからMyマス動ける。動く距離は正でないといけない。また、bがbadに含まれるとき、x方向、y方向両方にbマス動くことはできない。badには10の倍数だけが入っている。ちょうどR回で目的地につく場合の数を求めよ。

「動く距離が正でないといけない」→「0もbadに含まれる」と考えると楽だと思う。
0距離移動を特別視しないことで、移動の仕方はX方向、Y方向について独立に考えることができ、この場合はそれぞれDPで求められる。
bad移動が行われる場合は、包除原理を使えば除去できる。

というところまで思いついて、compileまでしたけどSample(4)が通らずにオワタ

結果

250と450が簡単すぎて早解きゲー。

oox 589.92 97位

Rating: 2477 -> 2485 微増