Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
競プロライブラリ紹介
Search
Sponsored
·
Your Podcast. Everywhere. Effortlessly.
Share. Educate. Inspire. Entertain. You do you. We'll handle the rest.
→
matumoto
March 12, 2022
Technology
47
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
競プロライブラリ紹介
2022/3月に行われた全国学生エンジニア交流会での発表資料です
イベントページはこちら
https://zli.connpass.com/event/239501/
matumoto
March 12, 2022
Transcript
31 slides
競プロライブラリを紹介 matumoto
自己紹介 • HN:matumoto • 学部 2 年(新3年) • 所属:Zli、競技プログラミング、企画開発部 •
趣味:漫画、YouTube、競技プログラミング • AtCoder:水 • GitHub:matumoto1234 • Twitter:@matumoto_1234
ライブラリを紹介したい!
作ったはいいものの... • 使わないものが多い • たまにバグっている • 素で書いた方が早い • 柔軟性が少ない •
使い方を覚えていない 紹介して供養 🙏
https://github.com/matumoto1234/library GitHubリポジトリ
データ構造
二分探索を構造体にしたもの • is_valid 関数と範囲を受け取ると二分探索する • 一番使っていない • 素で書いた方が早い • 実は既に消してしまった
dynamic_imos • imos 法の範囲が大きくなったバージョン • 1 <= value <= 1e9
https://github.com/matumoto1234/library/blob/main/data-structure/dynamic-imos.hpp
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 区間の重なりを知りたい!
区間の重なり 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 つの区間が重なってる => 区間の長さ × 区間の長さに比例してしまう
区間の重なり 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
区間の重なり 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 区間の長さ + 区間の数にはなった!
tree • 木に関係する操作をまとめた便利なやつ • 最小共通祖先 • レベルアンセスター • 木の直径 https://github.com/matumoto1234/library/blob/main/graph/tree.hpp
tree • 使わない! • 他のそれ専用のライブラリを使ってしまう https://github.com/matumoto1234/library/blob/main/graph/tree.hpp
グラフ系
convert_graph • グリッドグラフを隣接リストにする便利関数 • 隣接しているマスを隣接頂点とする • 迷路とかで使う予定だった https://github.com/matumoto1234/library/blob/main/graph/convert-graph.hpp
convert_graph • 使わない! • 迷路は迷路のままで解いてしまう https://github.com/matumoto1234/library/blob/main/graph/convert-graph.hpp
shortest-hamiltonian-path • 最小ハミルトン経路を解く • 巡回セールスマン問題の親戚 https://github.com/matumoto1234/library/blob/main/graph/shortest-hamiltonian-path.hpp
shortest-hamiltonian-path • 使わない! • 実は shortest-hamiltonian-cycle もある • どっちを使えばいいか悩んでしまう •
使用用途がかなり限定的になっている https://github.com/matumoto1234/library/blob/main/graph/shortest-hamiltonian-path.hpp
数学系
floor div • 切り捨ての整数除算をする https://github.com/matumoto1234/library/blob/main/math/floor-div.hpp
floor div • int 型で割り算すればよいです https://github.com/matumoto1234/library/blob/main/math/floor-div.hpp
is prime • 素数判定をする https://github.com/matumoto1234/library/blob/main/math/is-prime.hpp
is prime • 素数判定だけが必要な問題はほぼないです • 他のライブラリで補える https://github.com/matumoto1234/library/blob/main/math/is-prime.hpp
便利ツール系
stopwatch • 時間を計測してくれる https://github.com/matumoto1234/library/blob/main/tools/stopwatch.hpp
stopwatch • いる? • 性能を試したいときは使うかも https://github.com/matumoto1234/library/blob/main/tools/stopwatch.hpp
sliced • python のスライスがほしかった • array[l:r] で [l, r) の配列がほしい
• sliced(array, l, r) で行う https://github.com/matumoto1234/library/blob/main/tools/sliced.hpp
sliced • わざわざ使わない... • ごめん https://github.com/matumoto1234/library/blob/main/tools/sliced.hpp
おまけ
ありがとうございました!
More Decks by matumoto
See All by matumoto
Go標準パッケージのI/O処理をながめる
matumoto
0
550
testingを眺める
matumoto
1
230
sync/v2 プロポーザルの 背景と sync.Pool について
matumoto
0
860
Goトランザクション処理
matumoto
1
100
いまいちどスライスの 挙動を見直してみる
matumoto
0
440
Go1.22のリリース予定の機能を見る
matumoto
0
110
GoのUnderlying typeについて
matumoto
0
250
Typed-nilについて
matumoto
0
410
GoのType Setsという概念
matumoto
0
73
Other Decks in Technology
See All in Technology
Test Impact Analysis を武器に立ち向かう、AI 時代のテスト増加に対するヌーラボのアプローチ / getting-started-datadog-test-impact-analysis
k6s4i53rx
0
270
HTTP QUERY時代の型安全な検索APIをKotlinで設計する
sansantech
PRO
1
110
OWASP AI Agentic Top10に準拠するクラウドネイティブなガードレールの実践(CNDW 2026)
keitah
1
370
「個社」ではなく「業界」の課題を解く AI 対話開発 ー 価値を広げる設計と、価値を守るエンジニアリング ー
ivry_presentationmaterials
3
790
AWS DevOps Agentの構造から読み解く運用 AI エージェントの設計原則/aws-devops-agent-design-principles
tomoki10
0
150
PHPで家庭用ゲーム機の専用コントローラーをMIDIデバイスとして扱ってみる
wind111
0
170
IoTのデータ保存をSREの観点で考える
grimoh
1
110
Oracle Base Database Service 技術詳細
oracle4engineer
PRO
17
120k
Taking back control of your AI development
inesmontani
PRO
0
300
「任されビリティ」で引き受けて「よしなりてぃ」に頼らず任せる / Accept tasks with "makasarebility" and hand them over without relying on "yoshinarily"
pauli
1
860
さようならSSH鍵、こんにちはゼロトラスト ― AIフレンドリーで快適な自宅鯖SSH
atalie2m
14
7.3k
Kubernetes, Agones, WebRTC, GPU で作る クラウドゲーミング基盤を本番運用に乗せるまで
vivion
0
210
Featured
See All Featured
Ten Tips & Tricks for a 🌱 transition
stuffmc
1
290
How to Talk to Developers About Accessibility
jct
2
620
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
16
2.2k
HDC tutorial
michielstock
2
1k
RailsConf 2023
tenderlove
30
1.6k
Redefining SEO in the New Era of Traffic Generation
szymonslowik
1
530
Testing 201, or: Great Expectations
jmmastey
46
8.4k
The Curse of the Amulet
leimatthew05
4
17k
How to Align SEO within the Product Triangle To Get Buy-In & Support - #RIMC
aleyda
2
1.9k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
232
55k
How GitHub (no longer) Works
holman
316
150k
Digital Ethics as a Driver of Design Innovation
axbom
PRO
2
550