2021-03-28

数え上げ memo

大事なこと

主客転倒(数え上げる対象を逆転してみる)
まずはnaiveなDPを考える

考え中

包除を考える場合，ある状態の最大がhogehoge以上，とかいう包除はキツいことが多そう．管理しずらいので
E - LEQ and NEQ
これは連続する2つの値が同一にならないような列の数え上げだが， $X _ i == X _ {i+1}$ となる部分の個数の偶奇で数え上げて最後に包除している

数式記述メモ

$_N {C _ K}$

できることのメモ

$1\sim N$ から $M$ 個選ぶ，1個以上は $K$ 連続を含む

選ばれなかったものの集合を考える．
間隔が $K$ 以上の空間がある．この個数Xで包除
$T=N-M$ とする（選ばないもの)
$X=0$ -> $_ N {C _ T}$
$X=1$ -> $_{T+1} {C _ 1} * _ {N-T} {C _ T}$ ...
$X$ -> $_ {(T+1)} {C _ X} * _ {(N - X * K)}{C _ T}$
掛け合わせている1つ目はどこの隙間を間隔k以上にするか
2つ目はその隙間を確保した上で，どう塗るか
これを包除してあげると解ける
No.1414 東大文系数学2021第2問改 - yukicoder
https://yukicoder.me/submissions/635358

間隔をK以上開けて配置するパターン数

https://atcoder.jp/contests/typical90/tasks/typical90_o

物をT個置く -> 物の間にK以上追加でそれぞれ何個置くかをcombinationでやってやる

カタラン数関連

下のsnukeさんの記事の斜め線がどこに置いてあっても折り返しを考えれば解ける snuke.hatenablog.com

https://yukicoder.me/submissions/635379

${C _ 0} * {X _ 0} + {C _ 1} * {X _ 1} ... = S$ となる非負整数組 $({X _ 0}, {X _ 1}, ...)$ の数え上げ

係数の総和をKとしたとき，O(K³ log S)

// coef_0 * x_0 + coef_1 * x_1 ... =s
// をみたす非負整数(x_0, ...)の組の数を求める
// sum(coef)の行列を累乗する. 
mint myfunc(vector<int> coef,ll S){
    if(S<0) return mint(0);
    int n=(int)coef.size();
    int cs=0;
    for(auto &x:coef){
        assert(x>0);
        cs+=x;
    }
    assert(cs<=1000);// 多分1000でも耐えない

    vector<mint> A(cs+1,0);
    for(int bit=1;bit<(1<<n);bit++){
        int t=0;
        for(int i=0;i<n;i++)if((bit>>i)&1) t+=coef[i];

        if(__builtin_parity(bit)) A[t]+=1;
        else                      A[t]-=1;
    }

    Matrix<mint> M(cs);
    rep(i,cs) M[0][i]=A[i+1];
    for(int i=1;i<cs;i++) M[i][i-1]=1;

    M=M.pow(S);
    return M[0][0];
}

Editorial - AtCoder Beginner Contest 198

この問題では条件にx_1 < x_2...みたいな条件が付くが，差分を考えて変形することで項同士の関係を外してそれぞれの項が非負である条件のみを考えればよくなる

2021-03-27

UTPC 2020参加記

コンテスト前

リアルで集まって出たい！
ICPCチームメイツに声をかけるぜ！
1人欠けるから1人集めるぜ！
仮の人さんよろしくやで！

じゃあ当日集まってコンテストね！

仙台緊急事態宣言「ダメやで」

は？

コンテスト

開始前作戦
Aは仮の人さん
僕はBから見る
sota君は後ろから見る
得意分野を相談した結果↓

DPっぽい何か，僕
グラフ，sotaくん
数学，仮の人さん
— むげんちゃん (@mugen_1337) 2021年3月27日

仮の人さんがAを通す．
sota君がHを通す．
僕がDの部分点をとりあえず通す．
sota君がGを通す．
Dの部分点からの高速化ができないのでsota君を呼んで一緒に考えるがわからない
sota君&仮の人さんがJにかかることに
僕は分岐してDの考察とEの部分点にかかる
僕がEの部分点を通す
sota君がJを実装して通す
僕はD, Eの満点を考えるけどわからない
終了

D，解けなきゃダメじゃん．すまん...

感想

D, E復習します

2021-03-25

パズルに屈しない

屈した

https://codeforces.com/contest/1071/problem/C
https://codeforces.com/contest/1067/problem/C
D - 101 to 010
結局，1011111みたいなのと1111101みたいなのを取るしかない．
それらを組み合わせて元の文字列を作ることを考える．
実験しても気づくか微妙
naive解は作れるので方針乱打してnaiveと合うか，その方針は何がダメかの確認は手元でできたが，あまりに効率が悪いと思う
https://yukicoder.me/problems/no/1658

数列，2項以外全部1にして解ける？ -> 方程式が解ける形に落ちた．カス