Policy Based Data Structures
この記事はCompetitive Programming (2) Advent Calendar 2018およびISer Advent Calendar 2018 1日目の記事です。
CodeForcesやTopCoderで海外勢がよくヘッダーに
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
とかをインクルードしていますが、これのことです。日本語の記事が見当たらなかったので書くか〜と思いましたが、書き始めると普通に見つかってしまいました。
ということでもうちょっと詳しく書くことにします。
Policy Based Data Structures (PBDS)
何ができるか
- k番目の値を高速に取り出せるデータ構造があります
- std::unordered_mapより4倍近く速いhash tableが使えます
- Tagによってpush, modify, erase, joinなどがO(logn)やO(1)でできるpriority_queueが使えます
- trie木が使えます
すごく拡張性のあるデータ構造ですが、標準の機能をそのまま使って得られるオイシイ機能はこのぐらいです（もちろん自作クラスと組合せたりするとこの限りではありません）。実装削減や、いざというときの高速化に役立つかもしれません。
使い方
ここを見ればだいたいのパターンの実装が書かれていますが、GNUのpbdsではないのでコンパイラがGNU G++の場合はnamespaceのところを using namespace __gnu_pbds; に書き換えてあげてから実行してあげてください。
以下ではこれらのメインの機能を軽く紹介します。
tree
std::setの上位互換です。
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;
で宣言できます。tb_tree_tagは内部構造に赤黒木を指定しており、たとえばsplay木を使いたいときは代わりにsplay_tree_tagを指定すればいいです。
insert, erase
setと同じでinsert, erase関数です
k番目の値を取得
find_by_order(k)でk番目の要素のイテレータが返ります
kが何番目か
order_of_key(k)でk以上で最小の数が何番目か、つまりk未満の数が何個あるかわかります。実質lower_boundですね
コードです。 Submission #3643481 - AtCoder Regular Contest 033
hash table
std::unordered_mapは実装の制約上非効率な実装になっているようで*、速度が要求される場合にはgp_hash_tableが良いようです。
gp_hash_table<int, int> m;
で宣言できます。templateの第三引数にHash関数を指定できるので通常のunordered_mapと同様なHack対策が可能です。
使い方はunordered_mapとほぼほぼ同じなので省略します。
priority_queue
std::priority_queueは、内部のヒープにpairing heapを使用しているようですが*、pbdsではいくつかのヒープをタグとして指定できます。各操作の計算量は以下のような感じです。
pairing heapが案外優秀なので基本的にstd::priority_queueでいいような気がしますが、要素のmodifyとかをしたいときはpbdsが活きますね。
Thin Heapでダイクストラを書いてみましたが、std::priority_queueのほうが速かったです、、 Aizu Online Judge
trie
通常のtrieと同様、文字列の挿入、prefixによる検索ができます。実装にパトリシア木を指定することで愚直なtrie木よりも高速な検索が可能です。
trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> t;
で宣言できます。以下、コード例（#使い方 の部分に貼った実装の中の一例）です。
これも結構便利だとは思うんですが、trie木を使って即終了！ｗみたいな問題はまずないと思いますし、Aho-Corasick等に応用するなら自作クラスや自作policyと組み合わせる必要がありそうです。
性能比較
本家のドキュメンテーションに詳細に記載されています。treeは基本的に赤黒木を指定すれば速いです。
参考文献
C++ STL: Policy based data structures - Codeforces
C++ STL: Order of magnitude faster hash tables with Policy Based Data Structures - Codeforces
Chapter 22. Policy-Based Data Structures
網羅的に読みたい人は３つ目、もう少し細かい機能をざっと確認したい方は４つ目、５つ目の記事をおすすめします。
まとめ
tree, gp_hash_tableは使えそう！それ以外は微妙かなあ、、？
CODE FESTIVAL 2018参加記
お友達がたくさんできたのがよかったです。成績はダメでした。来年がんばりたいね。
高校時代/小学校時代の友達と再会できたしめでたしめでたし。
それにしてもEの簡単な解法に気づかず無限にバグらせて3完だったのはかなりありえなかったので来年は20位ぐらいに入れるようにがんばります。
n進数で桁和がmの倍数⇔mの倍数が成り立つような(n, m)の組合せ
タイトルにあるようなことを昨日考えてました。
試すとわりとすぐに気がつくのですが、(n, (n-1の約数))が条件を満たします。
例えば10進数では(10, 1), (10, 3), (10, 9)で、16進数だと(16, 1), (16, 3), (16, 5), (16, 15)ですね。
導出の過程を簡単に紹介します。 導出のときは、3の倍数⇔桁和が3の倍数、となるような進法が10進数以外にあるか、ということを考えます。
試してみると4進数(3: 3, 6: 12, 9: 21, 12: 30, ...), 7進数(3: 3, 6: 6, 9: 12, 12: 15, ...), 10進数, ...となっていることに気づきます。 逆に、3k+1進数のとき、これが成り立つことは帰納法を用いると示すことができます。3k+1でない場合は、小さなケースを考えるとこれが成り立たないこともすぐに確認できます。
この結果はすぐに一般化でき、mの倍数⇔桁和がmの倍数となるような進法はkm+1進数となることに気づきます。
そうすると、最初に書いた結論が導かれます。
いや〜〜〜〜かなりきれいな結果だと思うんですがこれまで一度も気がつかなかったのはなんででしょうね〜
Codechef SnackDown 2019 Round 1A
@bknshnと組んで出ました。後半３問を担当しました。
Dが難しかったのでE, Fを先に書きます。
E - Chef and Periodic Sequence
https://www.codechef.com/SNCK1A19/problems/PERIODIC
もともとこれがFでしたよねー、いつの間にか順番が変わっていました。明らかにFより簡単だったのでびっくりしてました。
まあ、数字が一つでもあると、1のインデックス（負としてもよい）が決まります。そうすると、1のインデックスの間隔は周期の倍数になるはずなので、 1のインデックス同士の間隔のGCDを取ります（1のインデックスが一つしかない場合は周期infで大丈夫）。これが最大周期です。あとは、順に見ていって矛盾してないかをチェックすればおｋです。
F - Chefland and Average Distance
https://www.codechef.com/SNCK1A19/problems/AVGMAT/
マンハッタン距離を見たら45度回すのは基本ですね〜と言って回します。そうすると、各1について、そこからマンハッタン距離がdの1の個数は、 [x-d, x+d], [y-d, y+d]の正方形の辺上の1の個数です。これは、行と列について1の数の累積和を事前にとっておくとO(1)で求まります。よって計算量はO(NM(N+M))です。
まあ、しかし定数倍がけっこう重い（45度回転させるときに600x600を確保する必要がある）ので、わりとギリギリでした。まあ、回転後に明らかにもとのグリッドを含まない領域の計算を 飛ばすとかなりの定数倍改善になるかもしれませんが、実装難易度はめちゃめちゃ上がると思います。
D - Chef and Strange Addition
https://www.codechef.com/SNCK1A19/problems/CHEFADD
部分点解法としては、popcount(a) bit立っているc以下の数をすべて列挙して、チェックすればいいです。
満点解法はDPっぽいです。
Codeforces Round #517 (Div. 2)
久しぶりの投稿です（Codeforcesは久しぶりではない）
紫になりました。やったー！
D - Minimum Path
解法は以下のSlackのトークを参考にしてください。
ところでこの問題を解いているときに、以前のHackerRankのUniversity Codesprint 5の問題を思い出しました（今回のこどふぉの問題よりずっと難しいしあんまり関係ない話です）。
これですね。今回はpathの長さが2n-1固定なので貪欲でいけましたが、どういう順序で回ってもいい場合は貪欲ではできません。その場合は、suffixに注目したDPをします。これは知っていたのですが、HackerRankはTLE解法を高速化して通したので、DPを書いたことがなく、今回の問題でけっこうびびりました。
DPにstringを保存する（つまり、dp[i]をi番目の頂点からゴールにいく文字列で最小のものとする）とMLEするので、何を保存するのかなと思いましたがdp[i]を、iから遷移できる頂点のうちもっとも辞書順で小さな頂点、としてできる。文字列の比較は、suffix arrayとかを使ってやる模様
↓↓参考↓↓
情報理工院試レビュー
東京大学大学院情報理工学系研究科コンピュータ科学専攻の院試結果の開示が届きました。
自分が受験するときに全然点数情報がわからなかったので、来年度以降調べる人用に自分のものを開示しておきます。
こんな感じです。第一志望の杉山研に受かりました。
数学と専門Iはまあこんなもんか、という感じでしたが専門IIでやらかしてしまい、まわりの人がかなり専門IIで得点をとっていたようなので 緊張してました。
何はともあれ合格してよかったです。
区間と区間がかぶる問題まとめ
【重要】面倒なので、区間の始点終点はすべて異なるとします。そうじゃない場合は適切にソートして順序付けとかしてやると大丈夫です。多分。
すでに区間がたくさんあって交差する回数を数えるやつ
No.743 Segments on a Polygon - yukicoder
すでに区間がたくさんあって、クエリが飛んでてきて指定された区間内にいくつ区間が入っているかを答える
多分一番楽？
- 座標値が収まるような配列を用意し、(Ai, Bi)に対してインデックスAiをBiにセットする
- (Pi, Qi)の間に区間がいくつ収まってるかカウントするときは配列のPi, Qiの範囲内でQi以下の要素の個数を数えます（セグ木とか使って）。
hama-du-competitive.hatenablog.com
ここにも永続セグ木を使うやつとかWaveletMatrixを使うやつなどが載ってます。
区間が動的に追加されていくやつ
無理じゃね？と思っている
