MENU

難しい和音【Mojacoder】 解説

問題解説

問題

mojacoder.app

初項がA,Bのフィボナッチ数列の部分和として正整数Mを表す時、部分和の要素数の最大値を求める問題

考察

何故うまくいくのか

\sum_{i=0}^n F_i=F_{n+2}-1 より、 F_{n+2} が取れる状況で F_{n+2} または F_{n+1} を取らない事は出来ない

また、map等で管理することにより、隣あう二連続の値を取る場合は考えないで良い(隣り合わないとり方で同じ数字を表せるため)

  • F_{n+2} を取った場合: その後のとり方は複数ある

  • F_{n+2} を取らなかった場合: 隣あう二連続の値を取ることは考えないのでその後のとり方は一意に定まる

よって最大 \mathcal{O}(\log M) 個の分岐しか存在しないことが分かるので全体で \mathcal{O}(\log ^2 M) で解ける

え、10重ループくらい10秒でかけますよね？これってゴリ押し解法なんですか？

テクニック解説

これを

#define extrep(v,...) for(auto v:make_mat_impl({__VA_ARGS__}))
vector<vector<long long>> make_mat_impl(vector<long long> v){
    if(v.empty())return vector<vector<long long>>(1,vector<long long>());
    long long n=v.back();
    v.pop_back();
    vector<vector<long long>> ret;
    vector<vector<long long>> tmp=make_mat_impl(v);
    for(auto e:tmp)for(long long i=0;i<n;++i){
        ret.push_back(e);
        ret.back().push_back(i);
    }
    return ret;
}

こう

int main(){
    extrep(v,3,4,5){
        cout<<v[0]<<v[1]<<v[2]<<endl;
    }
}

出力結果

000
001
002
003
004
010
011
012
013
014
020
021
022
023
024
030
031
032
033
034
100
101
102
103
104
110
111
112
113
114
120
121
122
123
124
130
131
132
133
134
200
201
202
203
204
210
211
212
213
214
220
221
222
223
224
230
231
232
233
234

内部でDFSしてるだけです

rustでN次元配列を楽に作るマクロ

テクニック解説 
macro_rules! make_vec{
    ( $val:expr , $head:expr)=>{
        vec![$val;$head]
    };
    ( $val:expr , $head:expr , $($tail:expr),+ )=>{
        vec![make_vec!($val,$($tail),+);$head]
    };
}

で作れます

let mut dp=make_vec!(0,h,w);

のように使います C++よりは元々作りやすい感じがありますが、それでも有ると便利だと思います

atcoder黄色になるために必要になるかもしれないし、ならないかもしれないライブラリ一覧

その他解説

util

modint:
二項係数系もつけておくと便利


ツェラーの公式:
どちらかと言うとcodeforcesで使える
年月日を入力にとって曜日を出力する


fastIO:
どちらかと言うとcodeforcesで使える
入出力が本質な問題が時々ある


iterator:
あんまり使わない
自作イテレーターのテンプレート


timer:
実行時間を図る
ラムダ式で関数を渡す形にすると便利

平衡二分木

とりあえず、AVL木でset型、map型、配列型を持っておけばOK
永続遅延平衡二分木とか言うヤバがatcoderに出たことがあるので、持っておいたほうがいい(本当？)(僕は持ってないです)

セグメント木

双対/遅延/通常を動的/通常の２つで持っておくといいかも
2Dセグ木もyukicoderではよく見る

union-find

UF:これはみんな持ってそう


マージテクUF:データを乗せてくっつける(実装省略に使える)


重み付きUF:atcoderで出たこともあったはず


online/offline dynamic connectivity:
...よければ

形式的べき級数

Problem Listを埋めれるようなやつ一つ持っておけばOK
atcoderではmodを取らないやつがよく聞かれるのでmod 2^64-2^32+1もあるといいかも(僕は持ってない)

データ構造

binary trie:
xor系はatcoderで頻出！！(binary trieは作っておけば役に立つかもくらい...)


bit vector:
WM用


cartesian tree:
もしかしたらなにかに使うかも...


累積和:
ライブラリ化したけどフルスクラッチの方が慣れると書きやすい


disjoint sparse table:
冪等性が要らない状態で静的にの区間クエリ


32分木trie:
高速なsetの実装に使える(newをメモリプールで高速しないと速くならない？)
Trie for Fixed Universe Set - 週刊 spaghetti_source - TopCoder部
木構造の実装テクニック - Qiita


kdtree:
要らなそう


leftist_heap:
永続化してからが本番
永続マージ可能なデータ構造はとても使える


Li_Chao_tree:
convex hull trickするやつ
自分のはdoubleで死ぬ


RMQ:
黄色になってから作った
\lt O(N),O(1)\gtのRMQ


skew_heap:
手軽なマージ可能ヒープ、非想定が殴れるかも


sparse_table:
実装も軽いし、disjoint sparse tableより定数倍が軽いかも知れない(冪等性が必要)


SWAG:
少し前に流行ったやつ
尺取法と相性がいい


wavelet_matrix:
何でも出来るけど自分は範囲内でk番目に大きい値を取るやつしか作ってない
必要になったら追加する予定


永続配列:
カラフルツリーなどatcoderにも殴れる問題がある印象


永続leftest heap:
永続マージ可能ヒープ、強すぎる


永続セグメント木:
意外と使い所が無い


永続union find:
atcoderで出がち(並列二分探索を想定解に出来るため)


永続queue:
永続配列使ったO(logN)実装しか持ってないけどこれで十分？


永続stack:
永続配列使ったO(logN)実装しか持ってないけどこれで十分？
簡単に作れるとの情報をもらったので、作ります

グラフアルゴリズム

ダイクストラ:
pbds使用前提でO(E+VlogV)に高速化出来るやつは持ってて損は無いかも
Travel by Carでafter contestのTLEを防ぐことが出来た例あり


重心分解:
この前記事を書いた
【競技プログラミング】重心分解を25行で書く方法 - Qiita


支配木:
趣味


最大独立集合:
atcoderで類題が出ても問題はなさそう(ほんと？)


euler tour tree:
動的木の一種


HL分解:
atcoderでも使用しやすいかも


LCA:
これは作っておいたほうがいい


link cut tree:
殴れるかも知れない


最大流:
普通にatcoderにでる(と思う)


最小費用流:
普通にatcoderにでる
コストスケーリングも持ってる(どや)


全方位木DP:
ABC勝ちたいなら持っておくべきなきがする


強連結成分分解:
これも持っておいたほうが良さそう


top tree:
作れないので要らない事にしておく


二辺連結成分分解:
あって損はしない


2-sat:
atcoderで普通に出ると思う(よく知らず)

数学アルゴリズム

二分探索:
親の顔より見た
評価関数をラムダ式で渡す
doubleもあるといい


カーマイケル数:
素数modとは限らない(本当？)


二項係数:
modint に合わせて

ガーナーのアルゴリズム:
特に使う機会はないかも(NTTくらい？)


素数判定:
ミラーラビンのO(logN)を持っておくと便利

素因数分解:
ロー法+ミラーラビンでO(N^{1/4})を持っておくと殴れがち


ラグランジュ補間:
0~N-1項渡すとk項目が帰ってくる感じ

離散対数:
持ってて損はない


sum_of_floor_linear:
\sum_{i=0}^{n-1}[\frac{a \times i +b}{c}]の計算
sum_of_floor_linearを解くのに使える


tetration:
a^a^a^a^a^a...の計算
tetrationを解くのに使える


totient_sum:
トーティエント関数$\varphi(i)$の和$\sum_{i=1}^{N}{\varphi (i)}$を$O(N^{2/3}(\log\log{N})^{1/3})$で求める Wiki - yukicoder
atcoder以外ではわりかし活躍しそう


離散平方:
持ってません(は？)

行列

行列式:
行列木定理とかatcoderで出たら(出るの？)
疎行列は色々な高速化がある


行列累乗:
ABCで出たことがあるので持っとくべき


対角化:
持っておくべきだけど毎回フルスクラッチ
noshi基底が便利(集合をxorして特定の値を作ったり、最大値を作ったり)

文字列アルゴリズム

AhoCorasick:
複数文字列検索のお供、オートマトン上をDPする応用は自分には難しいかも


manacher:
あんまり理解してないけど回文といえばこれとeertree


Zアルゴリズム:
はい


動的Zアルゴリズム:
これは流行る(*´ω｀*)


rolling hash:
昔過ぎて設計思想がむちゃくちゃなので、フルスクラッチすることが多い


subseqence:
部分列をオートマトン化して保持するやつ(俗に言う部分列DPが出来る)


suffix array:
使ったことなし


suffix automaton:
いずれは使いこなしたい


trie:
atcoderにあってびっくり

DP

monotone_minima
簡単だけど強力

オフラインオンライン変換
簡単だけど強力
dp[j]=min(dp[i]+f(i,j))をO(N\log N)とかO(N(\log N)^2)で解く事ができる

overleaf(texのwebアプリ)で簡単にatcoder風作問

その他解説

こういうのが作れます

f:id:hotmanww:20200706205135p:plain
例

手順
doratex.hatenablog.jp
これに従ってoverleafを日本語対応させます
後は下記のテンプレートに書き足すだけ！！
改行は\\\\でやると見やすい気がします！

\documentclass[dvipdfmx,autodetect-engine]{jsarticle}
\usepackage[noto-otc]{pxchfon}

\begin{document}

\huge{Xor Sum っぽいやつ}\\
\hrulefill\\
\normalsize
実行時間制限: 2 sec / メモリ制限: 1024 MB /\\\\
\huge{問題文}\\\\
\large
ここに問題文を書く\\
\huge{制約}\\
\large
ここに制約を書く\\
\end{document}

【C++】木の回転を3行で書く

テクニック解説


昔考えたやつをブログ化

//npはnodeのポインタ、b=1で右回転 ch[1]は右の子、ch[0]は左の子
np rot(np t,bool b){
    tie(t->ch[1-b]->ch[b],t->ch[1-b],t) = make_tuple(t,t->ch[1-b]->ch[b],t->ch[1-b]);
    if(t->ch[b])update(t->ch[b]);
    return update(t);
}

make_tupleとtieを使って簡潔にかけます
AVL木前提のコードなので、他の平衡二分木ならもうちょっとnullptrに対して厳密にやる必要があるかも
nullptr=hoge
という文を作っても今の所良い感じにignoreしてくれてます(c++の定義を知っているわけでは無いので知ってる方いれば教えて欲しいです)

競技プログラミングのためにインラインアセンブラに入門してみたので解説【入出力,基本命令編】

その他解説

0.はじめに

僕自身が学んでる途中なので嘘などあるかも知れません
高速化に目覚めたので書いていきます
これ使うだけじゃ速くならないと思います
SIMD使う前の準備だと思って練習してます
atcoderのC++(GCC 9.2.1)準拠です

1.入出力

int main(){
    int res;
    asm("":"=a"(res):"a"(2));
    cout<<res<<endl;
}

2をaに入力して、何もせず、aをresに出力するコードです。
当然resは2になります

asm("コード":"出力":"入力");

が基本の書き方になります。
セミコロンで区切れば命令を繋げられます

2. 変数と代入

int main(){
    int res;
    asm("mov %2,%1":"=a"(res):"a"(0),"b"(2));
    cout<<res<<endl;
}

左にあるものから変数が割り当てられて行きます

つまり
"=a"とあるので%0はa
"a"とあるので%1はa
"b"とあるので%2はb
といった具合です

"="は出力専用であることを示しているらしいですが普通に読めてそうでよくわからないです
また、a,b,=といった文字は制約文字と言ってなんでもいいわけでは無いです
とりあえず、a,b,c,dが変数っぽく使えるので今回はそれで行きます。
制約文字についての詳しい説明はGCC x86 Inline Assemblerにあります

次にmov関数について説明すると
mov x,y はyにxを代入する構文です
x,y逆じゃないのって思うんですが、デフォルトだとこれらしいです(GAS構文と言うらしいです)

3. 注意の要らない基本命令

整数型限定です
64bitで渡せば64bitで
32bitで渡せば32bitでやってくれるみたいです
fujita nozomuさんありがとうございます！！


int main(){
    int a;
    asm("add %2,%1":"=a"(a):"a"(1),"b"(2)); //(%1)+=(%2);
    asm("sub %2,%1":"=a"(a):"a"(1),"b"(2)); //(%1)-=(%2);
    asm("imul %2,%1":"=a"(a):"a"(1),"b"(2)); //(%1)*=(%2); imulなので注意
    asm("inc %1":"=a"(a):"a"(1));           //(%1)++;
    asm("dec %1":"=a"(a):"a"(1));           //(%1)--;
    asm("or %2,%1":"=a"(a):"a"(1),"b"(2));  //(%1)|=(%2);
    asm("and %2,%1":"=a"(a):"a"(1),"b"(2)); //(%1)&=(%2);
    asm("xor %2,%1":"=a"(a):"a"(1),"b"(2)); //(%1)^=(%2);
    asm("not %1":"=a"(a):"a"(1));           //(%1)=~(%1);
    asm("shl %1":"=a"(a):"a"(1));           //(%1)<<=1;
    asm("shr %1":"=a"(a):"a"(2));           //(%1)>>=1;
}

http://ankokudan.org/d/dl/pdf/pdf-linuxasm.pdf
が詳しいです

4.注意のいる命令(idiv)

この場合、aを(%3)で割った商をaに、余りをdに格納します
aとdは固定です。意味わかんねぇ
なので下の場合出力は1 2です

int main(){
    int a,d;
    // (a,d)=(a/(%3),a%(%3))
    asm("idiv %3":"=a"(a),"=d"(d):"a"(5),"b"(3),"d"(0));
    cout<<a<<" "<<d<<endl;
}

5.終わりに

学んだのはここまでなので、一旦ここまでにします
if,forを使える様になりたい

参考文献

kikairoya.hatenablog.com
ja.cppreference.com