線型代数の話 問題 G - Partial Xor Enumeration 長さ$N$の非負整数列$A$が与えられる。$A$から$0$個以上の要素を選び$\mathrm{xor}$をとってできる数の集合を$S$とする。$S$の$i$番目に小さい要素を$s_i$として、$s_L,\dots,s_R$を出力せよ。 制約 $N,R-L \le 2 \times 10^5,A_i\le 2^{60}...

広告で見るゲームの話 問題 E - Connected? $R \times C$の長方形の内部または周上に$1$から$N$までの番号がつけられた点が$2$個ずつ配置されている。長方形から出ず、互いに交わらないようにして同じ番号同士の点を曲線で結ぶことができるか？ 解法 長方形の内部の点を、他の点と被らないように内部の好きな位置に移動しても結べるかどうかは変わらない。同じ数字の点の一方を他...

問題 F - Subsequence LCM 長さ$N$の正整数列$A$と正整数$M$が与えられる。$A$の空でない部分列であって、列の要素の最小公倍数が$M$になるようなものの個数を求めよ。 解法 $M$の約数でないような要素は選ばないので予め取り除いておく。また、空でないという条件を無視する($M=1$のときのみ空部分列を数えてしまうから、答えから$1$引く)。 $M = \prod_...

黄色以上の問題を【精進】として解いていく。現在解いてない黄色の問題はProblemsによると$367$問残っているようなので1日1問程度解けば年内に黄色を埋められる計算になりそれを目指して進めていく 問題 G - Balance Update Query $N$種類のカードがあり、得点$a_i$と使用可能枚数$b_i$が定まっている。$3$種類のクエリを処理する $x$種類目の得点を更...

問題 Ex - K-Coloring $N$頂点$M$辺の無向グラフ$G=(V,E)$が与えられる。 各頂点を$1\sim K$の色で塗る方法であって、隣り合った頂点が異なる色で塗られているものの個数を求めよ。 解説 解説放送では包除原理があっさり説明されていたのでその部分を書く。\(\{ 1,2,\dots,N \}\)を$[N]$と書く。 彩色 $ c: V \to [K] $全体の集合...