codeforcesの復習 - yagura37s’s blog

println!は遅いので出力は以下のコードに

let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
//writeln!(out, "{}", res.len()).ok();

F 数学

// n0 - n1 >= 0 & (n0-n1)%3 == 0 を少なくとも満たしていないといけないが、隣り合って居るやつしか変更できないという条件も考慮するとこれだけでは足りないと思いきやこの条件だけで行ける。 (n0-n1)/2が変更できる回数になる。

D xor binary_trie

//１〜ｎのxorを眺めると、上からx桁目までは等しいとして、x+1桁目が0と1になっているグループをそれぞれ眺めると、問題の制約化では一意に定まる。なので大きい方と小さい方に分けることをやっていくと行ける。binary_trieを持っているとすごく簡単になる。

E 集合と論理

//一番大きいやつは確定で勝ち。dp[x1][y1] = 1 で勝ちとして、　manhattan(x1, x2, y1, y2)>kのセルはdp[x2][y2] = 0.

// P : dp[x1][y1] = 1

// Q: manhattan(x1, x2, y1, y2)>k

// R: dp[x2][y2] = 0

// P&Q->R !R -> !P or !Q

//で聞くと、dp[x1][y1] = 1の時は!Pではないので、!Rが成り立つためには!Qを満たす必要がある。

//なのでdp[x1][y1]=1 dp[x2][y2]=1　なら　manhattan(x1, x2, y1, y2)<=k である。

//やはり上記で言われたとおり、3. 「すべて」や「ある」を含む命題の扱い方

//の時にややこしくなってる気がする

//やっぱちょっとわかんないかも

//dp[x1][y1]=1を満たす集合で考えるということにしておこう。

D:dp 調和級数dp 良い　楽しい

Codeforces Global Round 19

　B dp 区間dp?

// 区間数１の場合をとりあえず求めて、左側に区間を１個ずつ追加する。区間数１,2, 3..の順番で求める。　O(n^4)だが、定数倍が軽いので行ける。　全部バラバラにするのが最適解らしい

　D dp

// dp[i] = 現在aに属する要素の和がiになるような列の答えの最小値

　E sqrt double_pointer　難しい

// 「数ごとの頻度」のヒストグラムを取ると、そのヒストグラムの横軸の長さは、数列の長さをnとするとsqrt(n)以下らしい　どの部分か知らんけどdouble_pointerと言うらしい

　D 後ろから考える　難しい

　E 区間を分割、区間をマージはO(N)になる　遅延評価セグメント木難しい