いろいろ方法がある 問題概要 $H\times W$のマス目に正整数が書かれている。高橋くんが$H_1\times W_1$の領域を選び、それを見て青木くんが$H_2\times W_2$の領域を選ぶ。このときのスコアを高橋くんが選び、青木くんが選んでないマス目に書かれた整数の和とする。高橋くんがスコアを最大に、青木くんがスコアを最小にするような戦略を選ぶときスコアはいくらになるか？$H,...

補グラフ、２部グラフ、DP 問題概要 E - Independence $N$頂点$M$辺の無向グラフがある。グラフを2つの完全グラフに分けることができるかを判定し、できるなら両グラフの辺の数の和の最小値を求めよ。 解法 補グラフを考える。頂点を$S,T=[N]\setminus S$に分けるとき、辺は$S,T$間にのみ張られている必要がある。従って補グラフが2部グラフでないなら不可能であ...

hackに失敗して勉強になった 問題概要 $X_1,Y_1$が与えられる。$X_n,Y_n$を \[\begin{align*} X_{n+1} &= X_1 X_n - 5Y_1 Y_n \\ Y_{n+1} &= Y_1 X_n + X_1 Y_n \end{align*}\] で定めるとき$X_1+\dots+X_N,Y_1+\dots+Y_N$を$\mod 9...

何回か前の精進でポインタを知らなくてポインタ木のコードが読めないという事があったのでポインタの入門をしながらsplay treeを書いた。 主に参考にしたのは splay tree をソラで書く！！！ エッ！？ 平衝二分木の update, push (eval, propagate) のタイミングがわからないですって？ フッフッフ…… maspyさんのライブラリ imp...

結構面倒だった 問題概要 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}...