# CF Round \#664 div.2
Original duration: 120min.
Commentary: https://codeforces.com/blog/entry/81355
Difficulty: 1000(Gray) - 1100(Gray) - 1600(Blue) - 1800(Blue) - 2300(Orange) - 2600(Bronze)

ruthenの提出：https://codeforces.com/submissions/ruthen71
でフィルターかけてください
追記：https://github.com/ruthen71/submissions/tree/master/codeforces/1395

shuzaeiの提出：https://codeforces.com/submissions/shuzaei

## A - Boboniu Likes to Color Balls
### 問題概要
r, g, b, w の ４ 色のボールがあり，rgb 1 セットを w 3 つに変えれる時，回文列にできるか判定

### 解法
偶奇を考えるだけでよい．
`r&&g&&b -> min((r&1)+(g&1)+(b&1),4-((r&1)+(g&1)+(b&1))) <= 1`
`else -> (r&1)+(g&1)+(b&1) <= 1`

### コメント
& の優先順位が分からなかった．

## B - Boboniu Plays Chess
### 問題概要
チェスのルーク（飛車）の動きでマスを全部埋める．

### 解法
最初の行は前後に動く
残りはヘビのように
last を持つと実装でバグらない．

### コメント
コーナーケースが排除されている．甘い．

## C - Boboniu and Bit Operations
### 問題概要
各Aiに対して任意にBjを選び、Ci=Ai&Bjとする
C1|C2|...|Cnの最小値を求めよ

### 解法
dpする
dp[i][j]=Ciまでのorでjにできるか(bool)
初期化
dp[0][0]=1
更新
rep(i, n) rep(j, m) rep(bb, (1<<9)) dp[i + 1][bb | (a[i]) & b[j]] |= dp[i][bb];

bit演算は繰上りがないので最大値を抑えられることや、$NM \leq 40000$ なのであらゆるCiを列挙できるな～あたりから考えました(ruthen)

答え x を全探索します
すべての i について `(A_i & B_j) | x == x` を満たす j が存在すればよい．

↑すごい、なるほど…(ruthen)

## D - Boboniu Chats with Du
### 問題概要
A の順列のうち以下の値の最大値を求める
$A_{B_1}+\cdots+A_{B_{|B|}}, B_{i+1} = B_i + 1 \ {\rm if}\ A_{B_i} \le M\ {\rm else}\ B_i + D$

### 解法
A を M との大小で分ければ，使用数を全探索して累積和で $O(N\log N)$

### コメント
c++20

vector<int> a(n + 1), s(n + 1);
a[1] ... a[n] <-
exclusive_scan(a.begin(), a.end(), s.begin(), x);
s[0] = x;
s[1] = x + a[1];
...
s[n] = x + a[1] + ... + a[n];

vector<int> a(n), s(n);
a[0] ... a[n - 1] <-
inclusive_scan(a.begin(), a.end(), s.begin());
s[0] = a[0];
s[1] = a[0] + a[1];
...
s[n - 1] = a[0] + ... + a[n - 1];

## E - Boboniu Walks on Graph
### 問題概要
列 $P_K$ で，グラフ上の以下の操作で全頂点から元の頂点に戻れるものの個数を求める
$u \to g[u][P[outdegree_u]]$

### 解法
行き先を並べた列が順列になればよい．
これは zobrist hash で O(N + M + K!)
### コメント
気づくのが難しい（典型ではある）

P1 P2.. PK
{...} {...} ... {...}
h() h() ... h()
{1..N}

実装(ruthen)
https://github.com/ruthen71/submissions/blob/master/codeforces/1395/1395_e.cpp
乱数の作り方ってこれで良いのかな
:+1:

Eの証明はまず問題文の条件から、いくつかのサイズ2以上のループの summationである必要があり(必要十分条件)、これは順列で表せる(グラフと対応しているなら必要十分条件、証明は順列がループのsummationであることに従う)。
これは全部の順列と一対一対応しているではなく、例えばid_nを満たすようなグラフは存在しない。
そもそも集合を列挙した時にグラフで表せないような集合になることはないから、順列で表せるなら必ず可能である。

## F 以降は省略