Posts

K番目の要素の二分探索による求め方と，ベクトルのt付近の要素

ネストしたベクトルは，添字を並べる順序で性能が変わるが，どのように並べれば良いかはよくわからない．

インタラクティブ問題のデバッグ方法

経緯 よく考えればもちろん作れるのだけれど，すぐ間違うのでメモをしておきます． 公式 $d \in \mathbb{Z}$，$t \in \mathbb{R}$ とする． $d \leq t \iff d \leq \lfloor t \rfloor$ $d < t \iff d < \lceil t \rceil$ $t \leq d \iff \lceil t \rceil \leq d$ $t < d \iff \lfloor t \rfloor < d$ 考え方 \begin{eqnarray*} d\leq t &\iff& t \in \{ t \mid d \leq t \} \\ &\iff& t \in \bigcup \{ [e, e+1) \mid e = d, d+1, \ldots \} \\ &\iff& \bigvee \{ t \in [e, e+1) \mid e = d, d+1, \ldots \} \\ &\iff& \bigvee \{ \lfloor t \rfloor = e \mid e = d, d+1, \ldots \} \\ &\iff& d \leq \lfloor t \rfloor \hspace{20em} \end{eqnarray*}...

mod ライブラリで素数以外の法に関してできること

順列組合せ・重複ありなし ライブラリに関するメモです．

二項係数に関する公式です．

setw(int n) 桁数を n にする setfill(char c) 余った場所を c で埋める． oct 8進にする hex 16進にする dec 10進にする fixed 固定小数点表示にする scientific 浮動小数点表示にする

インタラクティブな問題がたまに出題される． 特別扱いする必要があるか，ということだが， 何も考えずに書いてしまうとデバッグが難しい，ということがあるので， やはり形式を整えておきたい感じである． 先日の Codeforces R.812 (Div 2) Tournament Countdown で，TLE というめにあった． virtual base class を持つオブジェクトのメソッド呼び出しがあったりしたのが 良くなかったのではないかと思う． ということで，軽く実行できるようにしたい． ポイントとしては，ask() 関数と answer() 関数を用意する． これらで，問と答の入出力部分をラップする． 実装するときには，ask_i() と answer_i() という名前で書く． 通常はこちらを ask(), answer() として使い， 自動テストのと期には ask_judge(), answer_judge() に切り替える． 典型的な実装はこんな感じ．二分探索数当てゲームを想定． bool judge = false; ll ask(ll x) { return judge ? ask_judge(x) : ask_i(x); } ll answer(ll x) { if (judge) answer_judge(x); else answer_i(x); } ll ask_i(ll x) { cout << "? " << x << endl; string s; cin >> s; if (s == "SMALL") return -1; else if (s == "LARGE") return 1; else if (s == "EQUAL") return 0; else assert(0); } void answer_i(ll x) { cout << "!...

燃やす埋める問題についての記事です． 動機 燃やす埋める問題については，一度エントリを書いた のですが，そこにはともかく理解したことを全部書いたので，コンテスト中に参照しても把握するのがたいへん，という状況になってしまっています．そこで，コンテスト中に思い出したい最小限のことだけまとめることにしました． 考え方 問題文中に「$p$ のとき$b$を受け取る」という記載があったら，「先に $b$ を受け取る．$\neg p$ の時 $b$ を支払う」と読み替えて，すべて支払いをすると考える． グラフ全体の source ノードのラベルは True，sink ノードのラベルは False． ノード $p$ からノード $q$ への矢印に，重み $a$ がついているのは，「$p$が成り立つのに$q$が成り立たない場合，コスト $a$ を支払う」と読む． したがって，この図では，以下が表現されている $p_6$ が成り立って，$p_7$ が成り立たなかったら，$a_2$ 支払う． $p_1$ が成り立たなかったら，$a_5$ 支払う． $p_7$ が成り立ったら，$a_3$ 支払う． $p_8$ は成り立つ． $p_9$ は成り立たない． 最小カットが，コスト最小の真偽割当．図の赤線だと，$p_1, \ldots, p_6, p_8$ を真，$p_7, p_9$ を偽にする割当に相当し，この場合のコストは$a_2 + a_6$． 連言や選言のノードは，矢印を出せるか入れられるかが決まっている．下図を参照．不可の理由は，たとえば連言なら，$p$, $q$を真に，$p\land q$ を偽にできてしまうから．(矢印の根本を真にできてしまうと不当な利益がある．矢印の根本を偽にできても嬉しくない) したがって，「$p \land q$ なら，支払を行う」は，表現できない． しかし，$\neg q$ の方を表すノード $r$ を用意すれば， 「$p$ が成り立って $r$ が成り立たなければ，支払を行う」の形で表現できる．

解説ACです

Mo’s algorithm のコンテスト用メモです

Educational Codeforces Round 115 F. RBS の解法です． 解説ACです． 問題概要 問題へのリンク 文字 ( と ) のみからなる空でない文字列全体の集合を $S$ とする． $s \in S$ に対し，$s$ の空でない prefix であって， 括弧の対応が取れているものの数を $f(s)$ と書くことにする． 例えば $f(\verb!"()()()))"!) = 3$, $f(\verb!"(()())(("!) = 1$． $S$ の要素が $n$ 個与えられる． これらを並べ替えて連結して得られる文字列 $s$ について，$f(s)$ の 最大値を求めよ． 制約: $ 1 \leq n \leq 20$，与えられる文字列の長さの和は $4\times 10^5$ 以下． 制限時間3秒． 解法 0-index で記述する． $\bar{n} := \{0, \ldots, n-1\}$ とする． $s \in S$ に対し，現れる ( の数から ) の数を引いたものを $g(s)$ と書く． $s \in S$ で，全ての $i < |s|$ に対して $g(s) \geq 0$ であるものの集合を $L$ と書く．$D := S \setminus L$．...

公式解説とは少しだけ異なる解法です

公式解説の行間を埋めました．