久しぶりにCFに参加した。（開始10分後くらいに偶然TLを見て気づいた）
A
問題文が難しい＞＜
B
まぁ。
C
として、正しいかチェック。
D
累積xorをとって長さn+1の数列Xを作る。
Xから同じ数を２つ取ってきてその間を選ぶとxorが0になる。
つまり、とすると、
を最小化すればいい。
操作はある場所以降をflipに対応してるので、組み合わせると最初以外の要素を好きにflipできる。
は一定だが、その範疇では好きに配分できる。半分ずつくらいに配分すると最小になる。
E
「1行目に0を、2行目に1を集める」というのを標準形とする。
任意の状態←→標準形も標準形←→標準形もs回の操作で変換できるので、3s回でできる。
F
とりあえず各点を長さ0の線分で覆えば達成はできる。
隣り合う線分の間を繋ぐと答えが１減る。
"間"の線分を交差しないようにできるだけたくさん選ぶ問題になる。
縦と横の二部グラフで最大独立集合を取る問題になってあとは復元とか頑張って。
二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！
G
葉から順に消していく。
- ビット数=1のコミュニティは消す。
- 残りのコミュニティで常にs[i][v]=1,s[i][u]=0になってるiが無ければvをuにくっついてる葉としてvを消す。
コミュニティを全部消せればYES。（連結になってなかったら適当に繋ぐ）
実装はbitsetを使ってO(2000^3/64)
- a[i] = s[i]
- d[i] = a[j][i]=1であるようなa[j]の&を取ったもの(iビット目は0にする)
を持って、
- a[i].count() == 1があったらa[i]を消して、立ってるbitをjとしてd[j]だけ再計算
- d[i] != 0があったらiを葉にする
って感じでやる
lewin氏の別解頭良さそう。
完全グラフを作って辺uvの重みはs[i][u]=s[i][v]=1になってるiの個数にする。そのグラフでMST(minじゃなくてmaxだけど)を求めてそれをチェックすればいい。
重みを全部計算するのは長さMのbitsetで&とpopcountをすれば/64できる。（CFだと/32なんだっけ...）
感想
普通に楽しかったしCFもっと出ていきたい。（とりあえずIGM,LGMに戻すぞー、Nutellaになりたい）
