くるのプログラミング記録

プログラミングの感想とか解説とか。

OUPC2020 C. Symmetric NBase Number 解説

[謝罪]
問題文のサンプルの表現が間違っていました。すみません。
正しくは f(41,-4) = (1, 2, 3) です。






{\displaystyle a}の{\displaystyle b}進数表現、{\displaystyle -b}進数表現について考えると、数列{\displaystyle c=(c_0, \cdots ,c_N)}と数列{\displaystyle d=(d_0,\cdots,d_M)}を用いて下記のように書けます。

{\displaystyle a = c_0 + c_1*b + c_2*b^2 + c_3*b^3 + ...... + c_N*b^N}
{\displaystyle a = d_0 - d_1*b + d_2*b^2 - d_3*b^3 + ...... + (-1)^M*d_M*b^M}

ただし{\displaystyle c_i,d_i}はいずれも{\displaystyle b}より小さい非負整数
{\displaystyle f(a,b)}と{\displaystyle f(a,-b)}が一致するという条件は、数列{\displaystyle c}と{\displaystyle d}が一致するということと同値です。 このとき{\displaystyle N=M}が必要となり、下記の式が成り立ちます。

{\displaystyle c_0=d_0}
{\displaystyle c_1=d_1}
{\displaystyle \vdots }
{\displaystyle c_N=d_N}
ここで、どちらの数も{\displaystyle a}であるので

{\displaystyle c_0 + c_1*b + c_2*b^2 + c_3*b^3 + ...... + c_N*b^N = d_0 - d_1*b + d_2*b^2 - d_3*b^3 + ...... + (-1)^N*d_N*b^N}
{\displaystyle \Leftrightarrow}
{\displaystyle c_0 + c_1*b + c_2*b^2 + c_3*b^3 + ...... + c_N*b^N = c_0 - c_1*b + c_2*b^2 - c_3*b^3 + ...... + (-1)^N*c_N*b^N}

すなわち下記の条件が成り立ちます
{\displaystyle c_1*b + c_3*b^3 + ...... + c_{2L-1}*b^{(2L-1)} = 0}
ここで{\displaystyle 2L-1}は{\displaystyle N}以下の最大の奇正数です。

上記式が恒等的に成り立つことと、{\displaystyle b > 1}であることを考慮すると

{\displaystyle c_{2i-1} = 0}
が題意を満たす条件です。

すなわち{\displaystyle b}進数変換した際の、奇数桁が{\displaystyle 0}であるような{\displaystyle (a,b)}の組の数え上げに言い換えることが出来ます。
これは{\displaystyle b}を決め打ちし、そのあとは桁dpを行うことで求めることが出来ます。
よって計算量{\displaystyle O(B \log A)}でこの問題を解くことが出来ました。

OUPC β A,B,D 解説

OUPC β　解説

Grundy Number (200)

  • writer: ningenMe
  • URL

https://www.hackerrank.com/contests/oupc-beta/challenges/grundy-number

  • 解説:

与えられる入力をsetや配列に格納し、数字の既出管理を行いましょう。
数列{\displaystyle A}の最大値を{\displaystyle A_{max}}とすると{\displaystyle O(N+A_{max})}で解くことが出来ます。
writer解

#include <iostream>
#include <vector>

using namespace std;

int main(void) {
    int N; cin >> N;
    vector<int> C(101,1);
    for(int i = 0; i < N; ++i) {
        int A; cin >> A;
        C[A] = 0;
    }
    for(int i = 0; i <= 100; ++i) {
        if(C[i]) {
            cout << i << endl;
            break;
        }
    }    
    return 0;
}

Doubling Step (300)

  • writer: ningenMe
  • URL

https://www.hackerrank.com/contests/oupc-beta/challenges/doubling-step

  • 解説:

dpで解きましょう。{\displaystyle dp_{i}: i}番目の球に乗るような場合の数。
1つの球から移動できる選択肢は高々{\displaystyle O(\log(N))}個なので、全体として{\displaystyle O(N\log(N))}で解くことが出来ます。

writer解

#include <iostream>
#include <vector>

using namespace std;
constexpr long long MOD = 998244353;

int main(void) {
    long long N; cin >> N;
    vector<long long> dp(N+1,0);
    dp[1] = 1;
    for(int i = 1; i < N; ++i) {
        for(int j = 0; (i + (1 << j)) <= N; j++) {
            (dp[i + (1 << j)] += dp[i]) %= MOD;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

Product Grid (500)

  • writer: ningenMe
  • URL

https://www.hackerrank.com/contests/oupc-beta/challenges/product-grid

  • 解説:

まず定数{\displaystyle K}の値は、入力で与えられる{\displaystyle A_{1,j}\ (1 \leq j \leq W)}の最小公倍数になります。
ここで{\displaystyle K}はとても大きくなるため、実装上では{\displaystyle K}を素因数で管理します。
{\displaystyle K}の値が分かったので、各列において{\displaystyle A_{1,j}\ (1 \leq j \leq W)}以外の残りの数字の積が{\displaystyle K/A_{1,j}}になれば条件を満たします。
これは{\displaystyle j}番目の列を考えたとき、{\displaystyle K/A_{1,j}}の各素因数を{\displaystyle A_{2,j}...A_{H,j}}のいずれかに割り当てることをすればよいです。
よって割り当てる素因数の数を{\displaystyle r}個としたとき、重複組み合わせを考えると二項係数{\displaystyle Comb(H-1+r - 1,r)}で場合の数を数えることができます。
よって各列においてそれぞれ独立に計算することで求める場合の数を得ることが出来ました。


しかし{\displaystyle A_{max}=100000}以下の素数の数は{\displaystyle L=9592}個であるため、上記の解法では最悪計算量{\displaystyle O(WL)}となりTLEします。
ここで各列において、1行目の値{\displaystyle A_{1,j}\ (1 \leq j \leq W)}に含まれる素因数が{\displaystyle K}に含まれる素因数に比べて比較的少ないことを利用します。
{\displaystyle 2*3*5*7*11*13 = 30030 < A_{max} < 510510 = 2*3*5*7*11*13*17}であることを考えると、{\displaystyle A_{1,j}\ (1 \leq j \leq W)}に含まれる素因数の種類の個数は高々6個です。
なので各列において{\displaystyle A_{1,j}=1}と仮定して{\displaystyle K/A_{1,j} = K}の各素因数を{\displaystyle A_{2,k}...A_{H,k}}に振り分けます。この値は全列で同じ値なので{\displaystyle O(L+W)}で計算できます。
その後各列において、実際の{\displaystyle A_{1,j}}の値の差分だけ計算すればよく、これは{\displaystyle O(W)}で計算出来ます。
よって、全体として{\displaystyle O(Wsqrt(A_{max})+H+ L)}で解くことが出来ます。

writer解

#include <iostream>
#include <vector>
#include <map>

using namespace std;
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
constexpr long long MOD = 998244353;

//Prime Factorization O(sqrt(N))
vector<pair<long long,long long>> PrimeFactorization(long long N) {
    vector<pair<long long,long long>> ret;
    for (long long i = 2,M = N; i*i <= M; ++i) {
        if (N%i == 0) {
            long long cnt = 0;
            while (N%i == 0) N /= i, cnt++;
            ret.push_back({i,cnt});
        }
    }
    if (N != 1) ret.push_back({N,1});
    return ret;
}

//Combination Mod
class CombinationMod {
public:
	vector<long long> fac,finv,inv;
	long long mod;

	CombinationMod(int N,long long mod) : fac(N + 1), finv(N + 1), inv(N + 1), mod(mod) {
		fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
		for (int i = 2; i <= N; ++i) {
			fac[i] = fac[i - 1] * i % mod;
			inv[i] = mod - inv[mod%i] * (mod / i) % mod;
			finv[i] = finv[i - 1] * inv[i] % mod;
		}
	}
	
	long long num(int n, int k) {
		return ((n < 0 || k < 0 || n < k) ? 0 : fac[n] * (finv[k] * finv[n - k] % mod) % mod);
	}
};

//Pow_Mod O(log(n))
long long PowMod(long long x, long long n, long long mod) {
    long long res = 1;
    for (; n > 0; n >>= 1, (x *= x) %= mod) if (n & 1) (res *= x) %= mod;
    return res;
}

//Inv_Mod O(log(mod))
long long InvMod(long long x, long long mod){
	return PowMod(x,mod-2,mod); 
}

//O(WsqrtA + H + LlogL)解法
int main(void) {
    long long H,W; cin >> H >> W;
    vector<long long> A(W);
    for(int i = 0; i < W; ++i) {
        cin >> A[i];
    }

    //素因数を列挙　O(W*sqrt(A))
    vector<vector<pair<long long,long long>>> P(W);
    for(int i = 0; i < W; ++i) {
        P[i] = PrimeFactorization(A[i]);
    }
    
    //L<=(Kに含まれる素数の個数の最大値)<=(maxA以下の素数の個数)=9592
    //最小のKの素因数分解を構築　O(W + LlogL) 
    map<long long, long long> K;
    for(int i = 0; i < W; ++i) {
        for(auto e: P[i]){
            long long p = e.first;
            long long c = e.second;
            chmax(K[p],c);
        }
    }

    //二項係数 O(H) 2^16 = 65536 < maxA < 131072 = 2^17 < 2^20
    CombinationMod CM(H+20,MOD);
    
    //A=1のときの数え上げを前計算 O(LlogL)
    long long cnt = 1;
    for(auto e:K) {
        long long N = e.second;
        //N個の素因数をH-1個の箱に配る O(1)
        cnt *= CM.num(N+H-2,N);
        cnt %= MOD;
    }

    //全てA=1と仮定して前計算 O(W)
    long long ans = 1;
    for(int i = 0; i < W; ++i) {
        ans *= cnt;
        ans %= MOD;
    }

    //i=0から数え上げ O(W)
    for(int i = 0; i < W; ++i){

        //Aに素因数がある部分だけ数え直しO(1) 2*3*5*7*11*13 = 30030 < maxA < 510510 = 2*3*5*7*11*13*17 なので高々6回
        for(auto e: P[i]){
            long long N = K[e.first];
            //N個の素因数をH-1個の箱に配る数を戻す O(1)
            ans *= InvMod(CM.num(N+H-2,N),MOD);
            ans %= MOD;

            //M個の素因数をH-1個の箱に配る O(1)
            long long M = K[e.first] - e.second;
            ans *= CM.num(M+H-2,M);
            ans %= MOD;
        }
    }

    cout << ans << endl;
     
    return 0;
}

D - Semi Common Multiple

AtCoder Beginner Contest 150 D - Semi Common Multiple
問題リンク
https://atcoder.jp/contests/abc150/tasks/abc150_d

問題文は割愛。

これ難しいね。

考察過程。

まず言われた通りに式変形。
A_i/2=B_iとすると
X=2pB_i+B_i=(2p+1)B_i
p=0,1,2,3,......なのでB_iの奇数倍がXになる。

適当にB_iを奇数倍して数を揃えるとそこからは簡単に求まりそう。

最大公約数っぽい？→B_iが1e9ぐらいまではありえるので、LCMがオーバーフローして無理

こういうときは素因数分解してLCMの素因数だけ求める→Nsqrt(A)が通らないので無理

てかそもそもLCM求めたとして奇数倍遷移でいける？→無理なときもある


あーこれは全探索系か？Xの値を決め打ち全探索→でかすぎて無理

エスパーか？サンプルエスパーなのか？→エスパーできません

とりあえず無理なパターンだけ弾く方針で、そうすると残りは簡単に求まったりするときがあるので

2,3,5とかだと無理だなあ……あ、これ偶数あるとき無理なのでは？→嘘でーす2,6,6とかだと全然作れる。

LCMとりつつLCMとの商を見て偶数なら弾く？(何を言ってるんだ)(コンテスト中は慌てがち)→実装

いやいや違うわ

うーん、てかそもそもLCMでかくなっちゃうからなー……あっM以下じゃん……！

全体のLCMを計算しつつMを超えたらそこで計算打ち切って0を出力でオッケー。
これだとLCMを計算する方針で進めれる。
発想も綺麗だし典型っぽいしABCだしこれ想定解でしょと進めていく。

奇数倍遷移でLCMにならないパターンはどうしようか
そもそも奇数×奇数=奇数、偶数×奇数=偶数、偶数×偶数=偶数
なので今回は奇数の元は奇数のLCMにしかなれない。
もっと言うと偶数の数を調整できない、
あーこれはBに含まれる素因数2の数が同じであることが必要っぽい。

なので最初に2べきの数計算してsetに突っ込んでサイズ確認しておく

LCMが求まったのであとはカウントするだけ
算数苦手だなあ……あーこれは単調性があるので二分探索

個数をnとすると(nは自然数)
{2(n-1)+1}LCM<=Mならokだね。めぐる式書くだけ。

提出→AC
よかったよかった。

難しくて緊張感のある400でした。

https://atcoder.jp/contests/abc150/submissions/9409237

2020目標メモ。

まず去年の目標から。

･AtCoder青。
できた。

･黄パフォを出せるようにする。
少しできてきた。

･800点まで埋める。
できてない。持ち越し。700までは埋まったね。

･ARC-Eまで埋める。
取り組んでもない。

･AGC-Dまで埋める。
これは無理なやつ。

･こどふぉ紫。
できた。

･オンサイトに出る。
日経1回目出れたね。

･レートが上がらなくても精進をやめない。
やめてない。

･webアプリ何か一個ぐらいは作る。
自分用の精進記録アプリは割と普通に使えてて良い感じ。

･競プロ以外のプログラミングもそれなりに触る。
業務含めればまあ。

･会社をやめない/遅刻しない。
寝坊とかしても有給ぶちこんでるし社会性を保てている。


ほかにやったこと
・修士号get
・こどふぉ薄橙タッチ
・PASTエキスパート



2020目標
・AtCoder黄
・こどふぉ濃橙タッチ
・AtCoder800まで埋める
・ARC-Eまで埋める
・yukicoder★3まで埋める
・こどふぉ2000以下とかでいいから数を埋める。
・マスターオブ場合の数/整数をやる

・システム設計意識してwebアプリをつくる
・今の会社をやめてもいいから仕事は続ける
・機械学習を復帰する

2019は目に見える成長があって悪くなかった、2020年もやっていき。

yukicoder No.951 【本日限定】１枚頼むともう１枚無料！

タイトルがタイトル感薄い......。
No.951 【本日限定】１枚頼むともう１枚無料！ - yukicoder


ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
問題概要

{\displaystyle N}個の荷物がある。価値が{\displaystyle A_i}、コストが{\displaystyle B_i}
総コスト{\displaystyle K}以下のときの価値の最大化。
ただし1個荷物を選ぶ度に、そのコスト以下の残った荷物1つをコスト0で得ることができる。
{\displaystyle 1 \le N,K,A_i,B_i \le 5000}

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
とりあえず選んだ荷物のコスト「以下」の荷物1個コスト無しにできる、という制約が結構扱いにくい。
こういうときはコストでソートして大きいものから見る。

見た目がもうdp。ナップサックしたい。できそう？
コスト無しボーナスがあるので、今まで選んだ個数と今の所持金両方管理したい......がそれは3乗になり無理。

ここで最終的に選ぶ荷物の集合を考える。
すると無料ボーナスを充てるべきはどの荷物だろうか？
これは貪欲に高いもののコストを無にしたい気持ちになる。

そう、荷物をコストの降順にならべたときの偶数番目の荷物をコスト0にするのが最適
これを踏まえると、今まで選んだ荷物の数を管理する必要はなく、ボーナスを発生させられる余分な荷物が ある or ないの2状態だけになる。
遷移も2*5000*5000回なので十分間に合う。
愚直に配列持つとMLEするので%2とかでよしなに。

#include <bits/stdc++.h>
using namespace std;

#define ALL(obj) (obj).begin(),(obj).end()
template <class T> void chmax(T& a, const T b){a=max(a,b);}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int N,K; cin >> N >> K;
    vector<int> p(N),d(N),x(N),y(N),idx(N);
    for(int i = 0; i < N; ++i) cin >> p[i] >> d[i];

    //コストで降順ソート
    iota(ALL(idx),0);
    sort(ALL(idx),[&](int l,int r){return p[l]>p[r];});
    for(int i = 0; i < N; ++i) x[i] = p[idx[i]];
    for(int i = 0; i < N; ++i) y[i] = d[idx[i]];

    //dp[i][j] コストi使ったときの価値の最大値(ボーナスあまりあり(j=1)/なし(j=0))
    vector<vector<int>> dp(K+1,vector<int>(2,-12345678));
    vector<vector<int>> tmp(K+1,vector<int>(2,-12345678));
    dp[0][0] = 0;

    //遷移
    for(int i = 0; i < N; ++i){
        //一時配列を初期化
        for(int j = 0; j <= K; ++j) tmp[j][0] = tmp[j][1] = -12345678;        
        for(int j = 0; j <= K; ++j){
            //普通に選ぶとき
            if(j+x[i]<=K) chmax(tmp[j+x[i]][1],dp[j][0]+y[i]);
            //ボーナスでコスト0
            chmax(tmp[j][0],dp[j][1]+y[i]);
            //選ばないとき
            chmax(tmp[j][0],dp[j][0]);
            chmax(tmp[j][1],dp[j][1]);
        }
        dp = tmp;
    }

    //最大値探索
    int ans = 0;
    for(int j = 0; j <= K; ++j) {
        chmax(ans,dp[j][0]);
        chmax(ans,dp[j][1]);
    }
    cout << ans << endl;
}

貪欲考えてソート後dpのいい典型。割とすき。

yukicoder writer感想

先日ゆきこでwriterしたときの感想メモ。
コンテスト　https://yukicoder.me/contests/241
解説　https://ningenme.hatenablog.com/entry/2019/10/25/232215


反省点
・難易度傾斜がゴミだった
　130-72-42-46-13-15 人とLDS=4になった。せめて5にはしたかった。すみません。
　
・Aからdpはよくない
　よくないね。すみません。

・後日修正されるような難易度表記をしてしまった
　これが一番だめそう。Omiyageとか星1個多くなっちゃった。すみません。



良かった点
・ぼくが楽しかった
　ワクワクしながら順位表見れた、最高。

・yukicoderが最高
　使いやすすぎてすごい、神サービス。みんな作問したほうがいい。



問題
・A Omiyage
https://yukicoder.me/problems/no/914
貪欲に見えるdpを作りたかったのでこんな感じに。
簡単に解かせる問題って大体自明貪欲が多いなーと思ってメタ的な。
本当は別の問題だったのですが既出見つけて爆発したので1週間前ぐらいにこれを差し込んだ。
昔のABCのCってこんな感じで300点だよねーって思ったり。




B Plus Or Mutiple Operation
https://yukicoder.me/problems/no/915
dpに見える貪欲を作りたかったのでこんな感じ。
これ難しいと思う。
繰り上がり使って和の遷移で得するところなかなか気付けない。
僕もハマった。実験して気付いた。
愚直dpは秒で書けるからまあコンテスト中でもそんな感じで通せるのは通せるなあって思って。

最初これ★1.5の初手で置こうとしてた(は？)あぶないあぶない。
まつかわさんと話して難易度を★2にした。コンテスト後★2.5になった。ごめんなさい。

C=1がコーナーになるのもハマった。最初のwriter解はABでした()
サンプルに置いとけばよかったね。非本質で落としたい気持ちはないので。



C Encounter On A Tree
https://yukicoder.me/problems/no/916
これ数えれそうだな〜って思った設定が数えれたのでそのまま出した。
いつもとは違った形でlcaを求めるのが好きなところ。
問題文が分かりにくいよね、どう書いたらマシだったかなあ。



D Make One With GCD
https://yukicoder.me/problems/no/917
人工的に生やした。実装めちゃめちゃ軽くなるのがすき。dpテーブルをmapで持つのもすき。
僕は最初約数列挙してたんですがfineさんが今の解法を教えてくれた。賢い。
直前にこどふぉでこれの木ver.が出て焦ったよね、なのにそのまま出しちゃった。
1問枠を無駄にしたのでそこは反省。



E LISGRID
https://yukicoder.me/problems/no/918
これ割と難しく作れたつもりだったのにてんぷらさんが秒で解いて簡単になっちゃった()
僕はAtCoder600点ぐらいの気持ち。まあ構築だし気付けば簡単ではあるか。
割と綺麗に解けてお気に入りの問題。これを出したくてコンテストしたまである。
なのに一番解かれなかった、解いて～～。



F You Are A Project Manager
https://yukicoder.me/problems/no/919
解きにくい問題作りたいなと思って。
ゲームっぽい設定で操作の自由度が高いと難しいかなーと思ってこんな設定に。
今見るといや決め打ち自明やろってなるけど。

チームエンジニアリングは中央値の人間に依存するみたいな謎設定にしたら平方分割とか必要になっちゃった。
実際どうなんだろうね。

この問題だけ非想定解出まくったので反省点
・RBSTを知らなかった。
・Wavelet Matrixを知らなかった
・nth-elementを知らなかった。
無知ですみませんでした……いやーやっぱ青がwriterは力不足だね。本当に。
色のせいしちゃいけないけど。




全体を通して。
yukicoderさん、テスターさんありがとうございました。
僕一人では嘘解法だらけの貧弱テストケースワクワクコンになっていた。本当に。
テスターみんな僕よりレート高い人にしてもらえたので恵まれてるなあと感じた。豪華だ。


コンテスト後の解法ブログとかツイートとか見ると嬉しい気持ちになるね。うれしい。

個人的には準備大変だった。問題は20問近く作ってそこから選んだ。ボツばかり生まれる。


今回は300-400-450-500-600-700ぐらいの所感でセットを作った。
もっと強くなって難しい問題作れると楽しいだろうな。精進しないとな。
また黄色になったときセットやりたい。作問もどこか機会があればまたやってみたいな。




おしまい。



テスターが赤コーダーってお金発生するのかな......。

yukicoder contest 229 解説

writer: くる / ningenMe
解説です。

A - Omiyage

https://yukicoder.me/problems/2842
部分和{\displaystyle dp}を行い、使えるお金のうち{\displaystyle K}以下の最大値を求めます。
{\displaystyle dp_{i,j}: i}番目の国まで訪れて{\displaystyle 1}つずつおみやげを買ったときに{\displaystyle j}円使えるかどうか。
これは計算量 {\displaystyle O(NMK)}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/391792










B - Plus Or Multiple Operation

https://yukicoder.me/problems/3389
まず {\displaystyle C=1}のときは{\displaystyle A}を作ることができません。その他の場合では必ず{\displaystyle A}を作ることができます。
{\displaystyle C}進展開を考えます。{\displaystyle C}進数で{\displaystyle M}桁(0-indexed)であるとき {\displaystyle A=D_MC_M+D_{M−1}C_{M−1}+… +D_1C+D_0,\ 0 \le D_j < C\ (0 \le j \le M)}と書けます。
ここで{\displaystyle C}倍する操作は{\displaystyle C}進数において{\displaystyle 1}桁シフトする操作、{\displaystyle i\ (0 < i < C)}を足す操作は{\displaystyle 0}桁目に{\displaystyle i}を足す操作に言い換えることができます。
よって桁の大きい方から「和の操作」によって数字を揃え、「積の操作」によって桁を上げることを貪欲に繰り返すことで、最適なコストで数{\displaystyle A}を作ることができます。
ただし最初の{\displaystyle 2}回の操作に関しては、和の操作で起きる繰上りにより桁シフトを行うことができ、この場合の方がコストが少ないときがあります。
具体的には{\displaystyle D_MC+D_{M-1}}と{\displaystyle 2C-2}の大小関係によってこのコストが変化します。
1クエリあたり{\displaystyle \log{A}/\log{C}}で計算することができるため、全体として計算量{\displaystyle O(Q \log{A}/\log{C})}で解くことができます。

【補足】
上記の操作が最適なことに関しての補足を以下に記します。(主にテスターのtpyneriverさんが証明してくれました、ありがとうございます)
数xにする最小手順を{\displaystyle f(x)}とすると以下が成り立ちます。

(1)
{\displaystyle f(0)=0}
{\displaystyle f(x)=1 \ (0 < x < C)}

(2)
{\displaystyle f(x)=\min{(f(x−1),f(x−2)…f(x−C+1))}+1 \ (C \le x,\ x\equiv\begin{eqnarray} i \bmod C\end{eqnarray}, 0 < i < C) }
{\displaystyle f(x)=\min{(f(x−1),f(x−2)…f(x−C+1), f(x/C))}+1 \ (C \le x,\ x\equiv\begin{eqnarray} 0 \bmod C\end{eqnarray} ) }

(3)
{\displaystyle f(Cx)=f(x)+1 \ (0 < x)}

{\displaystyle x=k \ (0 < k)}のとき{\displaystyle f(Ck)=f(k)+1 \ (0 < x)}が成り立つと仮定する
{\displaystyle x=k+1}のとき{\displaystyle f(C(k+1)) < f(k+1)+1}とすると(2)より{\displaystyle f(C(k+1)-i)+1= f(C(k+1)) \ (0 < i < C)}なる{\displaystyle f(Cx)=i}が存在する。
また{\displaystyle f(C(k+1)-i-j)+1=f(C(k+1)-i) \ (0 < j < C)}なる{\displaystyle j}が存在する。
これらより{\displaystyle f(C(k+1)-y)+2=f(C(k+1)) \ (C < y < 2C-2)}なる{\displaystyle y}が存在する。
ここで{\displaystyle C(k+1)-y \le Ck}であることと(2)より
{\displaystyle f(Ck) \le f(C(k+1)−y)+1=f(C(k+1))−1}が成立するので{\displaystyle f(k)+1\le f(C(k+1))−1 < f(k+1)}が成立。
しかし(2)より{\displaystyle f(k+1)\le f(k)+1}なので矛盾する。
よって{\displaystyle x=k (0 < k)}で{\displaystyle f(Ck)=f(k)+1}が成り立つとき{\displaystyle x=k+1}で{\displaystyle f(k+1)+1\le f(C(k+1))}が成立。
また(2)より常に{\displaystyle f(Cx) \le f(x)+1}であることから{\displaystyle f(k+1)+1\le f(C(k+1))\le f(k+1)+1} となり{\displaystyle f(C(k+1))=f(k+1)+1}が成立。

以上より{\displaystyle f(Ck)=f(k)+1}が成り立つとき{\displaystyle f(C(k+1))=f(k+1)+1}が成り立ち、{\displaystyle f(C)=2=f(1)+1}より{\displaystyle 0 < x}のとき常に{\displaystyle f(Cx)=f(x)+1}が成り立つ。

(4)
{\displaystyle f(Cx+i)=f(Cx)+1 \ (1 < x, 0 < i < C)}

{\displaystyle x=k \ (1 < k)}で{\displaystyle f(Ck+i)=f(Ck)+1}が成立すると仮定する。
まず{\displaystyle f(C(K+1)+1) \ (0 < j < C)}について、{\displaystyle C(k+1)+1}が{\displaystyle C}の倍数でないので(2)より
{\displaystyle f(C(k+1)+1)=\min{(f(C(k+1),f(Ck+i))}+1=\min{(f(C(k+1)),f(Ck)+1)}+1=\min{(f(C(k+1)),f(k)+1)}+1=f(C(k+1))+1}
同様に{\displaystyle j=2,…,C−1}で{\displaystyle f(C(k+1)+j)=f(C(k+1))+1}が成立。
よって{\displaystyle x=k}で{\displaystyle f(Ck+i)=f(Ck)+1 \ (0 < i < C)}が成立するとき{\displaystyle x=k+1}で{\displaystyle f(C(k+1)+j)=f(Ck)+1 \ (0 < j < C)}が成立する。
{\displaystyle f(2C+i)=f(2C)+1 \ (0 < i < C)}が成立するので、{\displaystyle 1 < x}で(4)は成立する。


以上より最適手順として
{\displaystyle f(0)=0}
{\displaystyle f(x)=1 \ (1 \le x < C)}
{\displaystyle f(x)=2 \ (C \le x < 2C-1)}
{\displaystyle f(x)=f(x/C)+1 \ (2C-1 \le x,\ x\equiv\begin{eqnarray} 0 \bmod C\end{eqnarray} )}
{\displaystyle f(x)=f(x - {\begin{eqnarray} x \bmod C\end{eqnarray}})+1} {\displaystyle (2C-1 \le x,\ x\equiv\begin{eqnarray} i \bmod C\end{eqnarray},\ (0 < i < C) )}

と遷移がわかる。

writer解はこちら。
https://yukicoder.me/submissions/392103









C - Encounter On A Tree

https://yukicoder.me/problems/2827
「すべての{\displaystyle i,j}について、頂点{\displaystyle i}の深さが頂点{\displaystyle j}の深さよりも大きいならば、頂点{\displaystyle i}に書き込まれる番号は頂点{\displaystyle j}に書き込まれる番号より大きい」という条件から深さ{\displaystyle d}の頂点に書き込まれるような数字の候補の集合を{\displaystyle s_d}とすると、{\displaystyle s_1=\{1\},s_2=\{2,3\},s_3=\{4,5,6,7\},…,s_d=\{2^{d-1},…,2^d−1\},…}となります。
よってある数字が書きこまれるとき、その頂点の深さは一意に決まることが分かります。

{\displaystyle l, r}が書き込まれた頂点の深さをそれぞれ{\displaystyle d_l, d_r}とし、また{\displaystyle l, r}が書き込まれた頂点の{\displaystyle lca}(最小共通祖先)の頂点の深さを{\displaystyle d_{lca}}とします。
長さ{\displaystyle k}のパスが存在する場合{\displaystyle k=d_l+d_r−2d_{lca}}かつ{\displaystyle d_{lca}≤d_l}が成り立ちます。
このような{\displaystyle lca}である頂点の候補は{\displaystyle 2^{d_{lca}-1}}通りあり、その1つの{\displaystyle lca}に対して{\displaystyle l}が書き込まれるような数字の候補は「{\displaystyle lca}の子を根とする部分木」を考えると{\displaystyle 2^{d_l-d_{lca}-1}}通りあります。
同様に{\displaystyle r}が書き込まれるような数字の候補は{\displaystyle 2^{d_r-d_{lca}-1}}通りあります。
また{\displaystyle lca}の子は左右の2通りがあるため、パスの長さが{\displaystyle k}となるような{\displaystyle l, r}の書き込み方は{\displaystyle 2^{d_{lca}-1}×2^{d_l-d_{lca}-1}×2^{d_r-d_{lca}-1} ×2}通りとなります。
残りの{\displaystyle l, r}以外の書き込み方に関しては、各深さごとに独立に候補の数字の順列を考えればよく、これは簡単に計算できます。

実装の際は{\displaystyle d_l=d_{lca}}となる場合のコーナーケースに注意してください。
全体として計算量{\displaystyle O(2^d)}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392120












D - Make One With GCD

https://yukicoder.me/problems/3305
愚直に全探索をすると{\displaystyle 2^N}通りの場合があり、とても間に合いません。そこで {\displaystyle dp}を行います。
{\displaystyle dp[i][j]: A_1}から見ていって最後に{\displaystyle A_i}を使って最大公約数が{\displaystyle j}になるような場合の数。
ここで{\displaystyle j}に関してですが、{\displaystyle \max{A}≤10^8}なので愚直に状態を持つと空間計算量、時間計算量ともに制約をオーバーしてしまいます。
しかし{\displaystyle A_i}を用いた最大公約数は必ず{\displaystyle A_i}の約数となり、{\displaystyle 10^8}以下の数字の約数の個数は高々{\displaystyle 768}個であることから無駄な状態を減らすことで十分高速に計算できます。

{\displaystyle 1}つの状態に対して遷移が{\displaystyle O(N)}個あるので、{\displaystyle x}以下の数字の約数の個数の最大値を{\displaystyle d_{max}(x)}とすると、計算量 {\displaystyle O(\ N^2d_{max}(A)( \log{\max{A}}+\log{d_{max}(A)})\ )}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392116













E - LISGRID

https://yukicoder.me/problems/3092
最初に数列{\displaystyle A}と{\displaystyle B}を昇順にソートします。
そして各行、各列において「前半は単調減少な数列、後半は単調増加な数列」になるように数列を構築することを考えます。ここで単調増加な部分に関しては題意の条件を満たすようにします。

するとこのとき、各マスにおける隣接マスとの大小関係が決まります。
この大小関係を有向辺とみなすことでトポロジカル順序が決まるため数字を矛盾なく書き込むことができます。トポロジカルソートしたときのスタートの候補となる頂点は最大でも{\displaystyle (1,1),(1,W),(H,1),(H,W)}の4つが存在しますが、{\displaystyle (1,1)}を最初にスタートとして{\displaystyle H*W}から順に書き込み、最後に{\displaystyle (H,W)}をスタートとして用いることで問題の条件に合うグリッドを構築することができます。

ソートと書き込み時の探索を考慮すると、計算量 {\displaystyle O(\ H\log{H}+W\log{W}+HW\ )}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392115











F - You Are A Project Manager

https://yukicoder.me/problems/3227

{\displaystyle K}を決め打ちすることを考えます。
すると左右からぞれぞれ{\displaystyle K}の倍数だけプログラマを選ぶ操作としてみなすことができるので、そのときの区間の中央値の塁積和を前計算しておくことで左から{\displaystyle L}チーム、右から{\displaystyle R}チーム作ったときの行動力の最大値を求める問題になります。

またこの値は塁積和をとった値に対してさらに累積maxをとることで、{\displaystyle L,R}の分割を決める位置を探索することに言い換えれます。

{\displaystyle K=1,2,......N}と動かしたときに、中央値を求める区間の数に関しては調和級数的に状態が小さくなるため、全体で{\displaystyle O(N\log{N})}個になります。

よってこの{\displaystyle O(N\log{N})}個の区間の中央値が分かると、{\displaystyle K}について全探索することでこの問題が解けます。

すなわち区間の大きさ{\displaystyle O(N)}、クエリ数{\displaystyle O(N\log{N})}で区間の中央値をオフラインで答える問題に言い換えることができました。

この中央値を愚直に求めると計算量が{\displaystyle O( Σ (N/K) K\log{K}) = O( N^2\log{N})}となりとても間に合いません。
しかし区間を平方分割し、Mo's Algorithmを利用することで区間を伸縮させながら高速に中央値を求めることができます。
区間の伸縮の際は(c++における)multisetを2本持つことで、{\displaystyle O(\log{N})}で中央値を管理することができます。

よって必要な区間の中央値を{\displaystyle O(N\sqrt{N}(\log{N})^2)}で求めることができます。

また全体としても計算量{\displaystyle O(N\sqrt{N}(\log{N})^2)}で解くことができます。

writer解はこちら。
https://yukicoder.me/submissions/392113