知る人ぞ知る謎の知識みたいになってる気がしたのでメモ。 サイズ $A$ とサイズ $B$ のデータ構造 ($A < B$) が $O(A \log B)$ 時間でマージできる場合、合計 $O(N \log ^2 N)$ 時間で $N$ 個の要素がマージできます。競プロだと std::set や std::priority_…
久しぶりですごい時間がかかったのでメモ 大体次の問題。 $N$ 頂点 $M$ 辺の有向グラフと非負整数 $K$ が与えられる。各辺には非負整数の重みが付いていて、辺 $e$ の重みを $d_e$ とする。$K$ は $1 \to N$ の最短距離より小さくない。 $1$ 円払うと好きな…
AtCoderではともかく、ほかのジャッジでは想定解の正当性の保証がされていない出題が行われることがあります。 想定解の正当性の保証が出来ていなくても、ジャッジが大量にケースを入れてちゃんと動いたからOK!という出題は可能なのか考えてみます。 例えば…
追記：速くなってませんでした！sorry https://x.com/yosupot/status/1689337328547016704?s=20 競技プログラミングではmod 261 - 1のローリングハッシュが安全性と速度のバランスが良く、広く使われています。 詳しくは https://qiita.com/keymoon/items/11…
問題概要 問題 長さNのカッコ列 $a_1,a_2,\cdots,a_n$ が与えられる。これは正しく閉じているとは限らない。各文字は32bit非負整数の重み $b_1,b_2,\cdots,b_n$ を持っている。 カッコ列Sに対して、 $f(S)$ を次のように定義する $S$ が ()を部分文字列とし…
概要 文字列 $S$ のSuffix Automatonとは、ざっくりいうととても性質のいいDFA(決定性オートマトン)である。一番代表的な性質は次のとおりである。 $S$ の部分文字列全て、またそれらのみを受理する。 頂点数，辺数が $O(|S|)$、より正確には $|V| \leq (2|S…
解けずに解説読んだ 本質 答えが-1かどうか <=> (max < 2*min)に気づくかどうか [1, 1, ..., 1, 2, 2, ..., 2]のパーツができる <=> ↑の条件は全部できる 思考反省 方向性を間違えた 出来た: 辞書順最小なので判定条件 出来たが使わなかった: パーツごとに独…
これはなに 実装力で戦える！ ～競プロにおける実装テクニック14選～ - Qiita に触発された 競技プログラミングでコーディングの際気を付けていること - うさぎ小屋 を強く参考にしている 効果が高い or 一般性がありそう なことから書いたつもり 重要なこと…
今回は、Nimberを使ってWTF C Triangular Lamps Easy / Hardを解いていこうと思います。 C1 このような問題では、操作で変わらない不変量を考えたくなります 具体的にはにを書き込めば、では不変量です。 なのでこれを適切にシフトしたものを考えて、うまく…
あけましておめでとうございます。これは Competitive Programming (2) Advent Calendar 2019 - Adventar の 14日目の記事です。あけましておめでとうございます。 この記事では、Library Checker の宣伝をします Library Checkerって？ 競プロのライブラリ…
基本方針 ガン見 maspypy.com 解法 最近ipad買いました(私事) goodnote
N頂点のUnion Findが与えられます。以下のクエリがQ個与えられます。 given l, r, dist: merge(l, r), merge(l+1, r+1), merge(l+2, r+2), ..., merge(l+dist, r+dist) これを処理した後のUnion Findを計算してください これは D: LCP(prefix,suffix) - 「み…
TTPC2019にチームyosupo(yosupo, yosupo, yosupo)で参加して、優勝しました 前日 ここいる？*1 うんち 当日 コンテスト前 無(二度寝したので) 昼食 無(二度寝したので) チーム決め 無(それはそう) コンテスト 東 京 工 業 大 学 と4年ぶりの再会 A TTPC2020 …
背景 マンションのネットが、マンション共有で安い！みたいなやつ なんかネットが不安定だった 最近、不安定を再現する方法が分かった(研で使っているサイボウズをノートパソコンから開く)ので、真面目に調べることにした 原因 共有部分のルーターのIPマスカ…
メンバー yosupo, sigma, maroon 戦略 明確な戦略は特になかったです(完)。 いくつかのルールを守りながら(守らないこともある)、毎回適当にやってた感じです ルール 今誰がどの問題を読んだか、考えたか の紙を作る 特に得意ではないジャンルを無理にやらな…
Google hash code 2019に参加してきました hash codeって？ google主催のコンテストで、GCJみたいなものです。一番の違いは形式で、2-4人チーム、パソコン無制限で短時間(予選:4時間, 本戦:5時間)というコンテストになっています。 予選は一発で、上位から、…
コード部門 A: なんかバグった、素直にD言語のgroup関数を使うべきだったかも、遅かった B: 平衡二分木使うか悩んだけどしばらく考えたら貪欲で普通に解けた、遅かった D: もう典型、segtree.hとmatrix.hを貼って終わり、速かった C: みんな解法は簡単という…
A 隣り合う要素をswapして数列をsortする最小回数は転倒数と呼ばれています B 2で割れる回数でグループ分けして←いらない 大きい順にマッチしていく という解法で解いた、1個目いらない 証明 xとマッチできる値たちのうち、x以下のものは1種類しかない、とい…
本選 対策 特になし 結果 ふつう 原因 Hの得意度は参加者の中でトップクラスだった自信があるため，Iを速やかに解ければ勝っていたと思うが，Iに90分掛けたためどうしようもないね 対策 転生？ りんごの挑戦状 対策 ペイントで様々な色を作って眺める トップ…
背景 突然寒くなって二度寝不可避 →出来る限りしんどくなく早起きしたい 目的関数 minimize しんどさ s.t. 早起き, 現実的な予算 10時起き安定を目標にする 環境 照明 空き巣対策に決まった時間に勝手に電気がつく機能があるのでオンタイマーとして使用，30…
C++ライブラリのストレステストを切り出しているという話 背景 プログラミングコンテストのライブラリには色々と要求されるが，一番重要なのはバグを少なくすることだと思う。 バグが無いだろうと信頼できればバグったときでもライブラリ以外の部分だけ疑え…
-D_GLIBCXX_DEBUGを付けて以下のコードを実行するとアサートにひっかかります(https://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor)。 struct S { vector<int> a; } S s; swap(s, s); どう</int>…
たまには記事を書きます，優勝したし(イキリ) 最初 何はともあれ木や数列にクエリを投げている100,000を探します。2題もありました。 M 実家のような安心感 クエリ3は見たことない気がします，有名？ 最初に実装を間違えてWA+MLEを貰いました。 理由はわから…
！！！解法のネタバレが含まれます！！！でも解説ではないです！！！ yosupo, sigma, sugim, maroonでJAGの夏合宿を1セット作りました 経緯 petrozavodsk(ロシア)では、毎年競プロの合宿が行われています。ロシアなので人外ばっかりいるので、セットもそれ相…
イロモノにしか見えないと思いきや案外いいのでは？ #include <bits/stdc++.h> using namespace std; using uint = unsigned int; template<class T> using V = vector<T>; //template<class D, class L, auto op_dd, auto op_dl, auto op_ll> (since c++17) template<class D, class L, D (*op_dd)(D, D), L (*op_dl)(D, L), L (*op_ll)(L, L)> str…</class></class></t></class></bits/stdc++.h>
色々隠蔽の方法を考えています。 これはなんかごついね #include <bits/stdc++.h> using namespace std; using uint = unsigned int; template<class T> using V = vector<T>; template<class OP> struct SegTree { using D = typename OP::D; using L = typename OP::L; static constexpr auto e_</class></t></class></bits/stdc++.h>…
#include <bits/stdc++.h> using namespace std; using uint = unsigned int; template<class T> using V = vector<T>; template<class D, class OP> struct SegTree { OP op; //f(data, data) -> data D e; //単位元 int n, sz, lg; //サイズ, 2^lgに拡張後のサイズ, lg V<D> seg; SegTree(V<D> first, OP _op, D</d></d></class></t></class></bits/stdc++.h>…
A 数列を2個に割って(l_max - l_min) * (r_max - r_min)をminimize →arc073.contest.atcoder.jp B 0, 1が書かれたグリッドなのでなにはともあれ二部グラフ →連結なら完全グラフにできそう →連結成分の個数 C とりあえずどこを使うか決まってたら？ →各場所に…
a * b + c * d * eみたいに+と*のみからなる式が与えられた時に，いろんな部分文字列を高速に評価するのが本質です。 こういう変なのはad-hocにやろうとすると大体大変だしバグると詰むんですが，SegTreeで強引にやってしまえばノード2個のマージに落とせる…
A うん(ループを1からn-2まで回しWA) B A, A+B, B, 0 → A, Bが独立 → AC C 数直線をジグザグして移動距離の総和を考える →区間が全部点だったら？ → ARC 087 Fに酷似，各[i, i+1]ごとに左右の個数に注目すると自明な上界が出る →区間が区間だったら？ →かぶ…
