ICPC Training Camp 2023 Day2

# ICPC Training Camp 2023 Day2 # A # B n 個の問題が最初スコア a_i を持っています m 人がそれぞれ v 問選び，それらのスコアを１ずつ上げますスコアの上位 p 問がコンテストに使われます，同点の場合は任意の順に並べられます何通りの問題セットができる可能性があるでしょう (すべての p についての答えの和) # C 2^m (m <= 30) 要素からなるゼロ配列が与えられます． i = 1, ..., n について次の操作をします・p' = (p_i + x) mod 2^m, q' = (q_i + x) mod 2^m ・l = min(p', q'), r = max(p', q') ・j = l, l + 1, ..., r について，a_j += i したあとに x を a_j 増やす最終的な x mod 2^30 の値を求める # D classical DP n x n のチェス盤について，上から i 行目は左から a_i マスだけ残っていますまた， a_1 <= a_2 <= ... <= a_n なので階段状になっていますすべてのマスをルークによってカバーするのに必要なルークの個数と，その個数でカバーするルークの配置の種類数を求めなさいカバーされているマスとは，あるルークによって一手で到達可能なマスのことを言います n <= 5000 https://atcoder.jp/contests/agc041/tasks/agc041_f?lang=ja # E classical FFT D と同じ設定で， n <= 2^17 # F (0, 0, 0) と (255, 255, 255) を対角とする立方体があります最初，(0, 0, 0) に点 p があります立方体の頂点と秒数 d を指定すると，p はその頂点に向かって毎秒 1 の速さで向かっていき，到着するか d 秒経過した時点で停止します．与えられた点 (r, g, b) に１０回以下の操作で到着する操作列を出力してください --- 任意の (x, y, 0) に到達させることはできるはず → (a, a, 0) に行ったあと， (255, 0, 0) か (0, 255, 0) のどっちかと (x, y, 0) の交点になっていればいいのでそれはできる → そしたら，z > 255/2 の一部の領域以外には行くことができる → (x, y, z) のどれかが零の面を最初に使えばうまく行きそう平面と直線の交点を求められる必要がある # G 無向グラフ G = (V, E) について，頂点集合 S は，任意の頂点が S もしくは S の近傍に含まれている時支配集合と呼ぶグラフ G の頂点は，高々 2 つの葉と隣接しているという性質を持つつぎの頂点集合 S を求めなさい・S は G の支配集合・V \ S は G の支配集合・S のサイズは floor(|V| / 2) # H 2n 個の異なる点が平面上にあって i 番目の点の座標は (x_i, y_i) です x座標もしくはy座標が一致してるペアはフレンドリーですフレンドリーなペアの数が最大になるように n 個のペアを作ってください --- x座標とy座標のペアに辺を貼った時，パスの長さ / 2 がフレンドリーペアの数になるので最大化？結局貪欲にやったとして奇数をどう押し付けていくかみたいな話になる，絶対有名問題っぽいんですが... # I H と同じ設定で，最小化してください # J n 個のトピックがあり，i 個目のトピックは a_i 分の勉強で学習できるまた，b_i 個のトピックを学習していれば自信が持てる t 分勉強時間がある時，自信があるトピックの個数を最大化してください # K $n$ 個の街が直線状に並んでいて，街 i と i+1 は距離1 $k$ 人の友達がいて，それぞれが a_i に住んでる時は $\sum d(u, a_i)$ が最小になる街 u に集まる同じ値になるときは番号が最小のもの $n^k$ 通りの居住地の組み合わせで，集まる街の番号の和を求めなさい --- 適当に固定してあげれば良さそう u に集まる時，u に一人と $[1, u]$ に floor((k-1)/2) 人，$[u, n]$ に ceil((k-1)/2) 人いるということで ~~人を区別するけど同じ箱に入ってる人同士は区別しない数え方を忘れました~~ n, k <= 10^6 h = k / 2 とする i より左に h 人いる場合と，i 含めてそれより左に h - 1 人しかいない場合を引けばいいと思う ~~~ ※ここはいろいろ間違ってます k個ランダム配置するとき、左からx番目の人が、左からi番目の街にいる確率が分かれば解ける x番目の人が、iより左に居る確率 = p(x,i) とするこれは、 $ {i/n}^x \times {(n-i)/n}^{k-x} \times {kCx} $ かな p(x,i) - p(x,i-1) を計算すれば終わり解けたかな？おかしいな iより左に、ちょうどx人いる確率 - iより左にちょうどx人いるが、iには誰もいない確率が求めるものかな違うな ~~~ q(x,i) = iより左にx人以上いる確率とすると q(x,i) - q(x,i-1) でいいか p(x,i) = iより左に、ちょうどx人いる確率とすると q(x,i) = p(x,i) + p(x+1,i) + p(x+2,i) ... + p(k,i) p(y,i) = pow( i/n , y ) × pow( (n-i)/n , k-y ) × nCr(k,y) うわ～　なんか2項定理になりそうな気しかしない q(k/2, 1) * 1 (q(k/2, 2) - q(k/2, 1)) * 2 (q(k/2, 3) - q(k/2, 2)) * 3 ... (q(k/2, n) - q(k/2, n - 1)) * n ↓ n * q(k/2, n) - q(k/2, n - 1) - q(k/2, n -2) - ... - q(k/2, 2) - q(k/2, 1) 仕切りの入れ方の方を考える？人人人人x人人人人 x人目が左からi番目の集合に居るためには… xより左に、i-1個の仕切りがあり、xより右に残りの仕切りが入る必要があるこれだと、サイコロを仕切りの回数分振った時、ちょうど (i-1) 回 xより左が出て、残りは右の確率に等しい解けた？全ての入れ方は、容易に計算できる