AtCoderの新ジャッジにおいて C言語のコンパイルオプション -lm がついておらず、数学関数(libm) を使う事が出来ません。（引数が定数の場合最適化によって使えてしまう事もあります）そこでこれらのコードを実行するために x87 をアセンブリから使う方法やl…
初めに この記事ではあくまでも時間計算量のオーダーのみを考慮しているため、定数倍についての保証はありません。 relaxed convolutionとは で多項式の積を計算するオンラインアルゴリズムです。Online FFTと呼ばれる事もありますが、Relaxed Convolutionの…
id:hotmanww です。2022/8/より三週間に渡って開催されていたはてなインターン2021に参加してきましたので、その参加記を書かせていただこうと思います。 応募と面接 選考に関しては Web から応募 → 書類審査 → 面接（オンライン）という流れで行われました…
読み込んでいます…
こんにちは管理人のhotman78です。下記、「プライバシーポリシー」に関して記載致しましたので、ご一読願います。 当サイトに掲載されている広告について 当サイトでは、第三者配信の広告サービス（Googleアドセンス） を利用しています。 このような広告配…
はじめに atcoderの階層構造は普段競技プログラミングをするに当たっては必要ありませんが、黒魔術をする時に使用することがあるのでまとめます 問題がある場合すぐに消します。 https://t.co/wuMDEeiJfhNim を利用して C++20 を使う例— zer0-star (@0x_zer0…
ICPC海外リージョナルとかyukicoderとかatcoderで見たことある気がする(問題はatcoderのNon-triangular Triplets位しか思い出せない) 1,2,3,4,5 + 5,3,1,4,2 = 6,5,4,8,7 1,2,3,4,5,6,7 + 7,5,3,1,6,4,2 = 8,7,6,5,4,11,10,9 一般化は 1,2,3,...,2K+1 2K+1,2…
問題 mojacoder.app 初項がA,Bのフィボナッチ数列の部分和として正整数Mを表す時、部分和の要素数の最大値を求める問題 考察 パット見ゼッケンドルフの定理 - Wikipediaが使えそう 後ろから貪欲に取るもののサンプルが合わない という等式を発見 後ろから枝…
これを #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…</vector<long></vector<long></long></vector<long></long></vector<long>
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++よりは元々作り…
util modint: 二項係数系もつけておくと便利 ツェラーの公式: どちらかと言うとcodeforcesで使える 年月日を入力にとって曜日を出力する fastIO: どちらかと言うとcodeforcesで使える 入出力が本質な問題が時々ある iterator: あんまり使わない 自作イテレー…
こういうのが作れます例手順 doratex.hatenablog.jp これに従ってoverleafを日本語対応させます 後は下記のテンプレートに書き足すだけ！！ 改行は\\\\でやると見やすい気がします！ \documentclass[dvipdfmx,autodetect-engine]{jsarticle} \usepackage[not…
試してないのでわからないのですがtie(t->r,t->r->l,t)=make_tuple(t->r->l,t,t->r);で木の回転が出来そう？— 5％の確率で橙パフォをとるhotman (@hotmanww) October 30, 2019 昔考えたやつをブログ化 //npはnodeのポインタ、b=1で右回転 ch[1]は右の子、ch[…
0.はじめに 僕自身が学んでる途中なので嘘などあるかも知れません 高速化に目覚めたので書いていきます これ使うだけじゃ速くならないと思います SIMD使う前の準備だと思って練習してます atcoderのC++(GCC 9.2.1)準拠です 1.入出力 int main(){ int res; as…
staticな変数を使ってこう出来ます 最初に前処理が必要な競技プログラミングのライブラリに重宝します void f(){ static bool init=0; if(!init){ init=1; //初回実行処理 } //毎回実行する処理 }
gcc拡張により 関数の前に__attribute__(( constructor))を付けると最初に 関数の前に__attribute__(( destructor))を付けると最後に呼ばれます __attribute__((constructor)) void constructor() { cin.tie(0); ios::sync_with_stdio(false); cout<
コード例は抽象化してません あしからず 1.がちがちの動的セグ木を使う コピペありの環境なら一番いいです 思想としてはポインタを使って必要になった時にノードを作るです 構築O(1)です template<typename T> struct dynamic_segment{ struct node; using np=node*; str</typename>…
追記 テストケースを見れるサイトを公開しました library-checker-testcases.hotman78.com コマンドプロンプトを開きます gitを入れます(手順は各自調べてください) cdコマンドで適当なディレクトリに移動して下の2つのコマンドを打ちます sudo git clone ht…
ark4rk.hatenablog.comこれを事前に読んで欲しいです。 分割統治法の方針でセグ木に乗せられます これにより、 点更新 [l,r)間の連続部分列における総和の最大値を求める が出来ます からなるベクトルを考えると、これがモノイドになっています。試しにベク…
拡大係数行列を考える。 この時、の時のみ解が存在する事が知られている。 転置行列についてもrankは同じであるため、で計算が出来る。 からでが求められる事から転置行列においては2倍の定数倍高速化も可能である。
