クマーの競プロ精進日記

AtCoder赤とICPC World Final目指して頑張ります．競プロ自戦記、アルゴリズムなどについて

ICPC2021国内予選・チームSPJ視点

上位23チーム中唯一Dが解けず，ABCEFという摩訶不思議な5完で敗退したあの敗戦から1年．今年もこの季節が来た．さすがに去年は3人とも競プロ歴が浅くて勝てるとは思っていなかったが，今年は十分にチャンスがあると3人とも確信していたと思う．

チームメンバー

つちのこ (AtCoder: nok0 - AtCoder (黄), Codeforces: nok0 - Codeforces (濃橙, max: 薄赤))

twitter.com東大教養学部2年(工学部物理工学科内定)．アカウント名はノックゼロと読む．タイピングがチームで最も速く，主に重実装問題を担当する．私が「大丈夫？ほんとに1人で通せる？まじで？？」とめちゃくちゃ心配するような重い実装問題でも颯爽と書き上げてノーペナで通すすごい人．3人の中ではTwitter上で一番名前が知られてそう．いつもA問題をやる．

 

zkou (AtCoder: zkou - AtCoder (黄色, max: 橙), Codeforces: zkou - Codeforces (薄橙))

twitter.com東大教養学部2年(工学部計数工学科内定)．本人はゼットコウと読まれるのを想定していたそうだが，皆ずこうと読んでいる．チーム内で唯一メイン使用言語がPython．天才構築問題がかなり得意だがICPCにあまり出ないのが辛いところ．構築以外でも何かと天才性を発揮するのであまり実装には参加せずに考察を詰める役割．この人とつちのこが協力して数え上げをやると仕事が本当に速い．いつもBをやる．

 

クマー (AtCoder: Kite_kuma - AtCoder (橙), Codeforces: Kite_kuma - Codeforces (薄赤))

twitter.com

東大教養学部2年(工学部計数工学科内定)．筆者．3人の中で最もAtCoderのレートが高く，かつコンテストの爆死が最も少ないので一応安定枠っぽい感じの人．構文解析と幾何を担当する(できるとは言っていない)．構文解析は他の２人も書けるけど幾何をできるのが私しかいないので幾何が出るとぼっちになりがち．いつもCをやろうとするものの，実装がめんどくさくて結局つちのこに投げることも多い．じゃあ何ができるんですか？知りません…

 

 

開始前．3限の授業を終えて事前にお願いして借りていた教室に移動する．15時から20時まで貸切．

 

セットアップ作業を終えてもまだ開始まで結構時間があるので，それぞれ喋ったり寿司打をしたり音ゲーをしたり寝たりして思い思いに過ごす．緊張感が高まってくる．今年も不必要に東大の層が厚いので，抜けられるかどうかはちょうど半々くらいかなあとぼんやり思っていた．東大なら通過には10位以内がほぼ必要十分条件と言っていい．去年は東大のとあるチームが12位で許されていたが，かなりレアケースと考えてよさそうだ．

 

開始．つちのこがA，zkouがB，私がCを読む．ABを2人がサッと通す．あとで見返したら最速の2完だったらしい．これは余裕がありそうだと思いつつCを考えたがなんやこれとなる．構文解析は私の担当なのでとりあえずパースして木を作る．他の2人はCよりも正解者が多いDに行っている．まだパースが終わっていないが，Dが有名問題っぽいのに落ちたというので見てみる．2分割なら有名なNP完全だよねという話をしたらつちのこが トータルで50^5くらいのDPを思いついたので解決．私はCに戻る．Cのパースが終わり，やばそうな全方位木DPが思い浮かんだもののCでそんなめんどくさい問題でるのか？と思って別の方針を考えた．結局ひとまずO(N^2)の木DPを書いて自分のPCの速度に頼る方針に走った．書きあがったものの実行が全然終わらない．そうこうしているうちにDが通る．順位はこのとき7位とかだった気がする．Cがやっぱり全然終わらない．全ケース合わせると 6 \times 10^{10}くらいの計算量なのでまあ確かに遅そうだとなる．やはり全方位木DPしかないかとなる．zkouと一緒に実装を詰めるとなんとノーバグでサンプルが通る．おそるおそる出すとAC．自分の全方位木DPが古いライブラリだからあまり信用できずドキドキした．ひとまずノーペナで4完できたという事実を前にして落ち着いてくる．順位表を見ると上位のチームでCとEを通している割合が半々くらい．やはり今年も前半から結構辛い問題が並んでいるのだなと認識する．Eがもう書くだけだというのでFに行く．Fを見たら完全マッチングで，最近授業で習ったDM分解がすぐに思い浮かぶ．EがWrong answerになる．すぐつちのこが訂正して，投げる．Wrong answerになる．さすがにまずいとなって3人で一緒にデバッグをする．細かく修正しつつ慎重にコードの正当性を確認して，投げる．AC．この時点で8位，残りが80分．これで終わったらどれほど楽か…．F~Hはどのチームにも通されていない．改めてFを見る．やはりDM分解で解けそうということになる．解法が詰め切られていないままつちのこがDM分解を実装する．zkouがそれを横からチェックする．私は最後にどうやったら全体を強連結にできるかのアルゴリズムを考える．意外とできない．引き続き考える．考える．たぶんここは落ち着いてやればそこまで難しくないパートなんだろうが，時間の切迫を感じて頭が舞い上がっている中で私は必死で考えていた．思いついた．zkouに確認して書き始める．残り時間が40分ほどしかなく，とても少ない．とにかく全力で書いた．つちのこのコードを繋げて動くか確認する．Segmentation fault を何度か潜り抜けて，サンプルの結果が合う．あとは投げるだけ．残りが2分ほどしかなく，ほぼラストチャンス．Wrong answer．懸命にバグを探すが見つからない．19時31分．終わった．Eを通して以降見ないことにしていた順位表を見る．11位．上には東大の4チーム．椅子から転げ落ちて，地面に倒れ込んだまましばらく動けなかった．

 

 

 

起き上がって順位表を見る．

f:id:kumakumatime:20211106003808p:plain

10位との差は900秒程度．15分…挽回のチャンスはあっただろうか．Cで愚直実行をやろうとしなければ，全方位木DPのライブラリがもう少し便利な仕様であれば(上には書いていないが，このせいで少し手間取った)，Eのペナ１つ目で私が介入できていれば，授業でやったDM分解のライブラリを持っていれば，そもそも10位以内の他のチームが１つでもいなければ…．タラレバを並べても仕方がないのだが，この結果はあまりに非情なものに感じられた．

 

順位表を見つめたまま放心状態の私を前にしてzkouとつちのこが帰る支度を始める．リロードしたら順位が変わるんじゃないかとか，そんなバカなことを考えながら何回かF5を押し，結果の変わらない画面を見届けてからPCをシャットダウンした．

 

さすがに今日は何か旨い物でも食うかとなる．結局大学前にあるハンバーグステーキの店に入って，いい肉を食べてお腹一杯になった．

 

寮に帰ったら他の寮生が気を遣ってくれてとてもありがたかった．悔しい負け方をしたときって自分一人でいるときは何とも思わないけど，直接対戦に関わっているわけではない人に優しくされると胸が一杯になってしまう．将棋の全国大会の決勝で負けて泣いたあの日以降，あんな思いは二度としたくないと思ったけど，またそんなときが来るとはな．覚えてろよマジで．

橙

 

橙達成しました。先週だけど。今晩のARCで黄落ちする可能性あるので今のうちに色変記事書きます。

 

このブログの概要欄に「AtCoder橙目指して頑張ります！」って書いてあるんですが、もう達成しちゃいましたね。まだあまり実感がないし、意外とあっさり行くもんだなという感想です。概要欄は…「赤色目指し頑張りましょう」とでも変えておきましょうかね。

 

橙嬉しいんですけど、黄色になったときほどうれしくはないかな～とか言ってたらその日一睡もできなくてびっくりしました。いやどんだけ嬉しいねん。

 

精進記録

f:id:kumakumatime:20210516124520p:plain

 

知らない間に結構解いてますね。黄色達成時のグラフ見たら分かるんですが、黄～橙帯の埋まりが全く違います。赤はもうちょっと解いてる印象だったけど、まだ少ないですね。そもそも問題数がめちゃくちゃ多いんですが。

 

解説ACは黄色になって以降はした記憶がありません。１問だけやったのは強く覚えていますが…。もっとも、新たにアルゴリズムを学ぶ時の練習問題としてやったり、Twitterでヒントを見たりした結果ACできたものもあるので、そういうのを含めるともう少し他力ACは多いです。

AtCoderではデータ構造とかアルゴリズム知識で殴る問題はあまりないので、解説は全く見ずにうんうん唸ってればいいのではと思っています。

 

黄色と橙の残りを解きたい気持ちもありますが、残ってる十数問はどれも一生分かる気がしないものばかりで、どうしたものか。解説ACしない縛りでやってきたけどさすがにそろそろ降参してもいい気がしてきた。いや、でもこれはもうちょっと考えます。

 

 

橙にもなると競プロコミュニティでも相当上位みたいで、そろそろ発信とかする側の人間なのか？という思いはあります(とはいえ、気持ちはまだ競プロ歴１年ちょいの新人ですが)。作問などは全くやったことがないので挑戦してみようかな。いつかAtCoderに問題を提供したりして恩返ししたいですね。いやその前に進振りあるんですが。頑張ろ…。

AtCoder Grand Contest 050-D Shopping 解説


注意：以下 AtCoder Grand Contest 050-D Shopping のネタバレを思いっきり含みます. というかネタバレそのものです.

 

 

 

・問題

atcoder.jp

・計算量

公式解説のO(N^6)ではなくO(N^4)の解法です. 6乗を許しているのはわざとなんでしょうか. りんごさんが４乗の解法を見落とすのか？という疑問があります.

 

 

 

・解説
i := まだ商品を受け取っていない人数

k := 今から商品を選ぶ人が左から何番目か (i 人中)

l := 現在何ターン目か (1, 2,\cdots , N番の人が操作を行うことを１ターンとする)

とする。このときdp_{i,j,k,l}を、i 人中左から j 番目の人が商品を受け取れる確率として定義する. 特に {i\lt N-K} ならば dp_{i,j,k,l}= 0 である.


残りの商品の数が(K-(N-i))個、今から商品を受け取る人(i 人中 k 番目の人) がまだ調べていない商品の数が(K-l)個なので、k 番目の人が商品を即受け取れる確率は \frac{K-(N-i)}{K-l}. 受け取る場合とそうでない場合について、場合分けしてメモ化再帰で回せばよい.

 

 

・コード例

atcoder.jp

第４回PASTを解いてみた

ネタバレ防止でここに。受験したわけじゃないです。

 

f:id:kumakumatime:20201110182218p:plain

 

 

 

所要時間約３時間で全完。前回は確かMNOが解けずに82点だったから、成長したねえ。

前回はまだ水色だったから、まあ妥当な伸び方なのかな。

 

おもしろかった問題を抜粋。

 

I.ピザ

lowerboundでグダグダ書いたけど尺取りがよかったぽい。

 

J - ワープ

これ好き。全然分からなかった。色々場合分けした末に超頂点解法にたどり着いて、そりゃそうだ…となり。

 

M - 筆塗り

経路短縮してない嘘解法を通してしまった疑惑あり。500msくらいしかかかってないから実は正解なのかもしれないけど、ちょっと怪しい。

 

N - マス目の穴埋め

縦横固定なのは何か理由があるんですかね（計算量のオーダーがバレにくい？）。幅が狭いところを状態に持ってDPするのはこの前の国内予選Eでもありました。

 

O - 宝箱

なんか良く分からないままセグ木２本でゴリ押しました。大してバグらなくて幸運でした。セグ木なんて非競プロer受験者に優しくないし、何か別のマシな解法があるような気もする。→解説見た。グラフ？！天才！

 

 

ICPC2020国内予選参加記

 

線型代数の授業を欠席してまで過去問を解いて調整した今日のICPC。東大ボーダーきつすぎだけど最善を尽くそう。

 

…リロードしてもページが表示されない。え？となりとりあえずコーチから伝えられていた電話番号に連絡するも繋がらない。

えこれもしかしてunratedですか→16:39に突然復活して、バタバタと開始。その分終了時刻も10分後ろ倒しになった。

 

A, B: 略。それぞれつちのことzkouがやってくれた。

 

C: 自分の担当。いきなりちょっと詰まった。ポラード・ロー法とかいろいろやった末に、結局愚直探索で15分くらい回してAC…。

これ想定解なんなんですかね。まあ愚直探索回したときは気持ちが冷え冷えでしたが、なんとかノーペナACできてほっとしました。

 

D: 構文解析はzkouの担当。…なのだが良く分からず。３人集まってもやはり良く分からず。そのうちにEの考察が進んで、気付けば３人ともDを飛ばしていた。

 

E: 30列あるからbitDPすらできない…？と思ったが縦に見れば15行だよとzkouが教えてくれる。賢い。そこから (2^15)^2は簡単に分かったが、そこからzkouがゼータ変換を利用するという発想に至ったのが速かった。zkouすげーーーーー(天才)。

ここからは私とzkouで同時コーディング。いでよ、VSCodeLiveShare！！

 

qiita.com

 

処理を関数化して分けつつ、二人で別のパートを実装したらバグりまくり。私のパートもzkouのパートもしっかりおかしかった。結局デバッグだけで50分くらい使ったのかな？終了10分前に大事なバグに気付いて、サンプルが合ったーー！！！！と思って提出したらAC。デバッグ消し忘れたせいで大変面倒なことになったけど、まあOK。

 

 

F: 問題見てないけど、私とzkouがEで悶絶してる間につちのこが１人で通した。普通に難しい問題だったらしい。つちのこすげーーーーーー（天才2）。なんか永続Unionfind使ったそーな。なんですかそれは。

 

D: EFを終わらせてこちらに戻ったのが終了１０分前。これどうやって解くんだろうねーってみんなで話し合ってた。このテスト後に解法を見て、３人で絶叫…。解けたじゃん…。

 

 

というわけで5完23位、予選落ちです。落ち着いて見ればDが簡単だっただけに、CでグダったのとEでめっちゃバグったのが痛いけど、それも含めて実力かなあ。あとほんの少し運か実力が備わっていれば行けた気がする。悔しいな。

 

まあしかしチームはみんなB1だし、たぶんめちゃくちゃ伸びしろあるチームだと思う。来年はアジア地区行くぞ！

 

 

学んだアルゴリズム/データ構造/数学定理などを記録していく

タイトルの通りです。学びがあるたびに更新していきます。

 

 

2020/10/20 : Euler tour

atcoder.jp

以前から存在自体は知っていたが初めて利用した。DFS順に木の頂点や辺を配列に埋め込むことで、LISや頂点間距離などをセグ木を用いて求めたりできる。

この問題はその延長線上にある問題。初めて解説を見たときは意味が分からなかったが、理解した今見るとやるだけにも見える。Euler tourの練習問題みたいな問題だと思った。

 

 

2020/10/24 : Hallの定理

atcoder.jp以前から知ってはいたが実際に問題で使ったのはこれが初めて。今見るとどう見てもこの定理を使いそうな問題なのに、慣れてないと意外に気付かないもんですね。ってか忘れてた。

 

 

2020/10/31 : ラグランジュ補完

atcoder.jp

大学受験生時代に何かの模試でラグランジュ補完を見た気がするが、当時は自分が使うには高級すぎる概念だと思ってパスした記憶がある。今見るとめっちゃ大事やんとなる。これまで飛ばした多項式の問題が2-3問くらい解けそう。

 

 

2020/11/25 : O(N^3)に見せかけてO(N^2)になってるやつ(呼び方不明 更新: "2乗の木DP"と言われるらしいです)

 

atcoder.jp

atcoder.jp

呼び方不明だが、黄埋めをしていたら似たような考え方を用いる2問に遭遇した。初見だとかなりO(N^3)に見えてしまうのでメモ。

2問とも部分ごとの探索結果をマージしていく。サイズがA, Bである2つの部分の結果をマージするのにO(AB)かかるので一見O(N^3)かかるが、よく考えるとO(N^2)であることがわかる。気付いてしまえばどうということはない計算量解析だがうっかりしやすいと感じた。

 

 

2020/12/09: 最大正方形/最大長方形

 

onlinejudge.u-aizu.ac.jp

onlinejudge.u-aizu.ac.jp

atcoder.jp

いずれも計算量はグリッド面積に対して線型。

最大正方形: えっこんな簡単なDPで解けるんですか？

最大長方形: 蟻本に載ってたヒストグラム中の最大長方形に帰着するのは盲点だった。

 

 

12\19 高速きたまさ法

yosupo.hatenablog.comk項間線型漸化式の第n項をO(k^2 * logn)で求める。行列累乗ならO(k^3 * logn)だが、さらに高速に行えるという話。行列累乗だと行列の中身がスカスカになるのでコストが削減できないかなあと思ったことはあったが、このアルゴリズムはその具体的な手法を与えている。漸化式の線型性をうまく利用しているという印象。

 

atcoder.jp

これを使うと↑が解ける。実装めんどくさい。

 

2021/01/28 グラフの橋と関節点(Lowlink)

灘校パソコン研究部部誌2014「競技プログラミングで使えるグラフ理論の基本」

www.npca.jp

ARC111-Dにも応用できる考え方らしい。

「DFSの探索中に探索済みの頂点が出てきたらそれはDFSで取り出した全域木における先祖か子孫」はDFSの良い性質なんだなと思った。

 

verify用はこれ。

onlinejudge.u-aizu.ac.jp

onlinejudge.u-aizu.ac.jp

 

2021/01/29 並列二分探索

 

atcoder.jp

atcoder.jp

M回の操作列の途中で初めて~~なのはいつ？などのクエリが複数個ある際の二分探索。クエリごとに下界と上界を持ち、操作列を１回回せば１つの二分探索と同じ要領でクエリごとの答えの範囲(上界-下界)が半分になる。１回の操作にかかる計算量はO(M+Q)なので、全体として計算量はO((M+Q)logM)。

 

2021/02/08 ブルーフカ法

最小全域木を求めるアルゴリズム。プリムとクラスカル以外にもあるんですね。その時点での連結成分ごとに外へつながる辺のうち最もコストが小さいものを選び、それを小さい順にクラスカル法の要領でつないでいく。

クラスカル法に比べると無駄に複雑なことをやっているように見えるので、使う機会はないと思っていたのだが、「全ての辺の重みを調べきれないが、連結成分から伸びる辺のうちコストが最小の辺を調べられる」場合はこれが有効になる。

 

atcoder.jpちなみに非想定。

 

 

2021/02/24 プリューファーコード・ケーリーの公式

 

atcoder.jp

頂点ラベルあり・辺ラベルなしの木は、n^(n-2)通り存在する(n: 頂点数)。かなり非自明な公式。プリューファーコードと１対１に対応していることを用いる証明が簡単。上の問題もこの応用で解く。

青から黄になるために学んだアルゴリズムたち

色変記事でも書いたように、私が一番アルゴリズムを学んだのは青になってからです。青以降の期間が競プロ歴の7割くらいなので、当たり前かもしれませんが。

 

chokudaiさんのブログには

水色や青あたりで、競技プログラミングで必要な知識はほぼ揃ってしまうので、そこから先は応用力の違いになってきてしまいます。

と書いてあるのですが、個人的な感覚だと青になってからの方が学んだアルゴリズムが圧倒的に多いです。ABCは茶や緑くらいの人でも理解できるアルゴリズムを組み合わせて解く問題が多いので、高度なアルゴリズムを知らなくても青になれてしまうというのはあると思います。

 

しかし黄色になる、あるいはそれ以降のレベルで戦うには知識が足りないことは自覚していたので、夏休みに入ってからはひたすらアルゴリズムを勉強しました。

 

せっかくなので自分が何を勉強したか振り返ってみたいと思います。アルゴリズムを解説できる腕はないので、参考資料のリンクを紹介しておきます。

 

ところでライブラリをコピペするかどうかという話がよく議論になりますね。私はコピペに否定的だったのですが、今はどちらかといえば肯定的に考えています。だってめんんどくさいじゃん遅延セグ木などのライブラリは定数倍高速化の価値がそれなりにあり、言語仕様やアルゴリズムの内容に精通しないと自力で速いコードを書くことは難しいと思うからです。また競プロで問題を解く上ではデータ構造の内部処理に詳しくなってもあまり意味がなかったりするのも理由です。

 

ただしライブラリを自分で書けば実装力がつきますし、オンサイトなどでコピペできない大会もありますから、いずれ自分で全て書いてみたいなあとは思っています。

 

それでは紹介に移ります。ダイクストラとかUnionFindとか、簡単すぎるものは除きます。アルゴリズム名などはカタカナだったりアルファベットだったりしますが、執筆者の気分です。

 

 

 

数学系

ユークリッドの互除法・不定方程式

拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita

mod逆元もこれでできます。非再帰実装で何が起こっているのか、正直よく分かっていません…。

 

FFT/NTT

競プロのための高速フーリエ変換

FFT（高速フーリエ変換）を完全に理解する話 - Qiita

 

畳み込みで殴るの最高！

…FFTは数式だけは辛うじて追えているものの、なぜ畳み込みができるのかという本質部分についてはあまり理解できていません。今のところ「離散フーリエ変換をごちゃごちゃすると、たまたま畳み込みの形に帰着されるからできる」みたいな認識で終わってます。

NTTについては完全未履修で、ライブラリだけ持ってます…（おい）

 

エラトステネスの篩 / osa_k法

osa_k法、「おさ・けーほう」って読んでるけどいいんでしょうか。エラトステネスの篩なんて小学生の頃から知ってるわ…と思って軽視していたのですが、osa_kはABC177E-Coprimeの解説を見て初めて知りました。(当時は素数列挙してその中で試し割り、という冷や汗解法で通しました)

 

Floor sum

サーバル「ALPC C『floor sum』を解いたよ。問題は、「直線 y=(Ax+B)/Mの下にある格子点の個数を求めよ」になるよ。境界を含むか含まないかには注意してね。後で話を簡単にするために左右を反転して考えることにしておくよ」 pic.twitter.com/fZvOZyOWPu— 競技プログラミングをするフレンズ (@kyopro_friends) 2020年9月10日

 

 

 

 

ACLに入ってて、なにこれとなりました。普通にあたまいい。ABC-Eに出たら「は？」って言いながらググります。

 

幾何

幾何テンプレート(Geometry) | Luzhiled’s memo

Luzhiled's memoは神。Luzhiledってなんて読むのか分からないけど。Counter Clockwise (CCW) 関数を設けるのがコツで、点の位置関係の把握に困りにくくなるみたいです。

最近点対とかは普通に難しいので、個別に調べました。（最近点対についてはwikipediaが分かりやすかったです） 

 

写像12相

「写像12相」を総整理！ 〜 数え上げ問題の学びの宝庫 〜 - Qiita

 

安心と信頼のけんちょんさんクオリティ。AOJで全部verifyできます。

こうして見ると、単純な数え上げ問題でも知らないことってたくさんあるんだなーと感じました。

 

 

離散対数・平方剰余

整数論pdfにあるやつです。難しい…。

 

ミラー・ラビン素数判定法 / ρ法

ミラー–ラビン素数判定法 - Wikipedia

「え？これってO(√N)じゃないの？」ってなるやつです。なんか良く分かんねえけどすげええええ！！！！！

余談ですが、この前のACLコン1-BではO(√N)が間に合わないと勘違いをして、このライブラリを貼っちゃいました。

 

 

グラフ

最大流（Dinic）/ 二部マッチング / 燃やす埋める

Dinic法 - tkw’s diary

これとFord-Fulkerson法がよく紹介されているのですが、DinicがあればFord-Fulkersonって要らないよね？と信じています。間違っていたらどなたか教えて頂きたいです。

Dinicは基本的に計算量がO(E*V^2)で、二部グラフだったり辺の容量が全て同一だったりする場合はO(E√V)、という説明がよくありますし、大半の問題はそれに合わせて作られています。ただ実際投げてみると最悪ケースで10^8付近になるかな？という場合でも余裕で間に合ったりするので、アルゴリズムの説明でよく言われる「ただし、ほとんどの場合でさらに高速に動作する」という文言は結構信頼できる気がしています。

 

燃やす埋めるに関しては、友達に貰ったライブラリで勉強しました。辺の張り方は落ち着いてやらないと間違えるので、あらかじめライブラリの形で持っておくのが良いと思います。

 

木の直径

D - 高橋くんと木の直径：解説スライドにアルゴリズムの説明があります。

 

実はこれ青になってから初めて知りました。アルゴリズムもダイクストラ2回で終わるから楽ちん。

木構造の問題で、直径を伸ばして考えると答えにすんなり辿り着くことは結構よくある印象です。

 

Lowest Common Ancestor (LCA)

D - 閉路：解説スライドにアルゴリズムの説明があります。

 

ダブリングです。オイラーツアーはさわりくらいしか知りません。

 

 

強連結成分分解

目指せグラフマスター

強連結成分分解＆トポロジカルソート

 

アルゴリズムが胡散臭いランキング1位（個人の感想）です。有向グラフの到達可能性を調べる際は便利だったり。でも使わなくても意外に解けちゃったりします。

 

セグ木系

Binary Indexed Tree (BIT, Fenwick Tree)

Binary Indexed Tree のはなし

セグ木は水色で勉強しましたが、BITは青になるまで使ったことがなかったです。区間和くらいでしか使えないけど、実装軽くて嬉しい！

区間加算点取得・区間加算区間取得も上のリンクを参考に作りました。

 

非再帰非２冪抽象化遅延伝播セグ木

非再帰セグ木サイコー！一番すきなセグ木です

セグ木のお勉強を敬遠している人へ - えびちゃんの日記

セグメントツリーの抽象化（C++）

Segment Tree のお勉強(1) | maspyのHP

Segment Tree のお勉強(2) | maspyのHP

 

遅延セグ木、載せられる条件も含めて難しい…。解説記事を書こうとしたこともありましたが、他の方より良く説明できる自信がなく、断念しました。

maspyさんの記事にある図が分かりやすいので、それをじっくり眺めるのがおすすめです。

２冪にした方が二分探索しやすいという説があり、ライブラリを書き換えるか迷っています。でもACLあるからいっか。

 

 

文字列

Rolling Hash

蟻本片手に学ぶアルゴリズム ~ローリングハッシュ~ - Qiita

安全で爆速なRollingHashの話 - Qiita：この記事めちゃくちゃ引用されてる印象があります。分かりやすい。

衝突回避のために以前はハッシュを2~3個tupleにして持っていたので面倒な印象でしたが、mod(2^61-1)のものを作ってからは一躍文字列問題の主力選手に。しかしこれでも基数が小さすぎると普通に衝突します（１敗）。基数は10000以上にしましょう。またそもそも文字列ごとに基数をランダムで変えてたりすると一致判定として全く意味をなさないです（１敗）。

 

Z-algorithm

配列解析アルゴリズム特論文字列探索・比較（１）- 東京大学医科学研究所ヒトゲノム解析センター（兼）情報理工学系研究科コンピュータ科学専攻

：ゲノム解析をしている研究室で使われたpdfのようです。文字列アルゴリズムってそういうところで使えるんですねなるほど。

 

マジでこれ頭いいですよね。計算結果をうまく使い回すと部分連続文字列が接頭辞とどのくらい一致しているのかが線形で全部判定できるんですね～。

色んなサイトを見て首を傾げた後で上のリンクにたどり着き、全貌を理解したときは感動しました。

 

 

その他テクニックなど

集合とその部分集合をO(3^N)で列挙するbitDP

ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary

これはO(4^N)でしかできないと思ってましたが、遷移式を工夫するとO(3^N)になるみたいです。N==15くらいの問題は割とこれだったりします。

 

包除原理・高速ゼータ変換・高速メビウス変換

包除原理-解ける数え上げの範囲を広げよう：高速ゼータ変換・高速メビウス変換も載っています。

FFTが難解だったこともあり高速ゼータ変換の勉強をこれまで避けていたのですが、コードを見てみると数行しかなくて拍子抜けしました。N==20くらいでO(3^N)も厳しかったらこれのことが多いです。（制約エスパー、楽しい！）

 

Sliding Window Aggragation (SWAG)

Sliding Window Aggregation - data-structures

区間集合 [L_i, R_i) (i = 0, 1, 2, ... ) が L_i <= L_(i+1) && R_i <= R_(i+1)を満たしていて、かつ区間に対する演算が結合則を満たすとき、これを使うと線型時間で区間クエリを処理できます。特に全部の区間の幅が一定の時は左端でソートすればこれが使えます。ただこれ最悪セグ木に載せればO(NlogN)になるんですよね。定数倍がきついときにどうぞ。

 

入力マクロ

宣言と入力を同時に行うマクロです。超便利です。宣言だけして入力を忘れるおっちょこちょいさん（私など）におすすめ。

 

デバッグマクロ

printデバッグって提出前に出力部分を消さないといけないし、コンテナの中身を見るにはループを回して要素を取り出していかないといけないからめんどくさい。

そんな悩みを解消するのがデバッグマクロです。#ifdef LOCALを付けることで自分の環境でのみデバッグ出力されるようになります。つまりマクロ部分を消さなくても、AtCoder上ではデバッグ出力が表示されません！

このマクロについては個人的に色々工夫したので別記事で紹介するかもしれません。

 

 

 

以上です！本当は「これから学びたいアルゴリズム」の欄も作るつもりだったのですが、意外に長くなったのでここで一旦終わろうかと思います。もし書くとしたら別記事に書きます。