サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
災害への備え
yosupo.hatenablog.com
これはなに 実装力で戦える! ~競プロにおける実装テクニック14選~ - Qiita に触発された 競技プログラミングでコーディングの際気を付けていること - うさぎ小屋 を強く参考にしている 効果が高い or 一般性がありそう なことから書いたつもり 重要なこと 「競プロのきれいなコードと業務のきれいなコードは違う」と定期的に唱える。未来の自分 or 他の人 が読む必要がないことを仮定できるため、様々なバッドノウハウ(業務)が正当化される。(あえて過激なことを書くと、)「using namespace stdを使わない」などは逆にバッドノウハウ(競プロ)だと思っている。 -fsanitize=undefined,address / -D_GLIBCXX_DEBUG #include <iostream> using namespace std; int main() { int a[10
あけましておめでとうございます。これは Competitive Programming (2) Advent Calendar 2019 - Adventar の 14日目の記事です。あけましておめでとうございます。 この記事では、Library Checker の宣伝をします Library Checkerって? 競プロのライブラリを整備するために爆誕したサイトです。特徴としては、問題が全部ライブラリを整備する目的に特化していること、ケースジェネレーター、チェッカーなどが全て公開されていることが大きな特徴です 中身を全て公開することにより 誰でも問題の追加が出来る 誰でもケースの修正などが出来る CIに組み込める*1 などの、様々な利点を得ることが出来ます。理論上はO(使用人数)でケースが強くなっていくので、最強のテストケースが出来ると言う目論見です。 概要 こんな感じです こういう図を
平衡二分木は、定数倍は遅いしコード長がアホみたいに長くなりますがとても強力なデータ構造です。 そんな平衡二分木を使う事が最近多いので、使った問題を紹介します。 木の種類 RBST 軽実装かつコピー可能な(追記:不可能です。)プロコンなら最強感のある木 とりあえずコレを書いておけば困る事はあんまり無さそう 実装、解説はiwiwi大先生のスライドが良かった プログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~ AA Tree or LLRB Tree(Left Leaning Red Black Tree) insert/eraseだけの実装なら簡単 merge/splitの実装は面倒 reverseの実装は闇 insert/eraseの定数倍はRBSTより速い、僕の実装では Red Black Tree 実装は面倒だけど、reverseに関してだけはAA Treeよりも簡単だと思
T: フィボナッチ - Typical DP Contest | AtCoder 僕はこれの解法の理解に非常に時間がかかりました。 なので他の人もきっと時間がかかるよね?ということでメモを残します まず数列 について となるが与えられている ここでf(n) = {}となる関数f(x)を定義する(つまりfは ) ただし を満たす つまり、 ここで, nが渡されるからf(n)をO(k^2 logn)で求める 愚直に行列累乗してしまうともちろんO(k^3 logn) まず,f(n)がわかっている時に f(n+1)はO(k)で求められる これは簡単で とすると となり よって結局 またf(n)がわかっていたら, f(2*n)がO(k^2)で求められる まず、前述の方法により, f(n), f(n+1), f(n+2), ..., f(n+k-1)がO(k^2)で列挙できるのでする とすると となる
わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、 なんかいい感じのグラフを作ったらなんかそれの最小カットが答え というのがあります 最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り分けるという問題を考えます。燃やすと埋めるでも大丈夫です 最小カットで解ける問題というのは、実は 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある 罰金の最小値は? という問題だけです。 これの解法は、 「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る SからTに最大流 流せた量が答え 処理できる条件は「Xが赤で、Y
このページを最初にブックマークしてみませんか?
『yosupo.hatenablog.com』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く