Codeforces Global Round 31 A:gcd(b,l)の倍数を任意に移動できる B:2乗が許される。sをmin(s+a,a+s)で更新していく C:お気持ち貪欲。k奇数の場合は自明。k偶数のとき、b降順にb bit目がなるべく多く1になるようにしていく。各要素は<nが確定したか否かの2状態を持つ。nのb bit目が1のとき、1要素だけ
1
0
1
Replies
状態を<nに変えるとする。 D:「右端がどこか」を状態に持ってDPするようなDPをグッと睨むと、最大値を取る位置は区間をなし、それ以外の位置は最大値-1となる。 E:上の桁から見ていって、初めて異なるbitで区間を前後に分けられる。そのbitを立てるかどうかで場合分け。 F1:数え上げではなく確率で考え
1
0
1
る。マス(i,j)に訪れるときに、マス(i,j)の左下、右上の交点の方向を決めることにする。dp[i][j][a][b]=「現在(i,j)にいて、マス(i,j)の下/右がブロックされている/されていない」ような状態になる確率 としてDP。 F2:間に合わず。以上のDPの遷移を列ごとに行うことを考えれば行列累乗でいけるはず
0
0
2