ferinの競プロ帳

競プロについてのメモ

チーム練習 (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を持ちながら順番に参照していけばよい。

Codeforces Round #641 (Div. 1) A. Orac and LCM

問題ページ

gcdを求めたいので素因数ごとに独立に考えて、最後に掛け合わせても問題ない。

例えば数列が (2^0, 2^1, 2^2, 2^3) であったとする。このときのlcmの集合は

  • \text{lcm}(2^0, 2^1) = 2^{\max(0, 1)}
  • \text{lcm}(2^0, 2^2) = 2^{\max(0, 2)}
  • \text{lcm}(2^0, 2^3) = 2^{\max(0, 3)}
  • \text{lcm}(2^1, 2^2) = 2^{\max(1, 2)}
  • \text{lcm}(2^2, 2^3) = 2^{\max(2, 3)}

となる。このときの \gcd2^{\max(0, 1)} となる。このように指数が小さい方から2番目の値のものが \gcd の指数となる。

あとは素因数ごとに指数が小さい方から2番目のものを列挙していく。指数が0のものもすべて列挙すると O(n \times (素数の個数)) かかってしまうので、各数の素因数のみを参照するように工夫する。

\text{num} \lbrack i \rbrack  = (素因数iを約数にもつ数の個数)\text{mi} \lbrack i \rbrack  = (素因数iの指数の最小)\text{mi2} \lbrack i \rbrack  = (素因数iの指数の小さい方から2番目) とした配列を持つ。数 A_i素因数分解を行い、現れた素因数についてこれらの配列の更新を行う。これは O(\sqrt{A_i}) でできる。

配列を構成した後、\text{num} \lbrack i \rbrack  = n であれば i^{\text{mi2} \lbrack i \rbrack } を答えに掛け、\text{num} \lbrack i \rbrack  = n-1 であれば i^{\text{mi} \lbrack i \rbrack } (最小の指数は0なので)を答えに掛ける。\text{num} \lbrack i \rbrack  \leq n-2 のときは2番目から小さい方の指数は0なので何もしなくても問題ない。

\text{num} \lbrack i \rbrack  = n-1 のときに i^{\text{mi2} \lbrack i \rbrack } を掛けてシステス落とした…

ダブリング

この間のABCで話題になってたのでダブリングについてちょっと考えたことのメモ
コードは適当なので雰囲気です

x:=f(x,y) を繰り返す

関数 f: T \times T \to T が存在
x,y \in T について x := f(x,y)K 回実行
これは O((fの計算量) \times \log K) で計算可能

繰り返し二乗法などが具体例としてあげられる

template<class T, class F>  
T binpow(T y, ll k, F f, T x) {  
    T ret = x, p = y;  
    while(k > 0) {  
        if(k%2 == 0) {p = f(p, p); k /= 2;}  
        else {ret = f(ret, p); k--;}  
    }  
    return ret;  
};  
  
int main() {  
    // 10^100 mod 1e9+7  
    binpow(10, 100, [](ll a, ll b){ return a*b%1000000007; }, 1);  
}  

行列累乗や置換の積を繰り返すような処理も f, x を変更することで対応可能

int main() {  
    // 行列累乗  
    {  
        const ll n = 3; // 行列の次数  
        using mind = modint<1000000007>;  // modintの実装は省略します  
        auto mul = [&](vector<vector<mint>> a, vector<vector<mint>> b) {  
            vector<vector<mint>> c(n, vector<mint>(n));  
            REP(i, n) REP(j, n) REP(k, n) c[i][j] += a[i][k] * b[k][j];  
            return c;  
        };  
        vector<vector<mint>> a = {  
            {1, 2, 3},  
            {4, 5, 6},  
            {7, 8, 9}  
        }, d = {   // 単位行列  
            {1, 0, 0},  
            {0, 1, 0},  
            {0, 0, 1}  
        };  
        // a^10  
        binpow(a, 10, mul, d);  
    }  
  
    // 置換の積  
    {  
        const ll n = 3; // 置換の要素数  
        auto mul = [](vector<ll> a, vector<ll> b) {  
            vector<ll> ret(a.size());  
            REP(i, a.size()) ret[i] = b[a[i]];  
            return ret;  
        };  
        // (0, 2, 1) を 10回適用  
        binpow({0, 2, 1}, 10, mul, {0, 1, 2});  
    }  
}  

このあいだのABCのD - Teleporterを置換の積と思うと、これで解ける
Submission #13117116 - AtCoder Beginner Contest 167

例題1
例題2

x:=f(x) を繰り返す

x \in T に関数 f:T \to TK 回適用したときの値を計算する

N=|T| と表す
f(x)\ (x \in T)O(g) で計算可能なとき、前計算が O(gN + N \log N) で可能
各クエリ O(\log K) で計算可能

前計算

前計算では \text{next} \lbrack k \rbrack  \lbrack i \rbrack  = (i番目の要素の2^k個次の要素) を計算する
まず、\text{next} \lbrack 0 \rbrack  \lbrack i \rbrack  = g(x_i) で初期化する。k \gt =1 に関しては \text{next} \lbrack k \rbrack  \lbrack i \rbrack  = \text{next} \lbrack k-1 \rbrack  \lbrack \text{next} \lbrack k-1 \rbrack  \lbrack i \rbrack  \rbrack と計算可能

クエリ

x \in T に関数 f:T \to TK 回適用したい
もし K&1<<i であったら x = \text{next} \lbrack i \rbrack  \lbrack x \rbrack として更新する

実装例

template<ll LOG=60>  
struct doubling {  
    // nxt[i][j] = (j番目の要素に関数fを2^i回適用した要素は何番目の要素か)  
    vector<vector<ll>> nxt;   
    doubling(vector<ll> nxt0) : nxt(LOG, vector<ll>(nxt0.size())) {  
        REP(i, nxt0.size()) nxt[0][i] = nxt0[i];  
        FOR(k, 1, LOG) REP(j, nxt0.size()) nxt[k][j] = nxt[k-1][nxt[k-1][j]];  
    }  
    // x番目の要素に関数fをk回適用した要素は何番目の要素か?  
    ll query(ll x, ll k) {  
        for(ll i=LOG-1; i>=0; --i) if(k&1LL<<i) x = nxt[i][x];  
        return x;  
    }  
};  

この間のABCのD - Teleporterの場合、f(x) = a \lbrack x \rbrack とすればよい
Submission #13117497 - AtCoder Beginner Contest 167

合計・最小などの求解

前計算のタイミングで 2^k 回適用したところまでの合計、最小を求めておけばよい

試しに合計で考える
\text{sum} \lbrack i \rbrack  \lbrack j \rbrack  = (j \lbrack 0, 2^i) 回適用した値の合計)
\text{sum} \lbrack i \rbrack  \lbrack j \rbrack (j \lbrack 0,2^i))(j \lbrack 0,2^{i-1}) 回適用) + (\text{next} \lbrack i-1 \rbrack  \lbrack j \rbrack  \lbrack 0, 2^{i-1}) 回適用)
より小さい i の情報を用いて計算できるので、i が小さい方から計算していける

二分探索

単調性があるなら二分探索できる

x_i \leq x_{i+1}, x \leq f(x) みたいな単調性があるとする
x から y 以上に移動するのに必要な関数適用の回数の最小
\text{next} \lbrack k \rbrack  \lbrack a \rbrack  \leq b が成り立つなら ret += 2^k, a := \text{next} \lbrack k \rbrack  \lbrack a \rbrack k が大きい方から実行すればよい

(実装例) Submission #13117640 - AtCoder Regular Contest 060

ダブリングで木のLCAを求めるのも同じ感じ

雑感
なんか一般化できないかなあと思って考えてたけど f(x), f(x,y) のやつ同じように扱うの難しそう
f(x,y) の方だと n が大きくてもいける
f(x) の方だとクエリに高速に答えられる