Star sky | Codeforces #427 (Div. 2)
// 思いつき方 // 明るさが最大11種類しかないことに注目 // s, x, y // 部分和sm[s][x][y2]-sm[s][x][y1]は // 初期の明るさsの星のうち、 // (x, y1), (x, y1+1), ... , (x, y2-1) // にある星の数 int sm[11][101][101]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, q, c; cin >> n >> q >> c; rep(i, n) { int x, y, s; cin >> x >> y >> s; sm[s][x][y]++; } // sm[i][x]ごとに部分和を計算する rep(i, c + 1)rep(x, 101)rep(y, 100)sm[i][x][y + 1] += sm[i][x][y]; while (q--) { int t, X1, Y1, X2, Y2, ans = 0; cin >> t >> X1 >> Y1 >> X2 >> Y2; for (int x = X1; x <= X2; ++x) { // 矩形内のすべてのx座標について rep(s, c + 1) { // 初期の明るさがsである星は // t秒後には // (s+t) % (c+1)の明るさになる。 int bri = (s + t) % (c + 1); // 明るさ * 星の数 ans += bri * (sm[s][x][Y2] - sm[s][x][Y1 - 1]); } } cout << ans << endl; } }
Round Subset | Educational Codeforces #26
f(i, x, y)
をi番目までの値のうちx個を使って
z * 5^x * 2^y を作れるとして、その最大のy
ただし、2∤zかつ5∤z
これをDPで解く。
つまり、素因数分解したときの形で
5の次数は添え字として、2の次数は最大値として計算していけばいい。
ちなみに5の次数は
log5(10^18) < 26 より
25 * 200 = 5000 が最大
Switch the Lights | CS Academy #40 (Div. 2 only)
まず1番目のスイッチを押すかどうか決める。1番目のライトをON/OFFするのは1番目のスイッチだけなので、1番目のライトがONならば押さない。OFFならばスイッチをおす。これで1番目のスイッチを押すかどうか決めて処理した。以後、1番目のスイッチは考えない。
2番目のスイッチを押すかどうか考える。1番目のスイッチを除けば2番目のライトのON/OFFするのは2番目のスイッチだけなので、2番目のライトを見て決める。
以下、同様にN番目のライトまで見ていけばいい。
Move the Bishop | CS Academy #40 (Div. 2 only)
(1) (R1+C1) ≢ (R2+C2) (mod 2) の場合
移動できない。市松模様の同じ色しか移動できない。
以下、(1)でないと仮定する。
(2) (R1,C1) = (R2,C2)の場合
0回
(3) (R1, C1)が(R2,C2)の対角線上にある場合
1回
(4) (R1, C1)が(R2,C2)の対角線上にない場合
まず、(R2,C2)の対角線上にある(R2,C2)でないある点まで移動する。次に、(R2,C2)まで移動する。
2回
SRM 717 DIV1 250: ScoresSequence
i!=jとしたとき辺(i, j)または(j, i)のどちらか1つだけを必ず使いたい。すべての異なる2値{i, j}でそうしたい。最大フローっぽいが、出次数の制約も考えなければならない。出次数の制約より、x!=iとして(x, i)であるような辺はs[i]個以下でなければならない。このようにiへ向かう辺を使う場合というのを1個の頂点で表し、そこへ辺(x, i)を向ける。下の図のようなグラフで最大フローをやる。
Codeforces #421 (Div. 1) B: Mister B and PR Shifts
まず初期状態のdeviationを計算しておく。
1回のcyclic shiftでdeviationの値がどのように変化するかを知りたい。
基本的には
p[i] < iのときp[i]の位置はiに近づくので、そのような値はdeviationを1だけ減らす。
p[i]>=iのときp[i]の位置はiから離れるので、そのような値はdeviationを1だけ増やす。
なので、次のcyclic shiftによってdeviationを減らす値と増やす値を数えておく。仮にそれぞれx, yとする。それによって毎ターンdeviationを増減させる。
ただし、この方針では右端が例外になる。
i(i>1)番目にある値はn-i回目のシフトで右端から左端へ移動する。このときだけ、deviationの計算をうまく分ける。
すなわち値zについて考える場合
deviationから|n-z|を引いて|1-z|を足す。また、このときx, yが変わる場合があるので注意。上図では
3は3から離れる => 3は3に近づく
というふうに状態が変化している。すなわち、
x++, y--
となる。
x, yの変化はもう1種類あって
のようにp[i]=iになるような場合で
x--, y++となる。
ただし、
のような場合に注意。
コード
Submission #28107263 - Codeforces