Joeの精進記録

旧：競プロ練習記録

ICPC JAG 国内模擬 2017 練習記

vjudge.net

team Girigiriでやりました。

方針

Aはいつもどおりぼくが速解きする。Aが簡単そうだったらそのままBもぼくが読んで速解きする。Aに多少時間がかかりそうならBはけんしん。荻野/けんしんでC, Dを担当。ぼくはA, Bを終えたらE以降を雑に読む。C, Dの助けが必要そうならそちらやる。

A

2分で通す。やるだけだった。

B

問題文の細かいところを誤読していてサンプルが合わなかったので、にらみ直してデバッグ。10分ちょいで通す。

C

パソコンが空いたので荻野が書く。サンプルが合わなくて考察ミスか〜と言っていたのでちょっと話してみると考察ミスではないことが判明したみたいでちょっと書いて通す。

D

知らない間にけんしんが通していた。

E

ずっとFとHが解けそうという話をしていて、彼らが考察している間にやるだけ問題のEを書く。幾何だけどだいぶ重い。1時間ぐらいかかったけどAC. FとHは未だ解けずといった感じ

F

HがDPであることはほぼほぼ革新したけど状態数を落とせず。Fは最大流で考えていたが、もしかしてマッチングなのでは？という話になる。最初一般マッチングを考えていたが嘘であることが判明。二部グラフにできないかな？と話してたら本当に二部グラフの最大重みマッチングに帰着できることにけんしんが気づく。ギリギリにAC.

G(未)

荻野がかなり考察を進めたけど細かい場合の処理が思ったより大変みたいだった

H(未)

TDPCのうしろから二番目と同じ問題だったらしい

良かった点

初めて6完できた。F通せてよかった。幾何でペナつかなくてよかった。

改善点

  • Bで誤読したのは時間がもったいなすぎる。Bはじめけんしんに読ませていたけど普通にABを両方ぼくの担当固定にしたほうがいいと思う（Aで明らかに時間がかかるようであればけんしんにBを依頼する）。

  • デバッグ用マクロは普通に用意したほうがいい気がしてきた。幾何で座標をprintするのとか毎回ちゃんと書いてるの時間もったいなすぎる

東京大学のパソコンオタクが0から始めるジムトレーニング#0

Intro

普段は深夜2時からCodeforces, 根津駅の階段でバテる、好きなプログラミング言語はC++, 最近AtCoder黄色を目指している東京大学のパソコンオタクです。 突然ですがこのたび、ジムに通い始めました。

きっかけは友人が腕につけていたfitbitがかっこよかったから（ガジェットオタク）。

「ぼくもジム通いたい！教えて！いますぐ！」

場所はどうする？となったので適当に最寄りのAnytime Fitnessに決定。

ジムの契約

とりあえずジムに入ってみるとインストラクターのお兄さんに器具やスペースの紹介をしていただきました。

24時間いつでも使えて、月額7500円*です

（*値段は店舗により微妙に異なりますが、特定回避のため近い値段を書きました）

いざ実践

fitbitの購入が完了したので、実践編に移っていきます。

師からは

とのことだったので早速見ていきます。

と言いたいところなんですが、重量挙げのハードルが高かったので、定番のランニングマシーンから始めてみることにしました。

ランニングマシーン

ランニングマシーンはかなり本格的なもので、走っている途中にモニターで番組を見れたり、ヨーロッパなどの町並みを流してシティランをしている気分になれたり、Spotifyで音楽を聞けたりします。

速度調節もモニターででき、距離や時間単位でワークアウトの目標を設定できます。

そう、ここでこう思います。

「いや、何言うてんねん！」

東京大学のパソコンオタクにとってはランニングどころか理学部7号館の階段さえも敵なのです。

とりあえず時速6kmから始めてみることにしました。本当にとりあえずです。

ここで、時速6kmはオタクの早歩きより遅いことに気づき、徐々にペースをあげていけば自然にトレーニングを開始できるのではということがわかり、気づいたころには平均時速8km程度で30分走りきっていました。

f:id:xuzijian629:20190412204805j:plain

あきらかに天才です。

自転車こぐやつ

30分いい汗をながしたところで、次に自転車こぐやつ（名前わからないです）をやってみようと思いました。

ランニングマシーンと同じく、モニターがついており、ギアの重さなどを操作できます。
全世界の他店舗で同時にトレーニングしている人とレース形式でトレーニングを楽しむこともでき、それなりにやる気が保たれます。

レース形式ではおそらく自分の平均ペースと同じか遅いのペースの人が相手になるので、抜かれまくって悲しい気分になることは少ないはずです。

ランニングマシーンだとモニター上の景色がゆっくりしか動かないのでいまいちモニターを楽しめませんが、自転車の方は景色がどんどん変わっていくのでなかなか飽きません。

あっという間に30分が経ち、なんと12.8kmも進むことができました。

天才だからです。

f:id:xuzijian629:20190412210451j:plain

Outro

トレーニングの記録はfitbitがしっかりしてくれているので毎日続けようという気分になります。 f:id:xuzijian629:20190412210642p:plain

これは成功と挫折を繰り返し、パソコン片手にジムに通い続ける、情報系アスリートが生まれるまでの物語である…。（不定期連載です。）

↓↓↓読みましょう↓↓↓

note.mu

ポエム19/04/05

ポエムです。

先日院に進学しました。なんか教授たちが、院生は実質プロの研究者（煽りの文脈ではない）なので、 自覚をもって社会に還元すべく研究をしてください、みたいなことを言ってて、もう自分もそういう段階なのかーという気分になりました。これについていろいろ考えてしまったので文章にしてみようかなと思います。

はじめに、ぼくはかなり理想を追い求めてしまう性格です。自分のスキル・才能を伸ばそうみたいなことはあまり追い求めていなく、むしろ足りないところや、かっこいい/うらやましいと感じた物事に手を出しがちです。 数学は中学のときからもともと得意ではなかった（理科系は才能があったようで、少なくとも学校ではあまり苦労した記憶がない）のですが、数学ができる人がかっこよくて、高校後半からはずっと数学ばっかりやっていましたし、大学に入ってからはそれが情報科学になりました。

正直、自分がコンピュータ科学が得意だとは別に思っていません。でもコンピュータ科学には自分の憧れる分野、勉強していてワクワクする分野が多く、しかも優秀すぎる先輩方の数々話を聞くと、日々それなりにモチベーションは保たれます。

こういう性格をしているからこそ、これまで向上心を保ち続けることができた気がしますが、何かと要領が悪い生き方をしているなあという自覚はだいぶあります。まあそれは別に社会に何かを還元する責務が生じないうちは別にいいことだと思うんですが、研究者もしくは将来社会人として仕事をしていく上では、もう自分の興味だけで理想を追い続けている場合ではないなあと思うのです。これはハイクオリティなものを社会にアウトプットできるかという点だけから言っているのではなく、自分のためでもあります。

正直、理想を追い続けるのはだいぶ疲れます。もともと才能がある分野をやるなら、特に無理をせずアウトプットし続けられると思いますが、ちょっと背伸びをしてやっとインプットできるレベルの分野でアウトプットするのは難しすぎますし、こういう分野を専攻してよかったのかなと思うことさえあります。

これは昔から思ってたことなんですが、社会人になったらこういった性格をやめようかな、と思っています。なんかパートナーなり、家庭なりに全力を注いで、勉強や仕事は二の次にしたほうが気楽なんじゃないかなと思うことが多いです。

大学に入ってから気づいたことですが、大学院までの課程は”制限時間”がある分、多くのことに諦めをつけやすい環境です。たとえばIOIやICPCといった世界大会を目指してずっと精進している学生は多いと思いますが、いくらもがいても手がとどかない状態だったとしても、いずれ時間が彼らを諦めさせることができます。いいですよね。しかし、勉強関連以外の多くのことにおいて、制限時間は実質一生というものが多く、そういったことにおいて手がとどかない場所を目指し続けるのは心身ともに疲弊します。だからこういう性格をやめたいです。

今期の履修登録科目も、全部数理系の理論で埋めてしまったので、GPA崩壊も覚悟しているんですが、こういうことをするたびにここに書いたような気持ちが蘇ります。高校の時や学部のときは、今は考えなくていいやと思っていたんですが、そろそろ向き合わなきゃいけない時期だなあと思った次第です。

なんかコメントしてくださる方、もしここに書きづらいようであればDMでどうぞ twitter.com

競プロで使える高速化テクニック

ということで自分で書きます。ここでいう高速化とは真に計算量を落とすようなかっこいいものではなく、定数倍高速化のことを指します。

まあこういうのは無限にあると思うんですが、自分が過去に使用したものをいくつか紹介します。 良さそうなのがあれば追記していきたいのでコメントなりで教えてください。

言語はC++です。普段から高速化意識してコード書いてる人には当たり前のことしか書いていないかもしれません。

いつでもできるような高速化

コンパイルオプション

コンパイルオプションをこちらが指定できる環境ならばだいぶ強いです。具体的にはAtCoderやCodeforcesが可能で、TopCoderなどクラスで提出するような環境ではダメな気がします。ソースはありません。

プログラムの最初に

#pragma GCC optimize("Ofast")

と書くだけです。たいていのジャッジサーバは標準でO2でコンパイルすると思うので体感わずかに速くなります。50msぐらい速くしたい、みたいな状況で使えそうです。

浮動小数点数の計算がボトルネックとなるときは

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

を書くとかなり速くなります（知らんけど100ms以上の改善はありそう？）

入出力

cinが遅いとかendlが遅いという話です。自分の場合

ios::sync_with_stdio(false);
cin.tie(nullptr);

で困ったことがないのでたいていこれを使っています。1e5行入出力する問題だとこうするだけで100msぐらい速くなる印象です。endlはこれよりずっと遅いので複数行出力するときは'\n'使いましょう。

reserve

vectorやunordered_mapなどで使います。これは、要素数が増えるに従ってメモリ確保が動的に内部で行われるので、事前に確保してあげると速くなります。

emplace, emplace_back

primitive型ではない型をvectorやstack, queueに格納するとき、普通にpush, push_backすると要素のコピーが行われてから格納されるので、emplace, emplace_backをしたほうが速いです。

コンパイラを変える

高速化前のチェックリスト

大抵の問題の場合、そもそもTLE解法はwriterによって落とされる前提なので本当にその解法が高速化によって通る見込みがあるのかしっかり考察すべきです。とくに本気で高速化しようとすると30分や1時間経ってしまうこともあり、普通に考え直したほうが早かったなんてことも多いと思います。

しかし、（ほぼ）想定解だったにもかかわらずACを逃してしまうということもあるかと思います。そういうときのチェックリスト的な感じでまとめていきます。

そのmap, unordered_mapは配列ではダメですか

配列にするとさすがにだいぶ高速です。

そのvector毎回宣言しないとダメですか

たとえば要素数が高々2, 3のvectorを1000000回宣言するのとすでに宣言したvectorを使い回したり、primitive型で宣言するのでは時間が二倍以上違うと思います（測ってないけどもっと違う気がする）

modをとりすぎていませんか？

a + bのmod mでの足し算なら

a += b;
if (a >= m) a -= m;

と書くほうが

a = (a + b) % m;

より高速です。

限界編

正直↑に書いたことを全部守れているなら、制限時間が2秒だったとして、0.1秒縮めるのも相当困難だと思います。大抵の高速化は プログラムの命令数を少しでも少なくしたり、メモリアクセスや投機的実行をしやすくしたりすることを考えるよりも、コアな部分の処理を軽量化するほうがずっと楽だしずっと速くなります。

ただ、それをやってもあと20ms縮めたい、とかが極稀にあるかと思います。

random系は自作のxorshiftを使う

たとえばunordered_mapやrandom_deviceを使ったりするときです。

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main() {
    unordered_set<long long, custom_hash> ss;
}

みたいな感じです。

ループを分割する

たとえば、かなり人工的ですが

for (int i = 0; i < (k & 1 ? 100 : 200); k & 1 ? i++ : i += 2);

のようなループがあった場合、毎回ループ内で第２項や第３項をチェックされると遅いので、kが奇数の場合と偶数の場合にわけてループを書き直します。

メモリアクセスを考える

多次元配列の場合、これはわりと効果のある改善になると思います。

ループのブロック化

これはだいぶ限界な話ですが、メモリアクセスの高速化を考えると

for (int i = 0; i < 2 * n; i++) for (int j = 0; j < 2 * m; j++)

のループを一度回すよりも

for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {}
for (int i = n; i < 2 * n; i++) for (int j = 0; j < m; j++) {}
for (int i = 0; i < n; i++) for (int j = m; j < 2 * m; j++) {}
for (int i = 0; i < 2 * n; i++) for (int j = m; j < 2 * m; j++) {}

の4回を回すほうが(n, m)の値によっては高速です。

このスライドがわかりやすいです。

www.slideshare.net

最後に

異常高速化をしていないで正攻法でさっさと通しましょう

卒論を書きました

前回の投稿から一ヶ月以上空いてしまったので何か書こうかなと思いまして、先日無事書き終えた卒論を振り返ってみようと思います。

TLDR;

卒論を提出しました。

ほんとこれだけ。あとの内容は通学/通勤電車とかで暇な人がみるとよいかも。 急ぎなら後半を読むと切迫感があって面白いかもしれません（適当）

読者層

B3以下→機械学習の研究分野の紹介 or 卒業研究の流れの紹介だと思って読むとよさそうです。専門用語少なめにしているのでご安心ください。

B4→おつかれさまです。

M1以上/教員→B4の苦悩を見るなり、自分の過去と照らし合わせるなりしてください。教員氏、優上をくれ。

9月下旬

大学のAセメスターが始まりました。うちの学科ではこのタイミングでやっと研究室配属が行われ、2/1の卒論締切までを期限として卒業研究をすることになります。

ICPC Programming Boot Camp at Barcelonaに行く

研究室の教員曰く、理想的なペースは、9月10月にいろいろ論文を読んでテーマを探し、11月から研究を始められたら最高。12月から始めてもまあ大丈夫、というペースでした。これならさすがに9月は競プロしかしなくても大丈夫そうと思って、競プロ中心の生活をしていました。バルセロナは普通に楽しかったです。

10月前半

テーマ探しスタート

バルセロナから帰国します。うちの機械学習系のメジャー学会をいくつか知り、ICML, NIPS, ICLRなどのpaper一覧という便利なサイトが存在することを教えられます。とりあえずいくつか楽しそうなものを探してみました。この時点ではあまりにやりたいことが決まっていないためタイトルがかっこよさそうなものを選びました。めっちゃ多いのですが、自分のメモの最初の10個を列挙すると

  • Quickshift++: Provably Good Initializations for Sample-Based Mean Shift
  • Active Testing: An Efficient and Robust Framework for Estimating Accuracy
  • Synthesizing Robust Adversarial Examples
  • Nonconvex Optimization for Regression with Fairness Constraints
  • On the Relationship between Data Efficiency and Error for Uncertainty Sampling
  • $D2$: Decentralized Training over Decentralized Data
  • Network Global Testing by Counting Graphlets
  • Adversarial Attack on Graph Structured Data
  • Learning Memory Access Patterns
  • Noise2Noise: Learning Image Restoration without Clean Data

などに目をつけました。10月上旬はこれで終わりです（今思うと何もやってねぇ〜）

10月後半

アイデア出し

データ圧縮

なんかニューラルネットで破損したデータを復元するような研究ってどれぐらいあるのかということに興味を持って、とくにうまく復元できるようであれば、データ容量を大幅に落としてデータを管理できるんじゃないかと思いました。ICML, NIPSで関連研究を調べると皆無だったのでキターーーーーーと思いましたが、教員に相談したところ別学会を紹介され、「あっはい、、」という気分になりました。

  • Data compression and prediction using machine learning for industrial IoT
  • Enhanced Intra Prediction with Recurrent Neural Network in Video Coding
  • Research of image deblurring based on the deep neural network
  • Lossless Image Compression Using Reversible Integer Wavelet Transforms and Convolutional Neural Networks
  • Joint Source-Channel Coding with Neural Networks for Analog Data Compression and Storage

こんな感じの関連研究がいくつかありました。今思うと、これを進めても全然よかったかなとは思います（具体的なフォーマットに絞って研究すると、かぶってないのもありそうだし、普通に実用性あるんじゃ）。しかし、当時は「はい被った〜〜〜〜〜〜〜」みたいな意識があまりに強くて、さらにリサーチ序盤だったので無理そうなやつは深入りする前に早めに切ろうと思っていたので深入りせずに終わってしまいました。

組合せ問題を解く

これは演習３とよばれる研究室巡りの授業で、自分がちょっと触れた分野だったのでとっつきやすかったです。

  • Artificial Neural Networks that Learn to Satisfy Logic Constraints
  • Near-optimal linear decision trees for k-SUM and related problems

ここで紹介する論文とはかなり内容が異なりますが、研究室同期で最終的にこの分野を選んだ人はいました。

異常検知

これも有名な分野ですね。個人的にはプログラムの不備を検知してsuggestionしてくれるAIとかは自分がコーディングする上でもほしかったので、この研究をしてみたいと思いました。

これも面白そうではあるんですが、深入りせずに終わってしまいました。

GAN

GANというものをここに来て初めて知ります。知らない人向けに説明すると、GANとはgenerative adversarial networksの略で、生成ネットワークと識別ネットワークとよばれる２つのネットワークを組合せたネットワークです。画像生成とかによく使われますが、画像を生成するネットワークと、生成された画像と本物の画像を区別するネットワークを並列して学習させることでお互いの精度をあげる、という構図になっています。

うちの研究室では、GANで何かをやる！というよりかは理論保証を与えたりする流れだと思うので、GANがどういう条件のときに収束するか、などを研究しようと思ったりしていました。

それと、GANで超高解像度の画像を生成しようとしても莫大な時間がかかってしまうので、機械学習アルゴリズムで画像の解像度をあげる研究とかないのかなってのも検索していました。

学習限界

これはもしかしてそんなに研究されていないかもしれませんが（あんまり耳に入らない）、ある分布に従うある量のサンプルが与えられたときに、どこまで精度をあげられるか/どこまで情報を抽出できるか、ということに素で疑問をもって、調べようと思いました。さすがに先行研究が無限にありそうですけどね。

オンライン学習

  • Online Learning with a Hint

という論文があって、わりと解析的なことをしていて楽しそうだなと思いました。

という感じで、10月後半はわりと下調べはしたものの、自分の方針自体は何も決まりませんでした。こうやって書くとかなり調べてそうに見えますが、作業時間は3日ぐらいで、ほかはずっと競プロをしていた気がします。

11月上旬

当初教員が「11月から始められれば良い方」と言っていたので、「ふぁ〜悪い方になっちゃったか〜〜」とか思いながら研究内容を決めようとする。しかし、実際にはまだそれほど焦っていなかったりする。

テーマを決める（１）

ディープラーニングの研究全般がものすごい学習時間を要するのが嫌いだったので（実験に手間がかかるし、人によってかける時間が違っていて、特に大企業とかが圧倒的計算資源で殴っている感じがしてhogeだったので）、ディープラーニングの計算量を少なくする研究をしようと思いました。

具体的には行列はそこまで密でなくてもネットワークは十分複雑になるはずなので、疎行列からなるネットワークや、必要に応じて、密度を変化させる（疎→密）ネットワークについて考えていました。

  • Sparse Deep Neural Network Exact Solutions
  • Learning Sparse Neural Networks Through L0 Regularization
  • Deep Rewiring: Training very sparse deep networks

数日間これをやっていましたが、教員氏に、「最近のTPUとかは密行列の計算にすごく最適化されていて、疎行列よりむしろ速い」という本質的な指摘を受け、やる気が0になります。まあCPU環境だとたしかに強いと思うけどそういやぁディープラーニングは全然CPU環境じゃなかったですね、、、、、、

アイデア出し（２）

いろいろな構造のネットワーク

ぼくはデータ構造が好きなのでディープラーニングにももっと多様な構造がほしいなあと思って行列ガリガリ以外のディープネットワークを調べました。 Deep Random Forestとかに興味を持ちましたが、深入りせずに終了

ディープラーニング界隈は細かいdivisionが多すぎて全部に詳しい人は本当に永遠に論文をチェックしているんだなあという気分になる。

Adversarial attackから守る

専門用語かもしれないので解説すると、ディープネットワークをある微分可能な関数としてみると、入力を微変動させると出力もそれに従って変動します。出力を誤った方向にシフトさせるように、もとの入力に一見酷似するようなノイズ付き入力をネットワークに与える攻撃をadversarial attackといいます。ディープネットワークでは入力のベクトルの次元が数百とか数千になることがざらにあるので、各要素ごとに調整することで、要素ごとのノイズを小さく抑えたまま、ネットワークの出力を大幅に変えることができます。

研究室の先輩がこれをやっていてかなり第一人者っぽいし、演習３ではこれをやったのでわりと最初からアンテナは張っていました。 ネットワークの枝を学習時にランダムに切る、dropoutという手法は過学習を防ぐ上でメジャーですが、推論時に切るのはあまり見たことがなかったのでそれをやってみようと思いました。よさそう！という反応をしてくれた人もいましたが、なんかそこまで熱中できなくて終了してしまいました。

11月下旬

CODE FESTIVALに参戦したり駒場祭してたりしました。ポケモンの新作が想像以上に楽しかったです。

初日にイーブイの色違いを捕まえて多少バズりました。

テーマを決める（２）

もうこれアイデア出しと厳密な区切り目がないので（２）なのかどうかもわかりませんが、雑な区切りめとして、一週間近く以上同じものをやり続けた場合、テーマの方に分類しようと思います。 今回は凸最適化をやろうと思ったわけなんですが、なんかDeepMindから - Hamiltonian Descent Methods というすごい論文が出てて、話題だったし、わりと好きな分野だったので読もうと思いました。しかし、ページ数が80ページ近くある上に、 凸最適化問題における双対とかいう概念とか知らないことが多すぎて、25ページぐらいまで追ったあたりで、絶対に卒論期間に間に合わないと見切り、諦めることにしました。研究室の先輩とご飯にいくと、みんな口を揃えて「あれはやばい」とか「卒論でやるのはさすがに無理そう」というので「まあ。。。。」みたいな気分でした（語彙力）。

12月上旬

abstの締切が12/14だったので上旬になんとかしなければ！という気持ちになってきます。 さすがに危機感を多少覚えてきました。それまでアイデア等はSlackの自分とのDMに書いてきたのですが、膨れ上がってきたので自分でチャンネルを作ることにしました（↑のメモはたいていそこから）。

この頃、ツイッターのユーザ名を”Joe@卒論RTA”にしました。

テーマを決める（３）

上の画像の最後に書いていますが、複素数パラメータのネットワークを考えることにしました。実数パラメータのネットワークが中心ですが、複素数に拡張しようとするのはすごい自然だと思って、数日間取り組んでいました。

  • Deep Complex Networks

を読むが、複素数のメリットが皆無でhogeだった。なんかよくよく考えればわかりますが、実数ベクトルの次元を2倍にしただけでは？という気分になる。本人も複素数を用いているメリットを説明できていないし、open reviewを読むと同じ指摘がされていて厳しい。 個人的に複素数に興味を見出したのは、実部虚部という分け方以外に絶対値と偏角という分け方があって、後者はたとえば分類問題を考えるときに偏角の方向をターゲットのクラスに対応させられるのでは？と思ったけど、よくよく考えるとちょっとむずかしい。

調べると似たような話があった。

  • Complex-valued unsupervised convolutional neural networks for sleep stage classification.

関連論文を調べると他にも

  • A Fast Learning Complex-valued Neural Classifier for real-valued classification problems
  • Complex-valued convolutional neural networks for real-valued image classification
  • A mathematical motivation for complex-valued convolutional networks
  • Complex-valued neural network using magnitude encoding technique for real-valued classification problems & time series prediction
  • Orthogonality of decision boundaries in complex-valued neural networks

などが見つかる。これらは割と古い論文で、ディープではなく1層だけになっているものとかもある。

他に興味を持った点として、複素数演算の演算結果の実部と虚部は独立ではないので、実部で学習し、（実部となんらかの相関をもつ）虚部をチェックに使えないかなと思った。パリティチェック的な。パリティじゃないけど。

これをしばらく考えるが、そもそもadversarial attackを弾こうと思っても、adversarial attackは通常、学習時にはまったく経験しないタイプのinputがくるわけで、これをいきなり弾くのは直感的にむずかしそうという気分になる。見たことない入力時に出力をしないdeep abstain networkというのもあるが、deep abstain networkの論文ではadversarialについては考えていなく、通常の学習時に、判断できなそうなものをスルーする学習手法だったので、adversarialを学習時に判別させるのは話が違いそう。

結果、しばらく複素数ネットワークをやってみるも、それ複素数でなくても実数で実現できる、という結果にすべて帰着されてしまう（量子コンピュータならアレだけどいまのコンピュータなら複素数演算は全部実数でそりゃ置き換えられるし）ので厳しい気持ちになる。↑の複素数の研究をした人は一体どういうモチベでやったんだろうか。

テーマを決める（４）

突然天才的なアイデアがひらめく。adversarial noiseが入った入力に対して、それを更にごちゃごちゃにするぐらいの強いノイズをかけて、その上でネットワークに投げると逆に精度あがるんじゃないかと思った。さすがに実装が容易なのですぐに実験する。

全体の精度は下がるがadversarialをかなり守れるのでうれしい。アイデアもシンプルで実験もしやすいしさすがに優勝したんじゃないかと思う。理論保証は直感的にはすぐ思い浮かばないが、解析しやすそうな形をしているので、微積を鬼のようにすればなんとかできるんじゃないかと思った。

ちょっと話はそれるが、ノイズってなんだろうと考えたりする。ガウシアンノイズは簡単に弾けるが、adversarial noiseは全然規則正しいノイズではない。波うっていたり、斜め線の模様になっていたり、要は他の特徴量だと間違えられるような模様のノイズになるわけで、でもこういう模様みたいなノイズを一律して弾こうとすると本来の特徴量も弾いてしまうことになるので難しい。まあでも、ノイズを全体に散りばめてadversarialなノイズをかき消すのは、解析して見る価値がありそうだとは思う。

  • Adversarial-Playground: A Visualization Suite Showing How Adversarial Examples Fool Deep Learning

では、adversarialノイズがどういうニセの特徴量を埋め込んでいるかがビジュアライズされていて楽しい。

調べてみると、ノイズを混ぜることによる正則化の研究は昔からわりとある。 - Adding noise to the input of a model trained with a regularized objective - Training with Noise is Equivalent to Tikhonov Regularization - Robustness and Generalization - Robust Large Margin Deep Neural Networks わりとニアミス感があるが、まだ被っていないと信じていた・・・

被る

いろいろ研究を追っていると

  • Towards Robust Neural Networks via Random Self-ensemble

という論文ともろ被りしていることに気づく。2018年8月なので4ヶ月前・・・・・・。ネットワークの各レイヤーの前にノイズを入れるレイヤーを加えることによって正則化する論文だった。理論保証も自分が途中まで考えたものの後半を完璧にやってくれていて完全敗北する。

無理矢理でも新規性を付け加えようとする

ノイズを入れたあとにnoiseを取るとadversarial noiseも薄くなるのではと思う。ノイズを除去するにはFourier変換やWavelet変換が有名で、これも手元で実験すると普通にうまくいく。各層の前にnoise層とwavelet層みたいなのを用意するといいんじゃないかと思うが、wavelet neural networkみたいなものを勉強してもいまいちピンとこないし、理論保証的な側面でもどうやって進めればよいか全然ピンとこなくて、hogeみたいな卒論になってしまいそうと危惧する。

教員にキレる

この辺で不機嫌さがピークに達しており、それなりにこれまでも下調べをしてきているのにテーマが決まらない焦りと、数日後に迫ったabst締切に挟まれて、教員にメールをしてアイデアの評価やフォローを欲していたにもかかわらず、ためになるアドバイスがまったく得られなかったのでメールでちょっと怒ってしまいました。後日聞くと研究室で広まってて草

まあこれは、それまでのミーティングや研究室メンバーとのコミュニケーションを軽視してabst締切直前まで一人でやってきて、でもそれが無理だということに気づいて突然教員に絡みだしたわけですから、教員側からするとかなり「！？」という感じでぼくにも全然非はあるわけですが、一応名目上は指導教員なわけですし、もう少し内容のあるアドバイスがほしいなあと思っていた感じでした。

アイデア出し（３）

このタイミングでアイデア出すのやばすぎるな〜と思いながらアイデアを出そうとふんばります。あまりにもテーマを変えすぎているせいで教員と面談をすると第一声が「テーマは以前と同じですか？」になります。やめてえ〜〜〜〜〜

画像のrotateに不変なCNNネットワークとかを見たので、すごそうと思ってちょっと追ってみました。画像のアフィン変換についてロバストなやつでも考えるか〜という気持ちになるんですが、論文が被ったショックで深入りできず。病む。病むと他人を食事に誘いがちなんですが、これわかりますか？研究室の先輩と食事にいっていろいろ相談しました。

先輩の話だとやっぱり、無からいきなりテーマを見つけようとするのは至難の業。自分はこれまでを振り返っても、ある特定のテーマ一本で調べて、画期的な改善をすることを望みすぎていた感がありました。先輩は複数の分野の研究を融合するような研究をして、普通に国際学会に通す論文を生成したので、すごいなあと思いながら、先輩の研究分野の話も聞きつつ、アイデア出しを手伝ってもらいました。abstの締切までもう3日とかでした。

ぼくのもともとのアイデアであった、入力にノイズを加えるというやつも、入力がベクトルでない場合（たとえばグラフや集合など、ノイズが非自明である場合）のアプローチを考えるのはさすがに新規性では？みたいな話を聞いたりして、天才か？という気分になるなどしました。

さて、いろいろためになる議論をしたわけですが、ここで、transductive learningという言葉を初めて耳にします。transductive learningとは、データセットのうち一部だけにラベルがついていて、目標はデータセットのデータのうちラベルがついていないものにラベルを割り振ることです。一般の半教師あり学習と異なる点としては、未知なデータにラベルを振り分けることではなく、データセット内の他データのみをターゲットとすることです。

たいていこういう場合、要素の類似度に注目してデータのインスタンスを頂点とするようなグラフを作り、グラフ上でラベルを伝搬させていくという操作を考えます。

  • New regularized algorithm for transductive learning
  • Revisiting Semi-Supervised Learning with Graph Embeddings

などには、YouTubeの動画サジェッションで使われるアルゴリズムである、Adsorptionアルゴリズムや、その改良版のMADアルゴリズムが紹介されており、この路線でやっていくことにしました。当初のアイデアとして、伝搬させると同時に、ランダムに選んだノードのラベルを削除することで、より安定するのではないか？と思って、とりあえず暫定的に卒論のabstとタイトルはそれっぽいことを書いて提出しました。

12月下旬

さすがにそろそろ本気をださねばと思い、ツイッターを卒論仕様にしました。

これすごくたくさんのいいねをもらって応援していただきました。精神を安定させる上で本当に助かりました。フォロワーの皆様本当にありがとうございます。

テーマ決定（５）（嘘）

とりあえずabstをこれで出してしまったわけですし、先行研究を追うことにしました。 adsorptionアルゴリズムは、あまりにヒューリスティックスの塊で、ハイパーパラメータを適当に選んだり、収束性が謎すぎるなどして、ちゃんと理論的に追うべき箇所はたくさんありました。MADアルゴリズムに関する論文で、adsorptionアルゴリズムは、ある目的関数を最小化するようなアルゴリズムになっていないことが指摘されていたので、自分的にはある目的関数を最小化するようなアルゴリズムを提案しようと思いました。

adsorptionアルゴリズムをもう一度紹介しておくと、グラフが与えられ、いくつかの頂点にラベルが付いているとき、同じラベルを持つ頂点同士が重みの大きい辺で繋がれるように、ラベルがついていない頂点にラベルを伝搬させていくアルゴリズムです。adsorptionではこれをランダムウォーク的に行います。

勘のいい方はもうお気付きかもしれませんが、これは実質グラフの頂点に関するクラスタリングを考えているようなものですね。これまでぼくも何度か課題でクラスタリングを実装しましたが、それは実数ベクトルで表されるデータ（つまりユークリッド空間上の点）のクラスタリングであり、グラフのノードのクラスタリングを考えるのは初めてでした。グラフのクラスタリングって他にどういう手法があるんだろうと思っていくつか調べてみました。

そうすると

www.slideshare.net

などのスライドに出会うんですが、グラフのクラスタリングはグラフラプラシアンとよばれる量の固有値問題と深い関係があって、たいていグラフラプラシアンを固有値分解することに寄って解かれることがわかりました。

グラフラプラシアンの固有値問題は、実はRatioCutとよばれるある目的関数を最小化する問題と等価になるんですが、この目的関数がいまいち直感に反するというか、「ほんとにそれ最小化して、良いクラスタリングできるの？」という感じがしました。まあRatioCutを最小化する手法は、定式化のしやすさから非常に意味があると思いますが、結果のクラスタリングが納得行くものかといわれると微妙だと思いました。

そもそも、何を最適化クラスタリングとするかは当然目的関数によって異なっていて、なのでぼくはこれよりも良さそうな目的関数を作ろうと思いました。

そこで次のような目的関数を考えることにしました。

グラフをいくつかのクラスタにわけてクラスタ間の辺の重みと、クラスタ間の辺の重みを考え、前者は大きければ大きいほどよく、後者は小さければ小さいほど良いので、（前者マイナス後者）を目的関数としてはどうだろうか、と考えました。かなり自然ですね。

しかし、しばらく離散数学をするとこの最適化問題がNP-hardであることに気付かされます。しかしまあ大抵の最適化問題はNP-hardなのでここで諦めるには早すぎて、近似アルゴリズムを考えることにしました。

ここの流れを細かく書くだけでも一部の読者は非常に楽しんでくれそうですが、今回の記事の目的とは大きく離れてしまうのでながれをざっと書くことにします。 ぼくの目的関数は、グラフにおけるmax-cut問題と関連付けることができて、max-cut問題には実は0.87856近似アルゴリズムが存在します。

  • Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming

要は、本来の最適解をMとするときに、0.87856M以上のcutを保証するようなグラフの分割を計算できるアルゴリズムです。しかも元論文では、ランダムグラフではこれよりずっとよい近似率を実験的に確かめた、ということが書いてあって、これだーーー！！と思いました。

で、ぼくの目的関数を同様に近似して最適解することを目指したんですが、どうしても頂点数 Nに対して O(N^3)の計算量がかかってしまいます。

指導教員に相談したところ、面白そうだけどそこまで計算量がかかっちゃうとね〜〜〜〜という感じでした。ぼくはまあでも最悪卒論の内容にはなるかなと思って久しぶりにちょっと一息していました。このタイミングでツイッターのアカウント名をJoe@卒論★★☆☆☆に変えた気がします。

1月上旬

年末年始はいろいろイベントがあったので卒論を忘れて人生を楽しみました。昨年度は研究室のミーティング等にまったく参加しなかったのでその反省として2019年は全参しようと思って意気込みました。

ぼくの当面の課題としては、まあ適当に論文を書きつつ、 O(N^3)という計算量をなんとか下げられないかなと思っていました。 O(N^3)は競プロでは完全に行列積だったりワーシャルフロイドだったりで激遅アルゴリズムの部類なので、うーーーんといいながら作業していました。

・・・・？

ワーシャルフロイド・・・？

距離じゃん

そういやK-means（ユークリッド空間のデータ点のクラスタリングアルゴリズム）も距離ベースで最適化行うな・・・

O(N^3)で全頂点対距離求まるならそれを求めてK-meansを同じことをやっても計算量変わらんってことか・・・

ん？それ全頂点対求める必要ある？

ダイクストラ数回やればよくない？

え？普通に速そうだしよさそう

テーマ変更（真）

1/10ぐらいでした。卒論締切までは3週間程度でした。とりあえず手元で雑にダイクストラを書いて実験します。さすがに競プロで無限回書いたので実験はテストケース生成等も含めて30分程度で終了しました。結果、よい！！！！！！！！！

とりあえずこれベースで論文を書くことにしました。本来、アカウント名は定義からするとJoe@卒論★★☆☆☆のままなんですが、明らかな進捗なのでJoe@卒論★★★☆☆にしました。

ちょっと研究を進めていくうちに、K-meansの理論保証付きアルゴリズムである派生版の存在も知りました。その理論保証を今回の場合に拡張できるかは定かではなかったですが、まあ頭に余裕があればやろうという感じで考えていました。

新年初の教員面談で案の定「前回とテーマは同じですか？」から始まり、ぼくも「いえ、変わりました」と答えて面談がスタートします。 教員もすごく興味をもってくれて、キターーーーーーーー！！！！！！と思いました。教員に理論保証はつくの？と聞かれて、何も証明していないのに「はいつきます」と雑に答えてしまいました（おかげでやらなければというモチベにつながったんですが）

その後1週間ぐらいは理論保証をやっていました。理論保証に関する論文を読むと、その中に現れるいくつかの不等式を自分の設定の場合でも示せたので、同様のロジックで示せそうだということがわかりました。

さすがに残り半月なので、いそいで論文を書くことにします。なんか当初語数が足りないと散々脅されていたので、めちゃくちゃ丁寧に書きました。グラフの定義、次数とは何か、隣接行列とは何かなど・・・

一応やったこととしてはK-meansを拡張するということですが、グラフのクラスタリング手法（12月下旬にいろいろ調べていたもの）とせっかくだから比較しようということになって、それらの説明もグダグダ書いているとすごい語数が膨れ上がってしまいました。

半分ぐらい書いたところで、証明があまりに長いので語数を気にする必要がないことを気づきます。 なんかグラフの定義とかも書き出すとキリがないし、競合アルゴリズムを詳細に解説したところでべつにそれを発展させるわけではないのでただただ読みにくさが増してるだけな気がしてきました。なので全部イチから書き直すことにしました。

とりあえず実験のチャプターまで書いて、教員に提出してレビューを待つことにしました。このときJoe@卒論★★★★☆にしました。待つ間数日暇なので、ちょっと気になっていた、上述したものとは異なる別アプローチの理論保証も今回の提案手法の場合に成り立たないかを考えてみることにしました。

直感的にはこれまた成り立ちそうなんですが、なんせアプローチが１つ目の証明と全然違うため、証明に苦戦します。

2/1締切ですが、写真は1/26の画像ですね・・・今思い返してもよく頑張ったと思います。

この日の夜にやっとその手法についても理論保証が与えられることが証明できました。理論保証がゆるすぎたので次の日に多少評価を改善するなどして、残された数日で論文を書ききることになります。

CodeforcesでDiv1にあがる

ちょっと時系列が前後しますが、実は1/23にこどふぉでDiv1にあがりました。これが本当に助かって、なぜなら2019年の目標をratedこどふぉ全参にしていたため、ここでDiv1に上がっていないと、卒論締切最後の週にある3回のDiv2（うち1回は締切前日深夜）に参戦することになって、明らかに卒論がやばいです。

1/27（締切5日前）

２つ目の証明を書く。これがかなり長い。一日中書いていた。実験のチャプターとconclusionを雑に生成してとりあえず最後まで書ききって教員に送る。

1/28（締切4日前）

やっと教員のレビューを読む時間ができたので、これまで溜まっていた（それほど溜まっていなかった）レビューを元に前半を校正する。校正し終えたところで、実験のチャプターの内容があまりに薄いので全部やり直そうと思う。

1/29（締切3日前）

実験プログラムを拡張しやすいように全部書き換える。レポジトリを公開するのに読みやすいようにかなりきれいに書き直した。また、もともとバグらせたままにして未実験になっていたやつなどをデバッグして直した。データ生成を自分でやったが、生成するグラフのパラメータを毎回手で調整するのが大変だったので自動化スクリプトを書いて、コマンド一つで論文の実験結果を再現できるようにしようと思った。これがかなり重い。

1/30（締切2日前）

実装を終わらせ、実験を全部やり直す。それまでは数値だけの表だけで、一切visualizeしていなかったのでpythonでもろもろのvisualizeをする。 さらに添削が返ってきたので、それを校正するなどする。

夜に実験部分を書き直し、校正も反映させて再提出

1/31（締切前日）

教員の添削がほぼほぼ英語なので、自分でも読み直して全部校正しようと思う。夜になってやっと英語の校正が完了する。それまで図表のキャプションは雑に書いていたが図表にもちゃんと説明文を入れることにした。

Conclusionが雑だったのでしっかり書いた。

同期３人が研究室に泊まることになったので景気づけにお寿司

こどふぉDiv1なおかげで深夜のDiv2コンテストを華麗にスルー

2/1（締切当日）

とりあえず自分の論文は全部読み直したし、教員からの校正も数箇所だけのレベルになったので、あとでもう一度読み直そうと思って、そのかわり教員のレビューがまったく進んでいなかった学科同期残り２名の論文をかわりに添削する。

一応初提出しておく（上書き提出が可能）

このためのbigEnter!!!!!!!

正直間に合うと思っていたのでちょっと他人に時間を割く。

当然徹夜。自分の論文２周めを読む。１週目ではアルゴリズム記述部分などはスルーしていたので、今回はちゃんとそこも追う。するとかなりfontなどに関する誤植が見つかって大忙しになる。また、先輩が、文献はbibtex丸コピだと、secondと2ndみたいに統一されてない箇所があってきれいではない、みたいな話も聞いて、そこも全部調整し直す。他にも、オーダー記法のbigOのフォントや、もろもろの細かい指摘を聞いて全部直す。普通に忙しすぎる。

指導教員が締め切り朝に、提案手法の名前おかしくね？みたいなメールを送ってきて、「！？！？！？！？！？！？！？！？！？！？！？」となる。このタイミングで言わないでくれーとなるが、研究室の先輩に相談すると、「ああ、よくあるよくある、俺も同じこと締切当日に言われた」みたいな反応を受けれぽかーんとなる。

さすがにアレなので、教員にあとで部屋にきて口頭でディスカッションしましょうみたいなメールを返信して自分の添削に全神経を傾ける。

教員がそのうち入ってきて、やっと教員が引っかかっていた点を理解したので直す。しかし、締切が近すぎて、もうレビューしてもらう時間がない！

締切18分前

結局ギリギリまで直して1分30秒前に最終盤を提出し、卒業研究が終了しました。

さいごに

長々しい文章を最後まで読んでくださってありがとうございます。なんか、いろいろありましたが、とりあえず形になる論文がかけてよかったかなと思います。研究室の先輩方にはいろいろ本当にお世話になりました。来年はつらそうな後輩がいたら声をかけてあげるやさしい先輩になろうと思っています。 指導教員の先生方もありがとうございました。優上をください（２回め）

文章を読み直していないのでかなり文体とかがごちゃごちゃになっていると思います。お許しください

毎日AtCoderを解いていないと怒ってくるchokudai botを作った話

事の発端

ぼくがICPC後に急に競プロにハマり始めて、でも案外（案外でもないか）毎日精進を続けるのは難しかったので学科Slackにそれをサポートする botを配置しようという話になりました。

結論から言うと、1ヶ月ぐらいはうまく機能しましたが、だんだんみんな怒られるのに慣れてきてただただbotの投稿が流れるだけになってしまいました。

同じシステムを採用するなら、やる気に満ち溢れている数人だけで採用するのがいいと思います。

↓こんな感じで怒ってくる

f:id:xuzijian629:20181212180642p:plain

仕様

  • 毎晩8時に、その日に一問も解いていない場合 AtCoderやれ とメンションが来る
  • 10時になっても問題を解いていないとさらに そろそろAtCoderやれ とメンションが来る
  • 11時になっても問題を解いていないとさらに いい加減AtCoderやれ とメンションが来る
  • Ratedな問題を解いた場合のみ、解いた問題の合計得点が200点以下なら、上述したメッセージが もうちょっとAtCoderやれ に変わる
  • 次の日の0:10に前日に解いた問題のSummaryと何日連続で解いたかのStreakが表示される
  • お叱りに対し、 やらない と返信するとその日の通知をミュートできる

こんな感じですかね。

実態

f:id:xuzijian629:20181212180814p:plain

（このときのぼくは別のことでめっちゃ不機嫌でした、、ゆるして）

実装

Hubotで書きました。 script/main.jsを以下のように設定します（ユーザ名のところや時間の設定のところは省きました）。

const puppeteer = require('puppeteer');
const cron = require('cron').CronJob;

// https://stackoverflow.com/questions/9768444/possible-eventemitter-memory-leak-detected
require('events').EventEmitter.defaultMaxListeners = 0

// ここにAtCoderユーザ名とSlackIDのペアを設定する
const id = {
  'xuzijian629': 'XXXXXXXX'
};
let latestPointsum = {};
let mute = {};

async function getSolvedProblems(user, date, update) {
  let ret = {solved: []};
  try {
    const browser = await puppeteer.launch();
    const page = await browser.newPage();
    await page.goto(`https://kenkoooo.com/atcoder/?user=${user}&kind=user`, {waitUntil: "networkidle2", timeout: 3000000});
    await page.waitFor(60000);
    let streak = await page.$('#root > div > div > div > div > div:nth-child(3) > div:nth-child(7) > h3');
    ret['streak'] = await (await streak.getProperty('textContent')).jsonValue();
    let longestStreak = await page.$('#root > div > div > div > div > div:nth-child(3) > div:nth-child(6) > h3');
    ret['isLongest'] = ret['streak'] === await (await longestStreak.getProperty('textContent')).jsonValue();
    if (ret['streak'] === '1 days') {
      ret['streak'] = '1 day';
    }
    let pointsum = await page.$('#root > div > div > div > div > div:nth-child(3) > div:nth-child(5) > h3');
    let sumvalue = await (await pointsum.getProperty('textContent')).jsonValue();
    sumvalue = Number(sumvalue);
    if (latestPointsum[user]) {
      ret['pointsum'] = sumvalue - latestPointsum[user];
    } else {
      ret['pointsum'] = undefined;
    }
    if (update) {
      latestPointsum[user] = sumvalue;
    }

    let problems = await page.$$('.react-bs-container-body > table > tbody > tr');
    let links = await page.$$('.react-bs-container-body > table > tbody > tr > td > a');
    let saved = {};
    for (let i = 0; i < problems.length; i++) {
      let problem = await (await problems[i].getProperty('textContent')).jsonValue();
      let link = await (await links[2 * i].getProperty('href')).jsonValue();
      if (problem.match(date) && problem.match('ACdetails') && !(link in saved)) {
        ret['solved'].push({
          problem: problem.match(/^20\d{2}-\d{2}-\d{2}(.*)ACdetails/)[1],
          link: link
        });
        saved[link] = 1;
      }
    }
    browser.close();
  } catch(e) {
    console.error(e);
  }
  return ret;
}

async function notifyIfUnsolved(robot, user, message, retry) {
  try {
    if (mute[id[user]]) return;
    const today = (new Date(Date.now() + 9 * 3600000)).toISOString().slice(0,10);
    let solved = await getSolvedProblems(user, today, false);
    if (solved['solved'].length === 0 && retry > 0) {
      console.log(`retrying for ${user}`);
      notifyIfUnsolved(robot, user, message, retry - 1);
      return;
    }
    console.log(`${user} solved:`);
    console.log(solved);
    if (solved['solved'].length === 0) {
      robot.send({room: '#daily_atcoder'}, `<@${id[user]}> ${message}`);
      return;
    }
    if (solved['pointsum'] && solved['pointsum'] < 300) {
      robot.send({room: '#daily_atcoder'}, `<@${id[user]}> もうちょっとAtCoderやれ`);
      return;
    }
  } catch(e) {
    console.error(e);
    notifyIfUnsolved(robot, user, message, retry - 1);
  }
}

async function summarize(robot, user, retry) {
  try {
    const today = (new Date(Date.now() + 9 * 3600000 - 600000)).toISOString().slice(0,10);
    let solved = await getSolvedProblems(user, today, true);
    if (solved['solved'].length === 0 && retry > 0) {
      console.log(`retrying for ${user}`);
      summarize(robot, user, retry - 1);
      return;
    }
    console.log(`${user} solved:`);
    console.log(solved);
    if (solved['solved'].length) {
      message = '';
      message += `<@${id[user]}> solved *${solved['solved'].length} problem${solved['solved'].length > 1 ? 's' : ''}*!!`;
      if (solved['pointsum']) message += ` Total *${solved['pointsum']} points* (Rated only)`;
      message += '\n';
      if (user in id) {
        message += `That's *${solved['streak']}* in a row to solve problems at AtCoder!${solved['isLongest'] ? " That's a new record!!" : ''}\n`;
      }

      for (let s of solved['solved']) {
        message += `${s.problem} ${s.link}\n`;
      }
      robot.send({room: '#daily_atcoder'}, message.slice(0, message.length - 1));
      mute[id[user]] = false;
    }
  } catch(e) {
    console.error(e);
    summarize(robot, user, retry - 1);
  }
}

async function init() {
  const today = (new Date(Date.now() + 9 * 3600000)).toISOString().slice(0,10);
  for (let user in id) {
    await getSolvedProblems(user, today, true, 2);
  }
}

module.exports = robot => {
  robot.hear(/test$/, res => {
    res.send('hoge');
  });

  robot.hear(/やらない$/, res => {
    mute[res.message.user.id] = true;
  });

  !(async() => {
    await init();
  })();

  // まあ他にも各投稿について設定します
  new cron('0 9 0 * * *', () => {
    for (let user in id) {
      !(async() => {
        await summarize(robot, user, 2);
      })();
    }
  }, null, true, 'Asia/Tokyo');
}

最後に

chokudaiさんはリアルにはめっちゃ優しい人なんでこんなこと言わないです

Implicit Treap

この記事はCompetitive Programming (1) Advent Calendar 7日目の記事とISer Advent Calendar 8日目の記事として書かれました。

TL;DR

Implicit Treapを実装しました。以下の操作がクエリ毎O(logn)で可能です。

  • 配列のランダムアクセス
  • 配列の任意箇所へのinsert
  • 任意要素のerase
  • 任意区間に対するsum, max, min等のクエリ
  • 任意区間に対する加算、更新等のクエリ
  • 任意区間のreverse
  • 任意区間のrotate
  • Implicit Treap上の二分探索

この記事では一般的なTreapから順を追って説明していこうと思うのでImplicit Treapだけコピペして使いたい！という人は最後の方へどうぞ。

追記

bug fixとかをした最新の実装はここにあります。

  • [12/24] [] operatorと累積を返すクエリで長さが0になるときのバグを修正しました。

github.com

前提知識

二分探索木に関する性質は既知とします。Segment TreeやBinary Indexed Treeに関する知識（遅延評価を含める）があれば理解にはかなり役立ちますが、まあなくても読めるかなと思います。Treapは知らなくても大丈夫です。

Treap (Cartesian Tree)とは

Treapという名前はtree + heapの略で、ペア(X, Y)を格納するデータ構造なんですが、Xに関しては二分探索木、Yに関しては最大値ヒープになっているもののことをいいます。Xはkey, Yはpriorityと呼ばれます。愚直な二分探索木は挿入等の操作に最悪O(n)を要しますが、ランダムなpriorityを導入することにより確率的にO(logn)の計算量を達成しようというものです（どう活用されているかは下で説明されます）。

https://www.geeksforgeeks.org/wp-content/uploads/treap.png

Treapの操作と実装方法

search(X)

通常の二分探索木のsearchと同様です。O(logn)

split(T, X)

Treapを分割して2つのTreapを作ります。片方はX未満のkeyからなるもので、もう一方はX以上のkeyからなるものです。これは部分木に関する再帰でO(Tの深さ)で書くことができます。

void split(Tree t, T key, Tree& l, Tree& r) {
    if (!t) {
        l = r = nullptr;
    } else if (key < t->key) {
        split(t->l, key, l, t->l), r = t;
    } else {
        split(t->r, key, t->r, r), l = t;
    }
}

insert(X, Y)

通常の二分探索木の挿入の操作と同様に、key Xに注目して木を降りていくのですが、priorityがY未満になっているノードVに遭遇したらストップします。将来的にこのノードを挿入したいノードに置き換えるのですが、それにはsplit操作を用います。すなわち、Vの部分木を値Xでsplitして得られる2つの部分木をL, Rとして、Vを(X, Y)に置き換えたのち、(X, Y)の左の子の部分木をL, 右の子の部分木をRにすればよいです。計算量はO(logn)です。

void insert(Tree& t, Tree item) {
    if (!t) {
        t = item;
    } else if (item->priority > t->priority) {
        split(t, item->key, item->l, item->r), t = item;
    } else {
        insert(item->key < t->key ? t->l : t->r, item);
    }
}

merge(T1, T2)

2つのTreapをマージする操作です。これには、priorityがより高いrootを選び、その部分木に残りを再帰的にマージしていく、という再帰的な操作で書くことができます。オーダーはO(Tの深さ)です。

void merge(Tree& t, Tree l, Tree r) {
    if (!l || !r) {
        t = l ? l : r;
    } else if (l->priority > r->priority) {
        merge(l->r, l->r, r), t = l;
    } else {
        merge(r->l, l, r->l), t = r;
    }
}

erase(X)

通常の二分探索木のsearchと同様にXのkeyをもつノードVに行きます。Vの部分木全体を、Vの左と子の部分木と右の子の部分木をmergeした木で置き換えれば終了です。計算量はO(logn)です。

void erase(Tree& t, T key) {
    if (t->key == key) {
        merge(t, t->l, t->r);
    } else {
        erase(key < t->key ? t->l : t->r, key);
    }
}

Treapの実装

template <class T>
class Treap {
    xorshift rnd;
    struct Node {
        T key;
        int priority;
        Node *l, *r;
        Node(T key, int priority) : key(key), priority(priority), l(nullptr), r(nullptr) {}
    } *root = nullptr;
    using Tree = Node *;
    
    void split(Tree t, T key, Tree& l, Tree& r) {
        if (!t) {
            l = r = nullptr;
        } else if (key < t->key) {
            split(t->l, key, l, t->l), r = t;
        } else {
            split(t->r, key, t->r, r), l = t;
        }
    }
    
    void merge(Tree& t, Tree l, Tree r) {
        if (!l || !r) {
            t = l ? l : r;
        } else if (l->priority > r->priority) {
            merge(l->r, l->r, r), t = l;
        } else {
            merge(r->l, l, r->l), t = r;
        }
    }
    
    void insert(Tree& t, Tree item) {
        if (!t) {
            t = item;
        } else if (item->priority > t->priority) {
            split(t, item->key, item->l, item->r), t = item;
        } else {
            insert(item->key < t->key ? t->l : t->r, item);
        }
    }
    
    void erase(Tree& t, T key) {
        if (t->key == key) {
            merge(t, t->l, t->r);
        } else {
            erase(key < t->key ? t->l : t->r, key);
        }
    }
    
    bool find(Tree& t, T key) {
        if (!t) {
            return false;
        } else if (t->key == key) {
            return true;
        } else {
            return find(key < t->key ? t->l : t->r, key);
        }
    }
    
public:
    void insert(T key) {
        insert(root, new Node(key, rnd.random()));
    }
    
    void erase(T key) {
        erase(root, key);
    }
    
    bool find(T key) {
        return find(root, key);
    }
};

こんな感じにわりとシンプルに書けます。Treapの概要がわかったところでいよいよ本題のImplicit Treapに進みます。

Implicit Treap Revisited

Implicit Treapは、ユーザには配列のようなインターフェースを提供しますが、中身はTreapです。インデックスがkの要素に対応するNodeはkというimplicit keyをもち、Node間の大小関係はそれらのimplicit keyの大小関係として定義されます。

実は、本記事で実装されるImplicit Treapよりも機能が制限されたバージョンがC++のSTLにも存在し、ropeと呼ばれています（ext/ropeをインクルードすると使えます）。

Implicit cartesian tree in GNU C++ STL. - Codeforces

Implicit Treapにおける区間の扱い

Segment TreeやBinary Indexed Treeでは、各Nodeにその部分木についてのmin/sum等の情報を保存しました。というか各Nodeにある区間が対応付けられていました。区間に対するクエリに答える際は、その区間をちょうど被覆するようなNodeの集合を見つけ、それらのmin/sum等について計算を行うことでクエリを処理しました。

Implicit Treapでも同様の考え方をします。なんならImplicit Treapのほうがシンプルです。Implicit Treapでは区間は、あるノードの部分木として表されます。Split操作により、木を分けることが可能なので、ある区間を（Segment Treeのときのようにいくつかの区間の被覆ではなく）一つの区間としてまるごと取り出せます。すなわち、[0, N)から[L, R)を切り出したいときは、まず[0, R), [R, N)にSplitし、１つ目の部分木をさらに[0, L), [L, R)にSplitすればよいです。区間に対する処理を行った後はMerge操作を逆に行うことで、もとの木を復元できます。

区間に対するクエリを処理するためにはノードに以下の情報を新たに保存する必要があります。

cnt

部分木のノード数です。Implicit keyを求める際に重要です。Implicit keyは上述したとおり、対応する配列の要素のインデックスのことであり、Node間の大小関係がimplicit keyの大小関係と同じであることから、あるNodeのimplicit keyは、そのNodeよりも小さいNodeの個数であり、これはcntがわかっていれば簡単に計算することができます。

すなわち、ノードVのimplicit keyはcnt(V->left)と、Vの祖先PでVがPの右の子の部分木に入っているようなVの各Pについてのcnt(P->left)の和、を合わせたものとして計算できます。

これはもっと簡単に、rootからimplicit keyを計算したい目的のノードまで順に降りていき、右に降りた場合のみcnt(V->left) + 1を累積していけば求まるので、O(logn)で計算できます。

cntの値は、それらの子がすでに更新されていると仮定すると、木DPの要領で簡単に更新できます（実際Implicit Treapではあらゆる更新は葉から根の方向に向かって行われます）。

void update_cnt(Tree t) {
    if (t) {
        t->cnt = 1 + cnt(t->l) + cnt(t->r);
    }
}

acc

部分木のmin/sumなどを保存する変数です。この値も、それらの子がすでに更新されていると仮定すると簡単に求まります。

最小値クエリの場合のコードです（変数accの代わりにminを用いています）。

int get_min(Tree t) {
    return t ? t->min : INF;
}

void update_min(Tree t) {
    if (t) {
        t->min = min(t->value, min(get_min(t->l), get_min(t->r)));
    }
}

lazy

部分木に対する遅延評価を保存する変数です。つまり、ノードVについて、V->value + V->lazyが、Vの実際の値となります。ここらへんは遅延Segment Treeなどと同様です。

rev

部分木の対応する区間が反転されているかのフラグです。

区間の処理の前後

Implicit Treapではあらゆる処理の前にpushdownといって、親から子方向へ遅延評価を適用していきます。

加算クエリの場合のコードです。

void pushdown(Tree t) {
    if (t && t->rev) {
        t->rev = false;
        swap(t->l, t->r);
        if (t->l) t->l->rev ^= 1;
        if (t->r) t->r->rev ^= 1;
    }
    if (t && t->lazy) {
        if (t->l) {
            t->l->lazy += t->lazy;
            t->l->min += t->lazy;
        }
        if (t->r) {
            t->r->lazy += t->lazy;
            t->r->min += t->lazy;
        }
        t->value += t->lazy;
        t->lazy = 0;
    }
    pushup(t);
}

処理の後、pushupという関数によって親方向の情報を更新します。

void pushup(Tree t) {
    update_cnt(t), update_min(t);
}

Implicit Treapの操作と実装方法

ここまでに紹介した実装がむしろ本質です。今から紹介する実装はsplit, merge, pushdown, pushupなどの組み合わせで書かれます。

split(T, key, T1, T2)

配列Tを位置keyを区切りとして2つに分割します。すなわちT1 = [0, key), T2 = [key, n)と分割されます。操作の実体はTreapのsplitと同じです。

void split(Tree t, int key, Tree& l, Tree& r) {
    if (!t) {
        l = r = nullptr;
        return;
    }
    pushdown(t);
    int implicit_key = cnt(t->l) + 1;
    if (key < implicit_key) {
        split(t->l, key, l, t->l), r = t;
    } else {
        split(t->r, key - implicit_key, t->r, r), l = t;
    }
    pushup(t);
}

merge(T, T1, T2)

配列T1, T2をマージしてT2にします。Treapのmergeと同じです。

void merge(Tree& t, Tree l, Tree r) {
    pushdown(l);
    pushdown(r);
    if (!l || !r) {
        t = l ? l : r;
    } else if (l->priority > r->priority) {
        merge(l->r, l->r, r), t = l;
    } else {
        merge(r->l, l, r->l), t = r;
    }
    pushup(t);
}

insert(pos, X)

配列の位置posにXを挿入します。split(T, T1, T2 pos)をして配列を[0 .. pos)と[pos, n)にsplitした後、merge(T1, T1, item)をしてXをT1にマージし、最後にmerge(T, T1, T2)で配列を1つに戻します。

void insert(Tree& t, int key, Tree item) {
    Tree t1, t2;
    split(t, key, t1, t2);
    merge(t1, t1, item);
    merge(t, t1, t2);
}

erase(key)

通常のTreapのeraseと同様に実装できますが、こちらのほうがシンプルでよいと思います。要は[0, key + 1)と[ket + 1, n)に分けて、さらに前者を[0, key), [key, key + 1)に分けて、[0, key)と[key + 1, n)を最後にくっつけます。

void erase(Tree& t, int key) {
    Tree t1, t2, t3;
    split(t, key + 1, t1, t2);
    split(t1, key, t1, t3);
    merge(t, t1, t2);
}

query(L, R)

配列の半開区間[L, R)についてsum/minなどを求めます。split操作で遅延評価の更新が行われるのでそのままmin/sumなどを見ればオッケーです。

最小値クエリのコードです。

int findmin(Tree t, int l, int r) {
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    int ret = t2->min;
    merge(t2, t2, t3);
    merge(t, t1, t2);
    return ret;
}

加算クエリのコードです。

void add(Tree t, int l, int r, int x) {
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2 , t3);
    t2->lazy += x;
    t2->min += x;
    merge(t2, t2, t3);
    merge(t, t1, t2);
}

reverse(L, R)

区間[L, R)を反転します。

void reverse(Tree t, int l, int r) {
    if (l > r) return;
    Tree t1, t2, t3;
    split(t, l, t1, t2);
    split(t2, r - l, t2, t3);
    t2->rev ^= 1;
    merge(t2, t2, t3);
    merge(t, t1, t2);
}

Implicit Treapの実装

上記の機能に加え、配列のdumpやrotateを追加しています。区間クエリはmin, addに対応したものです。一般化したものは次のセクションを参考にしてください。

// for RMQ & RAQ
constexpr int INF = __INT_MAX__;
class ImplicitTreap {
    xorshift rnd;
    struct Node {
        int value, min, lazy;
        int priority, cnt;
        bool rev;
        Node *l, *r;
        Node(int value, int priority) : value(value), min(INF), lazy(0), priority(priority), cnt(1), rev(false), l(nullptr), r(nullptr) {}
    } *root = nullptr;
    using Tree = Node *;

    int cnt(Tree t) {
        return t ? t->cnt : 0;
    }

    int get_min(Tree t) {
        return t ? t->min : INF;
    }

    void update_cnt(Tree t) {
        if (t) {
            t->cnt = 1 + cnt(t->l) + cnt(t->r);
        }
    }

    void update_min(Tree t) {
        if (t) {
            t->min = min(t->value, min(get_min(t->l), get_min(t->r)));
        }
    }

    void pushup(Tree t) {
        update_cnt(t), update_min(t);
    }

    void pushdown(Tree t) {
        if (t && t->rev) {
            t->rev = false;
            swap(t->l, t->r);
            if (t->l) t->l->rev ^= 1;
            if (t->r) t->r->rev ^= 1;
        }
        if (t && t->lazy) {
            if (t->l) {
                t->l->lazy += t->lazy;
                t->l->min += t->lazy;
            }
            if (t->r) {
                t->r->lazy += t->lazy;
                t->r->min += t->lazy;
            }
            t->value += t->lazy;
            t->lazy = 0;
        }
        pushup(t);
    }
    
    void split(Tree t, int key, Tree& l, Tree& r) {
        if (!t) {
            l = r = nullptr;
            return;
        }
        pushdown(t);
        int implicit_key = cnt(t->l) + 1;
        if (key < implicit_key) {
            split(t->l, key, l, t->l), r = t;
        } else {
            split(t->r, key - implicit_key, t->r, r), l = t;
        }
        pushup(t);
    }
    
    void insert(Tree& t, int key, Tree item) {
        Tree t1, t2;
        split(t, key, t1, t2);
        merge(t1, t1, item);
        merge(t, t1, t2);
    }

    void merge(Tree& t, Tree l, Tree r) {
        pushdown(l);
        pushdown(r);
        if (!l || !r) {
            t = l ? l : r;
        } else if (l->priority > r->priority) {
            merge(l->r, l->r, r), t = l;
        } else {
            merge(r->l, l, r->l), t = r;
        }
        pushup(t);
    }
    
    void erase(Tree& t, int key) {
        Tree t1, t2, t3;
        split(t, key + 1, t1, t2);
        split(t1, key, t1, t3);
        merge(t, t1, t2);
    }

    void add(Tree t, int l, int r, int x) {
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2 , t3);
        t2->lazy += x;
        t2->min += x;
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }

    int findmin(Tree t, int l, int r) {
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        int ret = t2->min;
        merge(t2, t2, t3);
        merge(t, t1, t2);
        return ret;
    }

    void reverse(Tree t, int l, int r) {
        if (l > r) return;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        t2->rev ^= 1;
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }

    // [l, r)の先頭がmになるように左シフトさせる。std::rotateと同じ仕様
    void rotate(Tree t, int l, int m, int r) {
        reverse(t, l, r);
        reverse(t, l, l + r - m);
        reverse(t, l + r - m, r);
    }

    void dump(Tree t) {
        if (!t) return;
        pushdown(t);
        dump(t->l);
        cout << t->value << " ";
        dump(t->r);
    }
    
public:
    void insert(int pos, int x) {
        insert(root, pos, new Node(x, rnd.random()));
    }

    void add(int l, int r, int x) {
        add(root, l, r, x);
    }

    int findmin(int l, int r) {
        return findmin(root, l, r);
    }

    void erase(int pos) {
        erase(root, pos);
    }

    void reverse(int l, int r) {
        reverse(root, l, r);
    }

    void rotate(int l, int m, int r) {
        rotate(root, l, m, r);
    }

    void dump() {
        dump(root);
        cout << endl;
    }
};

verified - RMQ and RAQ

モノイドを乗せる

上のコードで、minをとっている部分とlazy関連の処理をしている箇所を変更しました。ついでにインデックスアクセスとImplicit Treap上の二分探索を実装しました。

モノイドをよくわかっていないけど便利そうなのでコピペして使いたい人へ

MonoidクラスとOperatorMonoidクラスの実装は簡単だと思います。たとえばRSQ, RUQを処理したい場合は

using T = int;

struct SumMonoid {
    static constexpr T id() {
        return 0;
    }
    static T op(T a, T b) {
        return a + b;
    }
};

struct UpdateMonoid {
    static constexpr T id() {
        return 2e18;
    }
    static T op(T a, T b) {
        return b;
    }
};

と定義すればよいです。問題はModifierですね。上の２つは使い回しが可能ですが、Modifierは区間のデータに対するクエリと区間更新に対するクエリの組み合わせによって変わります。Modifierがそもそも何を計算するかというと、accのデータが、遅延の差分(lazy)によってどう変化するかを計算します。

今の場合Modifierは以下のようになります。

struct Modifier {
    // lazyの結果によってaccがどう変わるか。szは部分木のサイズ
    static T op(T a, T b, int sz) {
        return b == UpdateMonoid::id() ? a : b * sz;
    }
};

なぜなら、区間を表しているTreeがあって、その区間がbに更新されているとすると、その区間のsumは、b * 区間のサイズ（つまりTreeのサイズ）となるからです。SumMonoidやUpdateMonoidはコピペで使えますが、Modifierは毎回自分で考え直すようにしましょう。

template<class Monoid, class OperatorMonoid>
class ImplicitTreap {
    xorshift rnd;
    struct Node {
        T value, acc, lazy;
        int priority, cnt;
        bool rev;
        Node *l, *r;
        Node(T value, int priority) : value(value), acc(Monoid::id()), lazy(OperatorMonoid::id()), priority(priority), cnt(1), rev(false), l(nullptr), r(nullptr) {}
    } *root = nullptr;
    using Tree = Node *;

    int cnt(Tree t) {
        return t ? t->cnt : 0;
    }

    T acc(Tree t) {
        return t ? t->acc : Monoid::id();
    }

    void update_cnt(Tree t) {
        if (t) {
            t->cnt = 1 + cnt(t->l) + cnt(t->r);
        }
    }

    void update_acc(Tree t) {
        if (t) {
            t->acc = Monoid::op(acc(t->l), Monoid::op(t->value, acc(t->r)));
        }
    }

    void pushup(Tree t) {
        update_cnt(t), update_acc(t);
    }

    void pushdown(Tree t) {
        if (t && t->rev) {
            t->rev = false;
            swap(t->l, t->r);
            if (t->l) t->l->rev ^= 1;
            if (t->r) t->r->rev ^= 1;
        }
        if (t && t->lazy != OperatorMonoid::id()) {
            if (t->l) {
                t->l->lazy = OperatorMonoid::op(t->l->lazy, t->lazy);
                t->l->acc = Modifier::op(t->l->acc, t->lazy, cnt(t->l));
            }
            if (t->r) {
                t->r->lazy = OperatorMonoid::op(t->r->lazy, t->lazy);
                t->r->acc = Modifier::op(t->r->acc, t->lazy, cnt(t->r));
            }
            t->value = Modifier::op(t->value, t->lazy, 1);
            t->lazy = OperatorMonoid::id();
        }
        pushup(t);
    }
    
    void split(Tree t, int key, Tree& l, Tree& r) {
        if (!t) {
            l = r = nullptr;
            return;
        }
        pushdown(t);
        int implicit_key = cnt(t->l) + 1;
        if (key < implicit_key) {
            split(t->l, key, l, t->l), r = t;
        } else {
            split(t->r, key - implicit_key, t->r, r), l = t;
        }
        pushup(t);
    }
    
    void insert(Tree& t, int key, Tree item) {
        Tree t1, t2;
        split(t, key, t1, t2);
        merge(t1, t1, item);
        merge(t, t1, t2);
    }

    void merge(Tree& t, Tree l, Tree r) {
        pushdown(l);
        pushdown(r);
        if (!l || !r) {
            t = l ? l : r;
        } else if (l->priority > r->priority) {
            merge(l->r, l->r, r), t = l;
        } else {
            merge(r->l, l, r->l), t = r;
        }
        pushup(t);
    }
    
    void erase(Tree& t, int key) {
        Tree t1, t2, t3;
        split(t, key + 1, t1, t2);
        split(t1, key, t1, t3);
        merge(t, t1, t2);
    }

    void update(Tree t, int l, int r, T x) {
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2 , t3);
        t2->lazy = OperatorMonoid::op(t2->lazy, x);
        t2->acc = Modifier::op(t2->acc, x, cnt(t2));
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }

    T query(Tree t, int l, int r) {
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        T ret = t2->acc;
        merge(t2, t2, t3);
        merge(t, t1, t2);
        return ret;
    }

    // [l, r)の中で左から何番目か
    int find(Tree t, T x, int offset, bool left = true) {
        if (Monoid::op(t->acc, x) == x) {
            return -1;
        } else {
            if (left) {
                if (t->l && Monoid::op(t->l->acc, x) != x) {
                    return find(t->l, x, offset, left);
                } else {
                    return (Monoid::op(t->value, x) != x) ? offset + cnt(t->l) : find(t->r, x, offset + cnt(t->l) + 1, left);
                }
            } else {
                if (t->r && Monoid::op(t->r->acc, x) != x) {
                    return find(t->r, x, offset + cnt(t->l) + 1, left);
                } else {
                    return (Monoid::op(t->value, x) != x) ? offset + cnt(t->l) : find(t->l, x, offset, left);
                }
            }
        }
    }

    void reverse(Tree t, int l, int r) {
        if (l > r) return;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        t2->rev ^= 1;
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }

    // [l, r)の先頭がmになるようにシフトさせる。std::rotateと同じ仕様
    void rotate(Tree t, int l, int m, int r) {
        reverse(t, l, r);
        reverse(t, l, l + r - m);
        reverse(t, l + r - m, r);
    }

    void dump(Tree t) {
        if (!t) return;
        pushdown(t);
        dump(t->l);
        cout << t->value << " ";
        dump(t->r);
    }
    
public:
    ImplicitTreap() {}
    ImplicitTreap(vector<T> as) {
        ::reverse(as.begin(), as.end());
        for (T a : as) {
            insert(0, a);
        }
    }

    int size() {
        return cnt(root);
    }

    void insert(int pos, T x) {
        insert(root, pos, new Node(x, rnd.random()));
    }

    void update(int l, int r, T x) {
        update(root, l, r, x);
    }

    T query(int l, int r) {
        return query(root, l, r);
    }

    // 二分探索。[l, r)内のkでMonoid::op(tr[k], x) != xとなる最左/最右のもの。存在しない場合は-1
    // たとえばMinMonoidの場合、x未満の最左/最右の要素の位置を返す
    int find(int l, int r, T x, bool left = true) {
        Tree t1, t2, t3;
        split(root, l, t1, t2);
        split(t2, r - l, t2, t3);
        int ret = find(t2, x, l, left);
        merge(t2, t2, t3);
        merge(root, t1, t2);
        return ret;
    }

    void erase(int pos) {
        erase(root, pos);
    }

    void reverse(int l, int r) {
        reverse(root, l, r);
    }

    void rotate(int l, int m, int r) {
        rotate(root, l, m, r);
    }

    void dump() {
        dump(root);
        cout << endl;
    }

    T operator[](int pos) {
        Tree t1, t2, t3;
        split(root, pos + 1, t1, t2);
        split(t1, pos, t1, t3);
        T ret = t3->acc;
        merge(t1, t1, t3);
        merge(root, t1, t2);
        return ret;
    }
};

verified - 1508

参考文献

Treap - Competitive Programming Algorithms

maze0123さんの実装です。 github.com

github.com

追記

update_accを演算が可換でないときにも対応できるよう修正しました。noshi91ありがとうございます。