# ICPC Training Camp Day1 # A 数字の集合Sが与えられるので、 全ての値が 1以上X以下の、XOR基底の個数を数え上げよ SのXOR基底は、相異なる整数の集合で、Sを全て構築可能なもののうち、最小の要素数の物である。 --- とりあえず、XOR基底1つは構成できる。 X以下… なので 一番桁が大きい奴にだけ注目すればいいかな X,Y が既定の時、X^Y,Y も当然基底 --- # B インタラクティブ $P_i \rarrow P_j$ から見て、 $P_i \rarrow P_k$ が時計廻るか反時計回りかのクエリができる 凸包を構築せよ --- i->j を中心に偏角ソートしたい… すると、凸法上の頂点はその順に並ぶ → クエリの回数が足りなさそう…？ ans = 0 for i in range(1,5001): ans += math.log(i,2) ans -> 54232.55632160193 なので足りません --- ランダムな点であることが補償されているので、凸法上の点の個数は少なさそう # C n要素の順列が与えられる。 ある要素は、それ以前のどの要素よりも大きい場合recordである k個のレコードを持つすべてのsubsequenceに関して、(-1)^len の総和を求めよ --- レコード 尺取り法的に？ 伸ばすと, レコード数は大きくなる一方 一方で左端を削ると、レコードは増減両方起こりうる 3,1,2,4(レコード2) → 1,2,4(レコード3) シンプルな尺取り法では行けなさそうだ… --- 左端を決め打つ？ 左端を決め打つと、レコード数kになる長さは区間に入る → 区間が分かれば寄与も分かる 次の自分より大きい値を計算しておく → ダブリングで、k個先とk+1個先を求める あとは算数をやれば終わり？ --- 非連続も可なのを誤読していた… X,x が並んでいる時、Xを含むk の物は必ず、X,x を含むkの物と対になって存在できる。 → X を消せる？ 消していくと、単調増加だけになる？ 解けました # D 長さnの数列 b,c がある A[i][j] = b[i] ^ c[j] のとき、Aの行列式を求めよ --- b_i = b_j もしくは c_i = c_j となる i, j があれば線形従属なので0 a + b = (a ^ b) * 2 + a & b => a ^ b = (a + b - a & b) / 2 全部の2倍して最後に $2^(n^2)$ で割ればいいかな 列1のi行目 a_i + b1 - a_i & b1 列2のi行目 a_i + b2 - a_i & b2 ↓ 列1 - 列2 b1 - b2 - (a_i & b1 - a_i & b2) = !a_i & b1 - !a_i & b2 多重線形性を使いたい気がするけど，単に分解しようとするとすごいことになる 具体的には多重線形性でビットごとに分けると 60^n 個の行列ができる ~~ただ，全部 0 の行が多いかも？←多くない例が作れます~~ そうじゃなくて，b_i, b_j の k ビット目が両方同じ数ならゼロになる 3ビットで考えると b = 010 101 c = 100 001 110 011 001 100 ``` [[0 1] [1 0]] * 1, [[0 1] [0 0]] * 2, [[0 1] [0 1]] * 4 [[1 1] [1 0]]* 2, [[1 1] [0 0]] * 4, [[1 1] [0 1]] * 8 [[1 0] [1 0]] * 2, [[1 0] [0 0]] * 8, [[1 0] [0 1]] * 16 -1, 0, 0 -2, 0, 8 0, 0, 16 ``` ここで，ある i, j について b_i の k_i ビット目と b_j の k_j ビット目が同じならそれは計算しなくていい すべてのペアについて異なるやつのみ計算する←それだと n = 2 以外 0 になるはずだけどなりませんが？ 当然で，k_i != k_j だと c_l の k_i ビット目と k_j ビット目が違う可能性がある b = 001 010 011 100 c = 001 010 011 100 000 011 010 101 011 000 001 110 010 001 000 111 101 110 111 000 各ビットにつき 0, 1 の2つしか使えないはずなので，n > 120 なら 0 では？ # E ソートされた数列aがある i < j < p < q で a[i]a[q] = a[j]a[p] となる4ペアを1つ見つけよ (チェッカーは与えられる) --- a[i] / a[j] = a[p] / a[q] a[j] / a[i] = a[q] / a[p] a[j] / a[i] = x/y とすると(x,y は互いに素) a[q] は xの倍数 a[p] は y の倍数 a[i] と a[p] は互いに素ではない 多分切り捨てでチェックするよという話な気がするのでそう考える 要素数が多いとほとんど1倍にならないと 10^18 に収まらないですよね？そうですね？という気持ちになるので解けました # F # G n頂点の edge-weightedな 木Tがある d[u][v] = u,v 間 のsimple pathの重みの総和 完全グラフG を考える。u,v 間の重みは d[u][v] である。 k = 1,2, ... , floor(n/2) に関して、サイズkのマッチングの重みの総和の最大値を求めよ # H # I n 要素の順列が与えられる k 回目の操作では，prefix もしくは suffix の k 要素を昇順に並べられる 最小何回のどのような操作列で全部をソートできるか --- 1回のsortで動かせる要素数が全体の 1/3 を超えたら、必ず 残り3回でsortできる 同じ方を連続で選ぶメリットは…？ かなり無さそう 少なくとも、2回やる内の前の方は逆に移動してもいいよね…？ 逆に移動したとき、反対側に嬉しくないことが起こらないのならば、完全交互確定 起こらなそうなんだよな… 完全交互だとして、どうやってシミュレーションするか？ シミュレーションするのは、kが半分を超えてからでok それ以下は算数で行けるので 触れた後は、逆側に行きたい要素のみが動く 各要素は2回しか触れられないため、うまくやれば O(n) で行けるはずだが… 2つのsetを管理すれば行ける？ 最後にprefixクエリで触れられた要素 最後にsuffixクエリで触れられた要素 クエリは、逆のsetから奪い取れば処理できる 前後半両方が順番の数字で並んだら ok ```cpp= cin.tie(nullptr); ios_base::sync_with_stdio(false); ``` # J 1～mの数字で構築された、全ての長さnの数列を考える 各数列に関して、「連続部分列かつ回文」の個数を数える 個数が最小のやつ以外をすべて取り除く 残った数列の集合のうち、辞書順k番目の物を答えよ --- 長さ1の回文は、どうせあるので無視 回文が無い条件は、 2個隣以内に、同じ数が存在しない つまり、m >= 3 ならば回文は完全に消せる つまり… 3文字目以降は、m-2 個の選択肢がある dpでなんやかんやすれば解けるはず 残り k 文字の時、 ``` [0, 1, 0, 0] 6 [1, 1, 0, 0] 6 [0, 0, 1, 0] 6 [1, 0, 1, 0] 6 [0, 1, 1, 0] 6 [1, 0, 0, 1] 6 [0, 1, 0, 1] 6 [1, 1, 0, 1] 6 [0, 0, 1, 1] 6 [1, 0, 1, 1] 6 ``` ``` [1, 1, 0, 1, 0, 0] 10 [1, 0, 1, 1, 0, 0] 10 [1, 1, 0, 0, 1, 0] 10 [0, 1, 1, 0, 1, 0] 10 [1, 0, 0, 1, 1, 0] 10 [0, 1, 0, 1, 1, 0] 10 [1, 0, 1, 0, 0, 1] 10 [0, 1, 1, 0, 0, 1] 10 [1, 0, 0, 1, 0, 1] 10 [0, 0, 1, 1, 0, 1] 10 [0, 1, 0, 0, 1, 1] 10 [0, 0, 1, 0, 1, 1] 10 ``` ``` [0, 1, 1, 0, 1, 0, 0] 12 [0, 1, 0, 1, 1, 0, 0] 12 [0, 1, 1, 0, 0, 1, 0] 12 [0, 0, 1, 1, 0, 1, 0] 12 [0, 1, 0, 0, 1, 1, 0] 12 [0, 0, 1, 0, 1, 1, 0] 12 [1, 1, 0, 1, 0, 0, 1] 12 [1, 0, 1, 1, 0, 0, 1] 12 [1, 1, 0, 0, 1, 0, 1] 12 [1, 0, 0, 1, 1, 0, 1] 12 [1, 0, 1, 0, 0, 1, 1] 12 [1, 0, 0, 1, 0, 1, 1] 12 ``` ``` [0, 1, 0, 0, 1, 1, 0, 1, 0, 0] 18 [1, 1, 0, 0, 1, 0, 1, 1, 0, 0] 18 [0, 0, 1, 0, 1, 1, 0, 0, 1, 0] 18 [1, 0, 1, 0, 0, 1, 1, 0, 1, 0] 18 [0, 1, 1, 0, 1, 0, 0, 1, 1, 0] 18 [0, 1, 1, 0, 0, 1, 0, 1, 1, 0] 18 [1, 0, 0, 1, 1, 0, 1, 0, 0, 1] 18 [1, 0, 0, 1, 0, 1, 1, 0, 0, 1] 18 [0, 1, 0, 1, 1, 0, 0, 1, 0, 1] 18 [1, 1, 0, 1, 0, 0, 1, 1, 0, 1] 18 [0, 0, 1, 1, 0, 1, 0, 0, 1, 1] 18 [1, 0, 1, 1, 0, 0, 1, 0, 1, 1] 18 ``` ``` [0, 0, 1, 0, 1, 1, 0, 0, 1, 0] 18 [0, 0, 1, 1, 0, 1, 0, 0, 1, 1] 18 [0, 1, 0, 0, 1, 1, 0, 1, 0, 0] 18 [0, 1, 0, 1, 1, 0, 0, 1, 0, 1] 18 [0, 1, 1, 0, 0, 1, 0, 1, 1, 0] 18 [0, 1, 1, 0, 1, 0, 0, 1, 1, 0] 18 [1, 0, 0, 1, 0, 1, 1, 0, 0, 1] 18 [1, 0, 0, 1, 1, 0, 1, 0, 0, 1] 18 [1, 0, 1, 0, 0, 1, 1, 0, 1, 0] 18 ``` ``` [0, 0, 1, 0, 1, 1, 0, 0, 1, 0] 18 [0, 0, 1, 1, 0, 1, 0, 0, 1, 1] 18 [0, 1, 0, 0, 1, 1, 0, 1, 0, 0] 18 [0, 1, 0, 1, 1, 0, 0, 1, 0, 1] 18 [0, 1, 1, 0, 0, 1, 0, 1, 1, 0] 18 [0, 1, 1, 0, 1, 0, 0, 1, 1, 0] 18 [1, 0, 0, 1, 0, 1, 1, 0, 0, 1] 18 [1, 0, 0, 1, 1, 0, 1, 0, 0, 1] 18 [1, 0, 1, 0, 0, 1, 1, 0, 1, 0] 18 [1, 0, 1, 1, 0, 0, 1, 0, 1, 1] 18 [1, 1, 0, 0, 1, 0, 1, 1, 0, 0] 18 [1, 1, 0, 1, 0, 0, 1, 1, 0, 1] 18 ``` ``` [0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1] 22 [0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1] 22 [0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1] 22 [0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0] 22 [0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1] 22 [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0] 22 [1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1] 22 [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0] 22 [1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1] 22 [1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0] 22 [1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0] 22 [1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0] 22 ``` # K 4頂点からなる完全部分グラフはいくつありますか？ n, m <= 10^5 anti-K4 version https://codeforces.com/blog/entry/97762?#comment-866645 # L