背景プログラミングコンテストのライブラリには色々と要求されるが,一番重要なのはバグを少なくすることだと思う。高速化するという目的に対し本末転倒ではないかと思う。バグがないことを保証するのは不可能であるが,適切にテストを行えばバグが潜む可能性を十分下げることは可能だと思う。僕は後者のリポジトリにテスト用のコードも書く,のほうが好みで,自分のC++ライブラリ(https://github.com/yosupo06/Algorithm)にもある程度ストレステストを書いたりしていたのだが,ライブラリの長さが制限されているコンテスト用にライブラリをカスタマイズする必要が出てきた(個人的にこのルールに思うところはあるが)。テストは流用できるのだが,どうせなら切り出して両方のライブラリから共通で使えるようにしてしまおうと思い,切り出している。v)は危ない?という話-D_GLIBCXX_DEBUGを付けて以下のコードを実行するとアサートにひっかかります(https://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor)。std::move(s)が発生し、これがヤバイっぽい(UBを引き起す?)です。s)を使うことが多いと思います。s)をしないようにする。何はともあれ木や数列にクエリを投げている100,000を探します。M実家のような安心感クエリ3は見たことない気がします,有名?最初に実装を間違えてWA+MLEを貰いました。MLを使ったか見えた(これバグじゃない?)ので,あとちょっとメモリを減らせば通ることを確信しました(不正か?)。バグを直して,TrieのNodeのサイズを2/3にしたら通りました。(これはコンテスト後のスクショですが,コンテスト中もこういうふうに見えていた)Iちょっと考えたらlogたくさん解(SegtreeのNodeに2次元BITを乗せる)がわかったんですが,どう考えても間に合わないのでもう少し考えると,区間をsetで管理すればオーダーが落ちることがわかったので書きました(setが嫌いなのでsegtreeでごまかそうとしがち)。解かれてるニム?に取り掛かりました。今考えると戦略を間違えていたと思います。誤読して時間を溶かしました。これで実験すると規則性がありそうでなさそうでありそうなテーブルが作れます。相手より大きい数を一度宣言してしまったらもう殆ど負けみたいなものじゃないか?と気づくと解けます。順位表で前半からやってる人のスピードと後半の重さから考えて,後半を4題解く人は出ないだろうと予想しました。500解く人が出たらどうしようもないのでその場合は諦めることにして,前半を始めることにしました。AうんうんBDP書いちゃったC全探索系で出そうだな〜と思いながら紙で考えて解いたDだいたい半分にできそうなことはわかったが,クエリをきっちり30回で抑えられる証明ができなかった。辺に重み付き,というのは見たことがあった,確かIPSCG結構悩んだ結果,logを入れれば良くない?と気づいた。いうことでHとKのどっちに行くか悩む。順位表を眺めるにHなら時間内に通せそうだったので,Hに行くことにする。今思うとKのほうが良かった気がするHほうじょっぽい見た目をしていたのでほうじょをする。大体実家DPっぽい?同色がなければ実家DPだね。同色で完全に覆う区間があるとDPが破滅することでかなり悩んだ結果,よく考えるとそもそも抹消できたため解けた。思ったら実装がなんかバグりまくってしまい...運良くギリギリで通せたので良かったです。maroonでJAGの夏合宿を1セット作りました経緯petrozavodsk(ロシア)では、毎年競プロの合宿が行われています。ロシアなので人外ばっかりいるので、セットもそれ相応の難易度になっています。sugimでセットを作って送ろうという話があったのが始まりです。全部で11問作りました。そのうち8題を選んで、最初に2題追加したのがAPC001です。残りの3題に、最初に問題を8題追加したのが今回のセットです。MAX(petrozavodskの時点ではRESTOREは無かった))を足したのがpetrozavodskに送ったセットです。ない難易度に思えますがpetrozavodskだと9問解かれるらしいです→(http://karelia.snarknews.info/index.cgi?data=macros/day&menu=index&head=index&sbname=2018w&class=2018w&round=03)。ロシアはすごいですね(上のアルファベットにカーソルを合わせると問題名が見えます)。箇条書きmaroonはなんか流れで巻き込みましたが、結果的には相当作問してくれました。ありがとうございます。インターンシップを始めたら全然時間がとれなくなって、Fのデータ作成が炎上しました↑は諦めるという手法を取ることにより鎮火しました、実はケースがクソザコです(ごめんなさい...)突然数日前に英語をつけよう!という話になり、英語がつきました。maroonが大量の英語を書きました。前日の夜にJAGに英文校正頼む!って言ったらしてくれて、かなり大量の指摘をいただきました。JAGの方々本当にありがとうございます。(修正前に問題文は印刷されたので、合宿に来た方は見比べると指摘されたところがわかります)風船はやっぱり配りたいなってなって、FAだけ配ることにしました。D以降は全部行けそうだったので全部配りました。自分が関わった問題の感想を述べます。QueriesQ=1ならばなんの変哲もないDPです。クエリに答えるために要素を分割したくなるのですが、DPテーブルのmergeにminの畳み込みみたいなのが欲しくなります。これは厳しいことで有名です。実は、DPテーブルが2個に分割されていても、高速にクエリに答えられるという性質が有ります(3個以上だとだめです)。よって2個までなら分割できて、queueを2個に分割というと知っている人は知っているテクニックになります。僕は大学の授業でやりました。これは解法ドリブンで作りました。queueを2個に分割というのは昔から出したかったテクニックなのですが、うまく出題できたと思います。Sequences数ヶ月前にひたすら幾何精進をしていた時期があります。その時期に、幾何問題のepsの設定を、雰囲気submit連打ではなく理論立てて設定できないか色々考えたことがあります。その結果として、この問題の漸化式のような単純な操作をするだけでも爆発するから、深く考えても仕方がないという結論になりました。逆手に取って、この漸化式から問題を作れないか(そして普通にdoubleで計算すると爆発するんですよ〜ってイキれないか)考えました。直線の交点は連立方程式という昔習った知識を思い出し、連立方程式ならmodで面白いことが出来ないかと思い、問題が出来ました。一発ギャグみたいな問題で、どのぐらい解かれるか予想できずに不安だったのですが、思ってたのと同じぐらいの解かれ具合だったのでよかったです。Point三角形の内側の点を一点構成するだけというシンプルな問題です。考えるとピックの定理を検索できないという条件下だと厳しかったかもしれません。これは3人でいたときに適当にみんなで問題設定を考えて、うまく解けたので出しました。beatsというテクニックで解けたようです。beatsの記事を書いた人のチームでした。RESTOREがつきました。今回作った中で、一番好きな問題です。不可能にしか思えないんですが、実は物事がすべてうまくいって、結局普通の遅延伝播segtreeを書くだけになります。「長さNの数列が与えられます。以下のクエリをQ個処理してください。Rが与えられるので〜」みたいな問題文で、しかも考察がボス問級に難しいという問題はずっと作りたかったので、作れて満足です。Sortとりあえず適当に操作を考えた後、sigmaとこれのいい性質無いかな〜って考えたらsigmaが見つけました。その性質を活かすために、クエリを追加しました。クエリは何も考えずにAB反転にしたんですが、もう少し簡単なクエリでよかったかもしれません。問題案が十分だったこととか、データ構造が多かったこととか、なんか近い問題が直前に出たとかで、petrozavodskには送らずボツ担ってた問題です。準備はしてあったので今回は使うことにしました。01:56遅延Segtree2Tweet広告を非表示にするコメントを書くもっと読む2018-08-11遅延SegTree色々隠蔽の方法を考えています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。