練習メモ2-3

なんかthinkpadのwindowsが起動しなくなった。
最近はデスクトップのLinuxをメインで使っていてthinkpadはもはやゲーム機と化していたのでそんなには困らないんだけど、いい感じのとこまでゲームを進めていたので普通に辛い。原因がサッパリなんだが、どうしようか……。
yukicoder 484 収穫
常に端から収穫していくのが最適だと気づけば普通の区間DPで解けるのだが、なかなか気づかないよね……。
http://yukicoder.me/submissions/149864

CodeForces 396div2 E Mahmoud and a xor trip
ビットごとに独立に考えるのは定番の考え方なので、頭に留めておこう。
ビットごとに独立と考えるとXor値が０のパス、１のパスの個数を伝播させる木DPをすればよい。
子 -> 自分 -> 子が
0 -> 0 -> 1
1 -> 0 -> 0
0 -> 1 -> 0
1 -> 1 -> 1
になるのはそのまま答えに足してしまうので、Typical DP Contestでもあったように、順番にかけあわせて組み合わせの総数を計算する。
例えば
5, 4, 3, 4から２つ選ぶときの組み合わせの総数は
5 * (4 + 3 + 4) + 4 * (3 + 4) + 3 * 4
=
5 * 4 + 9(= 5 + 4) * 3 + 12( = 5 + 4 + 3) * 4
のように、和をもっておくことでも計算できる。こっちの方が実装しやすいのでこっちで計算する。
http://codeforces.com/contest/766/submission/24608853

CodeForces 97B SuperSet
蟻本に分割統治の練習問題として載っていた問題。
面倒な解法しか思いつかなかったが、かなりシンプルに解ける。
与えられた点集合を含み、任意の２点について
・ｘ座標またはｙ座標が等しい
・その２点をコーナーとする長方形がS内の点を一つ以上含む
のどちらかを満たすような集合Sを求める。
とりあえずｘ座標でソートして、区間をくっつけるときは真ん中の点を含む縦棒上に、その区間内の点全部のｙ座標を網羅するようにプロットする。こうすると、左側の区間の点aと右側の区間の点ｂで長方形をつくるとき、真ん中の縦棒にプロットした点を必ず通る。

手抜きしてSetを使ったのでNlog^2N
点の数はたぶんNlogNくらいだと思う。