読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

実装メモ

ローカル環境(win+msys)でのスタック拡張のおまじない

メモです再帰関数の呼び出しがかなり深いとこにいくときなど @btk15049 ulimit -s 20480とかはどうですか— nyashiki (@sizensuN) 2016年7月8日埋め込み機能便利

凸関数(単峰関数)の極値の探索について

単峰関数の極値の探索についてです.あんまり数学的な記述はしたくない(プロに殺されかねない)ので,単峰関数の説明は省きます. 凸関数のような極値を一つだけもつお山の形をした関数です.競技プログラミングにおいて,こういった問題を解くときに使われ…

競技プログラミングにおけるstd::unordered_***

はい. タイトルの通り,unordered_set,unordered_mapについてです. これらはset,mapを平衡二分探索木ではなく,ハッシュと連結リストによって実装することにより平均アクセス速度を定数に抑えています.ただし,悪意のある入力を除いて,です.一部のプロ…

定数倍を高速化するお話し

ただの経験則でベンチマークをしたわけではないが 結構重要だと思うのでメモ mapを使った座圧とsortを使った座圧 mapを使ったほうが実装は百倍楽です. しかし二分平衡探索木の挿入のlogが重いのか,結構遅い. 面倒だけど配列にぶち込んでstd::sortしてごにょ…

二分探索について

競技プログラミングにおいて,二分探索を使う機会はたくさんあると思います. そして二分探索の書き方には宗教,流派があって人それぞれ意見が異なるかと思います.整数範囲での二分探索ではwhileを使うやり方とforを使うやり方の二種類があると思います.ちなみ…

マス目を使う問題でのちょっとした実装テク

実装テク?H行W行のマス目があって 座標(i,j)から上下左右4方向に移動が可能な問題とかそういうやつに対応します。二次元配列で書いてもいいんですけど添え字演算子とか書く量増える上に 方向に対して番号付けできなかったりすると面倒なときがあるので便利な…

yukicoder 215 メモ 高速きたまさ法

間違ってるかもしれないけど解法の方針が分かった気がした。 実装している時間がないのでとりあえずメモまずM項間漸化式をで作成する。 これはEASY,MEDを解いてる人ならできてると思うので省略。 きたまさ法の説明は省略。 剰余環での畳み込み和をフーリエ変…

m項間漸化式の高速なアルゴリズム

3/22:テンプレート追加しました。m項間漸化式のk項目を高速に求める方法。通称「きたまさ法」と呼ばれるアルゴリズムについての(簡単な)解説。 考案者が蟻本作者の方でその名前からとられたみたいです。計算量は 入力 第k項: 初項 : で定義されるm項間漸化…

C++のvectorの比較のお話

問題じゃないけど重要なことなのでメモ。 C++のvectorはvectorオブジェクトに対して比較演算子が定義されている。 これはvector配列を辞書順で比較する。 2次元のvectorに対してsortを使えば辞書順での昇順になるしmapのキーにも使える。 盤面を二次元配列で…