Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
JVM言語でもできる、競技プログラミング
Search
dhirabayashi
June 15, 2024
Technology
0
320
JVM言語でもできる、競技プログラミング
JJUG CCC 2024 Spring
2024年6月18日(日) 10:25 - 10:45
dhirabayashi
June 15, 2024
Tweet
Share
Other Decks in Technology
See All in Technology
GPSデバイスを使った簡易位置案内システムの構築をしてみた話。/jawsfesta2024
kwada
0
210
Rist_Meetup_Kaggleは業務の役にたつ - ビジネスコンテンツ情報を活用する BtoB 事業編 - / rist-meetup-20241012
taro_masuda
0
260
Amazon Managed Grafana で AWS IoT TwinMaker によるデジタルツインアプリケーションを動かしてみた
wakatsuki
0
110
The road to green code (with Sonar)
bluehats
0
150
巨大企業でDX革新を起こすということ BTCONJP 2024
yamaken66
0
160
生成AI入門
shukob
0
110
AWSの初級者向けAI・ML資格『AWS Certified AI Practitioner』の傾向と対策/So You Want To Pass AWS Certified AI Practitioner
quiver
0
910
Automated Tests Now and Future @ SQiP Workshop Special Lecture 2024
teyamagu
PRO
2
440
自然言語処理を役立てるのはなぜ難しいのか
pfn
PRO
14
4.2k
LINE-ChatGPT 倫理問題を整理する全力肯定彼氏くん [LuC4]に訪れたサービス開始以来の最大の危機
o_ob
2
290
プログラミング写経のすすめ
natsutan
0
150
JAWS-UG 事務局 の「これまで」から みんなで「ここから」を考えよう
miu_crescent
2
140
Featured
See All Featured
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
27
1.9k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
48k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
26
1.4k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
167
49k
Rebuilding a faster, lazier Slack
samanthasiow
79
8.6k
Java REST API Framework Comparison - PWX 2021
mraible
PRO
28
7.6k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
40
2.1k
What's in a price? How to price your products and services
michaelherold
243
11k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
31
2.6k
Pencils Down: Stop Designing & Start Developing
hursman
119
11k
Imperfection Machines: The Place of Print at Facebook
scottboms
264
13k
Transcript
JVM言語でもできる、競技プログラミング JVM言語でもできる、競技プログラミング JJUG CCC 2024 Spring Daiki Hirabayashi
2 自己紹介 いわゆるシステムエンジニア – Javaをちょこちょこと – 最近はサーバサイドKotlin 平林 大輝 株式会社テクニケーション
– 2021年~ 現職 X (Twitter): @dhirabayashi64 競プロ歴について – 2022年から本格的に開始 – 実力は普通
3 話すこと • 競技プログラミング(競プロ)って何? – 概要 – 面白さや難しさ • 使用するプログラミング言語の話
• 面白さや実益についての実感
4 前置き • 競プロといってもいろいろある • 以下はAtCoderというサイトのABCというコンテスト前提
5 競技プログラミング(競プロ)とは? • プログラミングを使って問題を解くゲームみたいなもの • 参加者全員に同じ問題が与えられ、それを解くコードを書く • 正解するコードを書いたら得点が得られる • 多くの得点を獲得することを目指す
– 得点が高い人ほど上位 – 得点が同じなら早く正解したほうが上位
6 競プロで取り組む「問題」 たとえば以下のような感じ 出典: https://atcoder.jp/contests/abc169/tasks/abc169_a
7 競プロで取り組む「問題」 • 回答例
8 書いたコードは提出する
9 提出コードすると? • 提出したコードに対して即座にテストが実行される – 入力に対し、出力が期待値通りかどうか – 実行時間、メモリ使用量が制限を超えていないか
10 提出結果 →AC(Accepted): 正解
11 もうちょっと難しい問題 出典: https://atcoder.jp/contests/abc346/tasks/abc346_c
12 もうちょっと難しい例
13 もうちょっと難しい例
14 実装例(?)
15 提出結果… →TLE(Time Limit Exceeded): 実行時間超過
16 ダメな理由 →20億回ループが回るので間に合わない
17 どうやって解くか →こっち(20万件)なら全部見ても間に合う
18 どうやって解くか • 「現れないもの」の合計 – 2 + 4 + 5
= 11 • 「全部の合計」から「現れるもの」を引いても同じ! – 1 + 2 + 3 + 4 + 5 = 15 – 15 – (1 + 3) = 11
19 正解例
20 正解例 →1からKまでの合計を求める関数を作る。計算で求めるので速い
21 正解例 重複を排除 1からKの合計値を求める 現れる数を引く 最大20万件なので十分速い
22 提出結果 →AC!
23 競プロとプログラム実装 • ただの実装作業ゲーとは限らない – それなりに頭を捻ることになる – プログラムの実行時間も考える必要がある • ちゃんと実装しきる必要もある
– やってみると意外と大変…
24 プログラミング言語について • AtCoderの場合、メジャーな言語ならだいたい使える • 実際に使われているのは圧倒的にC++ – 次点でPython – だいたいどちらかがおすすめされる
• それら以外の言語も全く使われないわけではない
25 使用言語についての私見 • 好きなのを使えばいい – せっかくいろいろ対応しているので • 個人的にはKotlinを使っている – そんなに問題なくて2年くらい使っている
26 JVM言語(Kotlin)を使って得た実感 • そこそこ安心できる実行速度 – オートボクシング/アンボクシングで遅いことはある • バグなく実装しやすい – コンパイラのチェック、型安全性
• fluentなリスト操作は競プロでも活きる(※私見) • 不利な点も – 公式解説のコードはだいたいC++かPythonで書かれる – C++やPythonにあるがJavaやKotlinにはないライブラリも
27 競プロに取り組んで得た実感 • 実装力が鍛えられる – ちゃんと動くコードを素早く書く必要がある – 入念に動作確認している時間がない • 業務外で日常的にプログラミングする手段になる
– 作る物のアイデアがなくてもプログラミングできる – テストされるのでそれなりにちゃんと書く必要がある • プログラミングが楽しいと思えた
28 辛い点も… • それなりに時間を吸われる – コンテスト参加のための時間 • 提出が通らないが全然原因がわからないことも • 良い成績がとれるとは限らない
• 身につく力の範囲は局所的
29 代表的なコンテスト • AtCoder Beginner Contest(ABC) – オンラインコンテスト – ほぼ毎週開催される
• だいたい土曜日(たまに日曜日) • 21:00 ~ 22:40の100分間 – 直近では7問出題される • 難易度が幅広いのでだいたい誰でも参加できる
30 まとめ • 競プロは日常的にプログラミングする手段の一つとなる – 個人開発のネタがなくてもプログラミングできる – 実装力を鍛えられる – 楽しい
• 始めるならAtCoderがおすすめ • JavaやKotlinでも戦える