結構面倒だった 問題概要 C - 有向グラフ $N$頂点$M$辺の有向グラフが与えられる。各頂点には英小文字が書かれている。好きな頂点から開始し、英小文字を回収するか選び移動することを繰り返すとき長さ$K$の得られる文字列の内、辞書順最小のものを求めよ。 解法 強連結な集合内は自由に行き来できるから、文字を小さい順に貪欲に回収できる。従って強連結成分分解することで各頂点に(文字ではなく)文...

XOR基底シリーズ 問題 $N=2^n$頂点がある。長さ$M$の列$A$が与えられ、任意の$i$について$s\oplus t \ne A_i$のとき頂点$s,t$間に辺を張ることができる。連結にできるか判定し、できるなら$1$つ辺の貼り方を出力せよ。 解法 $A$よりも$A$にない数に注目する。$B$を$0$以上$N$未満の数であって$A$のどの要素とも異なるものの集合とする。$B$の張...

貪欲に決めていく 問題 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] $全体の集合...