AHC030 環境構築 振り返り

AHC030に出て、11位でした。 自分は長期マラソンは殆どやったことがなく、2015年に3回topcoder MMに出たのが最初で最後(のはず)でした。 なので今回のAHCで環境整備系も全て一からやることになりました。なのであえてそちらについての感想や振り返りを書きま…

マージテクの逆でよく出てくる"2個の木のうち小さいほうを探す"処理ってcoroutineと相性がいいよね

背景 次のような問題を考えます 2個の木が与えられます。部分木の頂点数を$n, m$とした時に、$O(\min{(n, m)})$時間で小さいほうの部分木の頂点を列挙してください。 このような問題は「データ構造をマージする一般的なテクの逆」などと呼ばれるテクニックを…

-march=native 諸々

概要 -march=nativeについて色々調べた。 話題の発端 こちらのツイートであると思われる。 分からんこれ何かの未定義動作踏んでる?? pic.twitter.com/ACV8fb8PjQ— AllDirections (@AllDirections4) 2023年12月21日 シンプルなコードで、しかも-march=nativ…

FHC 2023 Final 反省会会場 / 並列化研究

概要 / 言い訳タイム FHC 2023 Finalの順位表を見ると、私がBをダウンロードだけして提出していないことがわかると思います。 そもそもカクタス(F)をシバけないとどうしようもないセットではあったのですが、それでもBを出していれば一応5位で入賞であり、こ…

遅延Segtree3

大嘘昔話 実は「segtreeというのはモノイドを載せられて、lazysegtreeはそれにいい感じの作用が行えて…」のようにsegtreeが抽象化されたのは割と最近です。 昔はなんかsegtreeって大体実装一緒だな…と思いながら、みな自分のstarryskytree.cppを毎回コピペし…

Weighted balanced binary tree の平衡条件をWolfram Engineで

注: ガチ誰得記事 Weighted balanced binary treeという平衡二分探索木があります。詳細はwikipedia(Weight-balanced tree - Wikipedia)が詳しいのですが、ざっくり言うと 「子のサイズが親のサイズの少なくとも $\alpha$ 倍」 もしくは同値な表現として「左…

データ構造をマージする一般的なテクを高速化するやや一般的なテク

知る人ぞ知る謎の知識みたいになってる気がしたのでメモ。 サイズ $A$ とサイズ $B$ のデータ構造 ($A < B$) が $O(A \log B)$ 時間でマージできる場合、合計 $O(N \log ^2 N)$ 時間で $N$ 個の要素がマージできます。競プロだと std::set や std::priority_…

UCUP 2-11 (Nanjing) E: Extending Distance / 最小費用流の双対

久しぶりですごい時間がかかったのでメモ 大体次の問題。 $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…

Multiuni 2020 Day10 F

問題概要 問題 長さNのカッコ列 $a_1,a_2,\cdots,a_n$ が与えられる。これは正しく閉じているとは限らない。各文字は32bit非負整数の重み $b_1,b_2,\cdots,b_n$ を持っている。 カッコ列Sに対して、 $f(S)$ を次のように定義する $S$ が ()を部分文字列とし…

Suffix Automaton

概要 文字列 $S$ のSuffix Automatonとは、ざっくりいうととても性質のいいDFA(決定性オートマトン)である。一番代表的な性質は次のとおりである。 $S$ の部分文字列全て、またそれらのみを受理する。 頂点数,辺数が $O(|S|)$、より正確には $|V| \leq (2|S…

AGC 046 E Permutation Cover

解けずに解説読んだ 本質 答えが-1かどうか <=> (max < 2*min)に気づくかどうか [1, 1, ..., 1, 2, 2, ..., 2]のパーツができる <=> ↑の条件は全部できる 思考反省 方向性を間違えた 出来た: 辞書順最小なので判定条件 出来たが使わなかった: パーツごとに独…

競プロ実装テクニック

これはなに 実装力で戦える! ~競プロにおける実装テクニック14選~ - Qiita に触発された 競技プログラミングでコーディングの際気を付けていること - うさぎ小屋 を強く参考にしている 効果が高い or 一般性がありそう なことから書いたつもり 重要なこと…

WTF C2 Triangular Lamps Hard 別解法

今回は、Nimberを使ってWTF C Triangular Lamps Easy / Hardを解いていこうと思います。 C1 このような問題では、操作で変わらない不変量を考えたくなります 具体的にはにを書き込めば、では不変量です。 なのでこれを適切にシフトしたものを考えて、うまく…

Library Checkerを支える技術

あけましておめでとうございます。これは Competitive Programming (2) Advent Calendar 2019 - Adventar の 14日目の記事です。あけましておめでとうございます。 この記事では、Library Checker の宣伝をします Library Checkerって? 競プロのライブラリ…

yukicoder No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│

基本方針 ガン見 maspypy.com 解法 最近ipad買いました(私事) goodnote

Static Range Union Find

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参加記

TTPC2019にチームyosupo(yosupo, yosupo, yosupo)で参加して、優勝しました 前日 ここいる?*1 うんち 当日 コンテスト前 無(二度寝したので) 昼食 無(二度寝したので) チーム決め 無(それはそう) コンテスト 東 京 工 業 大 学 と4年ぶりの再会 A TTPC2020 …

プロキシを建てた

背景 マンションのネットが、マンション共有で安い!みたいなやつ なんかネットが不安定だった 最近、不安定を再現する方法が分かった(研で使っているサイボウズをノートパソコンから開く)ので、真面目に調べることにした 原因 共有部分のルーターのIPマスカ…

Gifted Infantsのチーム戦略について

メンバー yosupo, sigma, maroon 戦略 明確な戦略は特になかったです(完)。 いくつかのルールを守りながら(守らないこともある)、毎回適当にやってた感じです ルール 今誰がどの問題を読んだか、考えたか の紙を作る 特に得意ではないジャンルを無理にやらな…

Google hash code 2019 Final

Google hash code 2019に参加してきました hash codeって? google主催のコンテストで、GCJみたいなものです。一番の違いは形式で、2-4人チーム、パソコン無制限で短時間(予選:4時間, 本戦:5時間)というコンテストになっています。 予選は一発で、上位から、…

DDCC 2019

コード部門 A: なんかバグった、素直にD言語のgroup関数を使うべきだったかも、遅かった B: 平衡二分木使うか悩んだけどしばらく考えたら貪欲で普通に解けた、遅かった D: もう典型、segtree.hとmatrix.hを貼って終わり、速かった C: みんな解法は簡単という…

AGC 029

A 隣り合う要素をswapして数列をsortする最小回数は転倒数と呼ばれています B 2で割れる回数でグループ分けして←いらない 大きい順にマッチしていく という解法で解いた、1個目いらない 証明 xとマッチできる値たちのうち、x以下のものは1種類しかない、とい…

CODE FESTIVAL 2018

本選 対策 特になし 結果 ふつう 原因 Hの得意度は参加者の中でトップクラスだった自信があるため,Iを速やかに解ければ勝っていたと思うが,Iに90分掛けたためどうしようもないね 対策 転生? りんごの挑戦状 対策 ペイントで様々な色を作って眺める トップ…

minimize しんどさ s.t. 早起き

背景 突然寒くなって二度寝不可避 →出来る限りしんどくなく早起きしたい 目的関数 minimize しんどさ s.t. 早起き, 現実的な予算 10時起き安定を目標にする 環境 照明 空き巣対策に決まった時間に勝手に電気がつく機能があるのでオンタイマーとして使用,30…

C++ライブラリのテストを切り出している

C++ライブラリのストレステストを切り出しているという話 背景 プログラミングコンテストのライブラリには色々と要求されるが,一番重要なのはバグを少なくすることだと思う。 バグが無いだろうと信頼できればバグったときでもライブラリ以外の部分だけ疑え…

swap(v, v)は危ない?という話

-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>…

KUPC 2018

たまには記事を書きます,優勝したし(イキリ) 最初 何はともあれ木や数列にクエリを投げている100,000を探します。2題もありました。 M 実家のような安心感 クエリ3は見たことない気がします,有名? 最初に実装を間違えてWA+MLEを貰いました。 理由はわから…

JAG夏 2018 Day2 準備記

!!!解法のネタバレが含まれます!!!でも解説ではないです!!! yosupo, sigma, sugim, maroonでJAGの夏合宿を1セット作りました 経緯 petrozavodsk(ロシア)では、毎年競プロの合宿が行われています。ロシアなので人外ばっかりいるので、セットもそれ相…