貪欲に決めていく 問題 D - K-th K 長さ$N$列の数列$x$が与えられる。$1\le i \le N$を満たす各$i$をちょうど$N$回ずつ含む長さ$N^2$の数列であって、任意の$1\le i\le N$について$i$が$i$番目に現れるインデックスが$x_i$となるようなものが存在するならば$1$つ出力せよ。 解法 答えとなる配列を用意しておき、配列の値がまだ決まっていない...

前回のABCのupsolve。答え見ちゃったけど思ったよりギャグ 問題 自然数について、自身の桁和が自身を割り切るとき良い整数と呼ぶ。$N\le a<2N$かつ$a,a+1$がともに良い整数となるような$a$が存在するならば$1$つ求めよ。 解法 $a$が$8$の倍数かつ桁和が$8$で、$a+1$の桁和が$9$であるような$N\le a<2N$は条件を満たす。 これ...

前の精進つながりで$\mathrm{xor}$の問題。後ろから考える。 問題 A - Xor Battle 人$0$と人$1$がゲームをする。変数$x=0$とし$i$回目のラウンドで人$S_i$はなにもしないか$x \gets x\oplus A_i$とするかを選択する。最終的に人$0$は$x=0$を、人$1$は$x\ne 0$を目指すとき達成するのはどちらか？ 解法 たいていのケースで人...

線型代数の話 問題 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] $全体の集合...

1. [1-] $S,T$を互いに素な$1$要素の集合としたとき、$S \cup T$の要素数は？ $2$.(それはそう) 2.[1+] $\mathrm{(a)}$ $[10]$の部分集合であって少なくとも1つの奇数を含むものは何通り？ 偶数と奇数別々に考えて良くて偶数の選び方は$2^5$通り,奇数の選び方は$2^5-1$通りあるから$2^5\cdot(2^5-1) = 992$通り ...