競プロライブラリ紹介

2022/3月に行われた全国学生エンジニア交流会での発表資料です

イベントページはこちら
https://zli.connpass.com/event/239501/

Transcript

1. 競プロライブラリを紹介 matumoto
2. 自己紹介 • HN：matumoto • 学部 2 年（新３年） • 所属：Zli、競技プログラミング、企画開発部 • 趣味：漫画、YouTube、競技プログラミング • AtCoder：水 • GitHub：matumoto1234 • Twitter：@matumoto_1234
3. ライブラリを紹介したい！
4. 作ったはいいものの... • 使わないものが多い • たまにバグっている • 素で書いた方が早い • 柔軟性が少ない • 使い方を覚えていない 紹介して供養 🙏
5. https://github.com/matumoto1234/library GitHubリポジトリ
6. データ構造
7. 二分探索を構造体にしたもの • is_valid 関数と範囲を受け取ると二分探索する • 一番使っていない • 素で書いた方が早い • 実は既に消してしまった
8. dynamic_imos • imos 法の範囲が大きくなったバージョン • 1 <= value <= 1e9 https://github.com/matumoto1234/library/blob/main/data-structure/dynamic-imos.hpp
9. imos 法とは？ 0 1 2 1 ～ 6 5 ～ 10 12 ～ 17 2 ～ 12 3 4 5 6 7 8 9 10 11 12 13 14 17 15 16 区間の重なりを知りたい！
10. 区間の重なり 0 1 2 1 ～ 6 5 ～ 10 12 ～ 16 2 ～ 12 3 4 5 6 7 8 9 10 11 12 13 14 17 15 16 5 には 3 つの区間が重なってる 11 には 1 つの区間が重なってる ＝＞ 区間の長さ × 区間の長さに比例してしまう
11. 区間の重なり 0 1 2 +1 3 4 5 6 7 8 9 10 11 12 13 14 17 15 16 -1 +1 -1 +1 -1 +1 -1
12. 区間の重なり 0 1 2 +1 3 4 5 6 7 8 9 10 11 12 13 14 17 15 16 -1 +1 -1 +1 -1 +1 -1 区間の長さ + 区間の数にはなった！
13. tree • 木に関係する操作をまとめた便利なやつ • 最小共通祖先 • レベルアンセスター • 木の直径 https://github.com/matumoto1234/library/blob/main/graph/tree.hpp
14. tree • 使わない！ • 他のそれ専用のライブラリを使ってしまう https://github.com/matumoto1234/library/blob/main/graph/tree.hpp
15. グラフ系
16. convert_graph • グリッドグラフを隣接リストにする便利関数 • 隣接しているマスを隣接頂点とする • 迷路とかで使う予定だった https://github.com/matumoto1234/library/blob/main/graph/convert-graph.hpp
17. convert_graph • 使わない！ • 迷路は迷路のままで解いてしまう https://github.com/matumoto1234/library/blob/main/graph/convert-graph.hpp
18. shortest-hamiltonian-path • 最小ハミルトン経路を解く • 巡回セールスマン問題の親戚 https://github.com/matumoto1234/library/blob/main/graph/shortest-hamiltonian-path.hpp
19. shortest-hamiltonian-path • 使わない！ • 実は shortest-hamiltonian-cycle もある • どっちを使えばいいか悩んでしまう • 使用用途がかなり限定的になっている https://github.com/matumoto1234/library/blob/main/graph/shortest-hamiltonian-path.hpp
20. 数学系
21. floor div • 切り捨ての整数除算をする https://github.com/matumoto1234/library/blob/main/math/floor-div.hpp
22. floor div • int 型で割り算すればよいです https://github.com/matumoto1234/library/blob/main/math/floor-div.hpp
23. is prime • 素数判定をする https://github.com/matumoto1234/library/blob/main/math/is-prime.hpp
24. is prime • 素数判定だけが必要な問題はほぼないです • 他のライブラリで補える https://github.com/matumoto1234/library/blob/main/math/is-prime.hpp
25. 便利ツール系
26. stopwatch • 時間を計測してくれる https://github.com/matumoto1234/library/blob/main/tools/stopwatch.hpp
27. stopwatch • いる？ • 性能を試したいときは使うかも https://github.com/matumoto1234/library/blob/main/tools/stopwatch.hpp
28. sliced • python のスライスがほしかった • array[l:r] で [l, r) の配列がほしい • sliced(array, l, r) で行う https://github.com/matumoto1234/library/blob/main/tools/sliced.hpp
29. sliced • わざわざ使わない... • ごめん https://github.com/matumoto1234/library/blob/main/tools/sliced.hpp
30. おまけ
31. ありがとうございました！