ferinの競プロ帳

競プロについてのメモ

2020 ICPC Shanghai Site E. The Journey of Geor Autumn

問題ページ

dp[長さiの数列] = 何通り とDPをする。

1をi番目に置く

  • [1,i) は自由においてok → P(n-1, i-1)
  • (i,n] は dp[n-i] 通り

 \displaystyle dp \lbrack i \rbrack  = \sum_{j=1}^{\min(i,k)} P(i-1,j-1) * dp \lbrack i-j \rbrack  = (i-1)! \sum_{j=1}^{\min(i,k)} dp \lbrack i-j \rbrack  / (i-j)!

 dp \lbrack i-j \rbrack / (i-j)! の累積和をもちつつ更新すれば  O(n)

2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

チーム練でやった https://codeforces.com/gym/102433

BCLMは気づいたら通ってた

E

個数+1 を種類ごとに掛け合わせる

D

減らすのは/2で増やすのは+1しかないので適当にシミュレーション

I

同時に入れられないやつに辺をはると最大独立集合
swapのparityを考えると二部グラフなので求まる

A

全方位木DP
\sum_{u} a \lbrack u \rbrack  \times (u-vパスの重み) + a \lbrack v \rbrack  \times (u-vパスの重み) を求めたい
1項目は \sum_{\text{辺} e} (部分木内の頂点重み)*(辺重み)
2項目は a \lbrack v \rbrack  \times \sum_{\text{辺} e} (部分木の頂点数)*(辺重み)

1項目は dp[v] = sum(dp[c] + (辺v-cの重み)*(部分木cの頂点重み))
2項目は num[v] = sum(num[c] + (辺v-cの重み)*(部分木cの頂点数))

あとはこれを全方位にする

K

セグ木もって頑張る
キャッシュの方は最後にロードされた (i,p) の列を覚えておく
メモリの方は m 個の区間加算ができるセグ木をもっておく

クエリ2がきたタイミングでキャッシュの p 番目の情報をセグ木から取る
ただし、キャッシュに書き込んだあとにメモリを+1していると書き込んだ後の更新分まで反映してしまってまずい

クエリ2で答える場所について、何番目のクエリまでの情報で答えればよいか?をクエリ先読みで求めておく
クエリ1が来るたびその範囲にクエリ番号を更新しておいて、クエリ2がきたときにその位置を記憶しておくとできる
この情報を元にクエリ2の答えを求める

添字間違えて実装間に合わなくて涙

G

二次元平面で縦・横方向に移動する物体が衝突 → 直線y=-x+200000上に同時に存在
あるパルスがy=-x+200000に存在するか?を管理しつつ時系列順にシミュレートする
直線に乗るタイミングは t[i]+200000-a[i] で直線から消えるタイミングは t[i]+m[i]+200000-a[i] なのでこのタイミングで直線の状態が変わる

直線から消える方・乗る方をそれぞれまとめて処理しないと変なことになるので注意

チーム練習 (05/27)

2019 ICPC Asia-East Continent Final をやった

A は気づいたら通ってた

M

i^k = j となるような i,j の組はあまりない
2,4,8,\ldots3,9,27,\ldots のように素数のべき乗に分割する
各集合の要素数O(\log n) 個でbit全探索の要領で全部見てもok

E

universeなグラフ: 頂点1とn以外は次数が2で分岐しないグラフで、並列な同じ長さのパスの集合で構成される

このグラフの最大流は \sum_{path P} \min_{e \in P} (eの重み) となる
一つのパスに全て重みを移した場合、流量が最適となる
この最適な流量は \lfloor 流量の総和 / パスの長さ \rfloor となる
この最大流を達成するときに操作回数の最小化を行いたい

i 番目のパスに流れる流量が x_i となるようにする
+1する操作回数だけ数えたとしても、x_i の和が最適になるように定めているので、-1する操作の方の回数についてもつじつまが合う
i 番目のパスの操作回数は \sum_{w  \lt  x_i} x_i -(辺重みw) となるのでこの回数を最小化すればよい

この操作回数は x_i に対して大体等差数列のようになっている
x_i が辺重みを超えるタイミングでのみ公差が1増える
公差が小さいものから順にできるだけ採用する貪欲法を行えば操作回数の最小化ができる
この貪欲法はpriority_queueに公差などを挿入しておき、小さいものから順番に取っていけばよい

H

n/2 個以上の要素を取ろうと思うと、隣接する要素は距離2以下となっているものが大半を占める
したがって距離2以下の要素の公比のうち要素数n/4 以上のもののみが公比の候補となる
これによって公比の候補を限定することができる

あとは公比を固定したときの最大の部分列の長さをpolylog(n)で求めたい
これは \text{dp} \lbrack i \rbrack  = (iを最後に取ったときの部分列の長さの最大) とすればよい
遷移は \text{chmin}(\text{dp} \lbrack j \rbrack , dp \lbrack i \rbrack +1) (jv_j=v_i*rとなる最小のj) とすればよい

C

f(1)=g(1)=1 だと f^{\text{mod}}(n) = \epsilon(n) となるらしい
ただし、\epsilon(n)n=1 のときのみ1でそれ以外の場合0となる関数
証明できない

これを用いると g,k が与えられたとき f \equiv g^{k^{-1}}\ (\text{mod} M) となる
g^{k^{-1}} はダブリングで求められるので O(n\log n\log M) で答えがわかる

なんで検索なしでこれがこんな解かれてるんだ…

Codeforces Round #643 (Div. 2)

A

15:30
証明が全然できないけどみんなめっちゃ通していく
仕方がないのでK回普通に漸化式を計算して0が含まれたら終了にした
未証明

提出

B

30:41
全員どこかしらに入らないといけないんだと思って1ペナ
あと普通に実装が下手なので強い人のをあとで見る

提出

下のが一番簡単かなあ

sort(ALL(a));  
ll l = 0, ans = 0;  
REP(i, n) if(a[i] <= i+1-l) ++ans, l=i+1;  
cout << ans << endl;  

C(1回目)

x+y  \gt  z になる組を数えるのと同じ
z を固定 → x を大きくすると取れる y が1ずつ増えていく
等差数列の和なので算数するとサンプルすらあわない

D

1:01:20
解かれてるのでDに移動
明らかにYESをつくれるパターンとして 1 1 … 1 (残り) で残りがnより大きければ k=(残り)-1 とする

s < 2n のときを考える
1がいっぱい出てくる
どう頑張ってもNOのパターンをつくれない

未証明で投げた
提出

1 2 2 … 2 みたいなのを考えると n に対して s が最小でNOのパターン
これ以上2を分割しても s \leq 2n-1

C(2回目)

1:36:02
もうちょっとちゃんと整理する
z を固定して、x を変化させたときの取れる y の個数を考える

x が小さい → x が大きい に移動するにつれて、y の個数は以下のように変化する
0, 0, \ldots, 0, 1, 2, \ldots, c-b+1, c-b+1, \ldots, c-b+1
この列の x=a から x=b の部分の和を高速に求めたい

f(p) = (この列でp以下の部分)の和が求まればよい
1 がでてくる位置と c-b+1 がはじめて出てくる位置を計算する
3分割された区間のうちどこに p が存在するか?で場合分けして、「0の部分」「等差数列の部分」「c-b+1 の部分」それぞれを計算する

提出

z 固定じゃなくて x+y を固定すると簡単
\text{imos} \lbrack i \rbrack  = (x+y=iとなるようなx,yの組が何個あるか) を計算する
これは a \leq x \leq b について区間  \lbrack x+b, x+c \rbrack に+1すればできる
あとは各 x+y=i について i  \gt  z, c \leq z \leq d となるような区間の共通部分を求めて足せばよい

E

A+R  \lt  M だったらmoveをする必要はない、逆に A+R \geq M だったらmoveできる限りするべき

揃える高さ X を固定したときのコストを考える
X  \gt  h_i となる h_i について v_0 = \sum (X-h_i) の分ブロックを足す必要がある
X \geq h_i となる h_i について v_1 = \sum (h_i-X) の分ブロックを削る必要がある
\min(v_0, v_1) の分moveして、それでも揃ってない分をaddかremoveをする

問題は X の候補が多いことでどうにかして減らしたい
時間がなかったので X=h_i に限定できるのかと思って試すけどサンプルが通らない
|v_0-v_1| が小さいところが答えじゃね?と思って三分探索を書いたけど落ちる

冷静に考えて変なことしなくても X とコストについて凸性がありそうだしもっとシンプルっぽい
残り30秒なので終了です

三分探索の初期値のinfがでかくてオーバーフローしてたのが原因で1行直したら通った…
積がある場合は 10^9 以上の値がそこに入らないように気をつける!
提出
整理して書き直した提出

全体的に実装方針が悪かったり、誤読してたり、証明できなくて悩んでたりかなり微妙…

F

小さい方の素数を何個保持しているか?をクエリで特定する
大きい方の素数に関してはわからないが、誤差の条件から2個程度素数を見逃していたとしても問題がない

まず含んでいる素数の集合を特定する。これは 10^18 以下でできるだけ多くの素数をかけ合わせた数をクエリとして投げることで実現できる。次に含んでいる素数 p に対して、p^k \leq 10^9 となる最大のものをクエリとして投げることで、素数 p を何個含んでいるか特定することができる。

ここまでで紹介したクエリの投げ方で677以下の素数に関しては特定できた
これで誤差の条件に当てはまる答えを必ず出力できることを確認する

  • 特定した部分の約数の個数が1個
    677よりも大きい素数は高々3個しか掛け合わせられないので、特定していない部分は1個~8個のいずれかになる。4を出力しておけば絶対誤差の制約を満たす。
  • 特定した部分の約数の個数が2個
    同様に、特定していない部分は1個~8個なので9を出力する。
  • それ以外の場合
    特定した部分は4以上となる。このとき、特定しない部分は1個~4個のいずれかとなるので2倍した値を出力しておくと、相対誤差の制約を満たす。

以下のような流れで考察すると早いのかなあという想像

  • 小さい方の素数の特定に気づく
  • 素数の特定方法として効率のいいものが上のパターンであることに気づく
  • 前半・後半でクエリの個数の分配を考える
    10^9 以下の数は素因数を高々9個しか持たないので、クエリの後半パートは5個クエリを使えば足りる。前半は17個クエリを使える。
  • 特定できる素数の大きさから誤差の条件を満たす解を出力できることを確認する

チーム練習(05/13)

Dashboard - 2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019) - Codeforces をやった。

C,F,I は気づいたら通ってた
B,K はわからん

A

得点が同じ人ごとにまとめておいて、点数が変化した人の分だけ更新するようにシミュレーションすると通るらしい

D

まず v の値に関しては答えに何も関係がない。あるパス P={e_1, \ldots, e_k} の長さは  \displaystyle \sum_{i=1}^k (l_i/v+c) = \frac{1}{v}\sum_{i=1}^k (l_i+vc) なので結局定数を足したものと変わらない。以降では v=1 として考える。

c=\infty とすると、辺の本数を最小化したパスが最短となることがわかる。ようするに c を増やすと辺の本数が減少していくので、辺の本数と関連があることがわかる。

c=0 で辺の本数を k に固定したとき、最短となるパスを求める。\text{dist} \lbrack 辺の本数i \rbrack  \lbrack 頂点j \rbrack =(始点からの最短距離) とすると、\text{chmin}(\text{dist} \lbrack i+1 \rbrack  \lbrack to \rbrack , \text{dist} \lbrack i \rbrack  \lbrack j \rbrack ) という遷移で計算できる。

辺の本数が k 本のパスで c=x のときの最短路長は \text{dist} \lbrack k \rbrack  \lbrack n-1 \rbrack  + kx である。k 本の直線の中で最小になるような x \geq 0 が存在する場合、辺の本数が k のパスが最短になるような c が存在する。このような直線集合はconvex hull trickの要領で求めることができる。

あとは長さが k で最短となるようなパスに含まれる頂点を列挙し、答えから外す。残っている頂点集合を出力すれば良い。

E

時間 0 \leq t_5 \leq 30 を試せばよい
小数を100倍して整数に直すときに、ちゃんと誤差を考慮してepsを足さないといけなくて、a := (a+\text{eps}) \times 100 とするべき

G

あるモンスター i が出現 && 直前の出現するモンスターが j であるときの寄与をそれぞれ足していく

H

区間  \lbrack i,j \rbrack の斜度が g 以上である
\iff (h_j-h_i)/1000(j-i) \geq g/100
\iff h_j-10gj \geq h_i-10gi
i 番目の高さから 10gi を引いておくと判定ができる。

答えは小数になることもあるので、各 i について考えられるような最大の j を整数で求めたあとどこまで伸ばせるか?を求めればよい

J

増減の操作を行う回数を X に固定する。絶対値が X 未満の数については自由に符号が変更できる。逆に絶対値が X 以上の数については矛盾する部分は消去で対応する必要がある。X を固定したときの削除数を高速に求めることができれば解くことができる。

X 以上のみからなる数列で隣接していて、(距離が奇数 && 正負同じ) || (距離が偶数 && 正負違う) なら辺をつなぐとしたグラフを考える。このグラフで sum(連結成分の頂点数-1)=辺数 の分要素を消去する必要がある。

X を大きくして頂点 v が消える場合、今まで頂点 v に隣接していた辺を消して、v の左右の頂点に辺をつなぐべきならばつなぐ。辺数を管理できるので解けた。

Codeforces Round #641 (Div. 1) C. Orac and Game of Life

問題ページ

サンプル1,2のようにすべてのマスについて同じ色が隣接、もしくは異なる色と隣接しているような状況のときは明らか。そうではないケースについて、とりあえず実験してみる。

01   01   00  
10 → 11 → 00  
00   11   00  

同じ色が隣接しているマスが一つ以上存在した場合、同じ色が連結なマスがどんどん増えていくので、明らかなケースに行き着くまでのiteration数は O(H+W) で抑えられる。各マスについて色変化をはじめるiterationがいつなのかを求めたい。

21  
10  
00  

最初から同じ色が隣接している場合は0、そのマスに隣接している場合は1、さらに隣接している場合は2 …となっていることがわかる。0のマスからスタートする多点スタートBFSによって、各マスの色変化を始めるiterationが求められる。

Codeforces Round #641 (Div. 1) B. Orac and Medians

問題ページ

k が2つ連続して並んでいる場合、k\ k\ x に操作を適用すればすべて k にできるので k\ k の並びをつくれるならば 'yes' となる。また k\ k以上 と並んでいる場合、操作を適用すれば k\ k の並びをつくれるのでこの場合も 'yes' となる。

あとは k以上 の数を k の隣に持ってくることができるか?の判定を行いたい。先程の場合と同様に考えると k以上 が隣接していれば k以上 を k の隣に持ってこれる。ある区間に操作を行ったときに k以上 の数が中央値になるならば、k以上 の隣接はつくれる。

あとは k以上 が過半数を占めるような区間が存在しているか?を解ければよい。k以上 を+1、k未満 を-1に置き換えた数列を考えると、総和が1以上である区間が存在することと同値である。あとは zero-sum range と同じで、累積和を取ったあと、累積minを持ちながら順番に参照していけばよい。