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
競技プログラミングへのお誘い~私と競プロ友達になってください / Invitation to ...
Search
thatblue
December 03, 2022
Technology
1
740
競技プログラミングへのお誘い~私と競プロ友達になってください / Invitation to Competition Programming
Rails Girls Gathering Japan 2022のLT資料です。
https://gathering.railsgirls.jp/
thatblue
December 03, 2022
Tweet
Share
More Decks by thatblue
See All by thatblue
発表資料テンプレート / My slide template
thatblue
0
360
GitHub Pagesで構築したブログをスマホ対応させてみた / make mobile-compatible with lightweight css framework
thatblue
0
220
Sendai.rbコミュニティ紹介 2022 / Introduction of Sendai.rb 2022
thatblue
0
73
Rails Girls Sendaiコミュニティ紹介2022 / Introduction of Rails Girls Sendai 2022
thatblue
0
90
好みのコーヒー探し / find my favorite coffee
thatblue
0
490
Rails Girls Sendai 2ndの後日談としてのSendai.rb / Sendai.rb, As a After Story of Rails Girls Sendai 2nd
thatblue
0
61
Sendai.rbコミュニティ紹介2020 / Introduction of Sendai.rb 2020
thatblue
0
50
Rails Girls Sendaiコミュニティ紹介2020 / Introduction of Rails Girls Sendai 2020
thatblue
0
50
ようやくDDDに手を出したので感想でも / I've getting started to DDD
thatblue
1
380
Other Decks in Technology
See All in Technology
Findy Freelance 利用シーン別AI活用例
ness
0
290
AI によるドキュメント処理を加速するためのOCR 結果の永続化と再利用戦略
tomoaki25
0
390
ロールが細分化された組織でSREと協働するインフラエンジニアは何をするか? / SRE Lounge #18
kossykinto
0
150
Mambaで物体検出 完全に理解した
shirarei24
2
210
S3 Glacier のデータを Athena からクエリしようとしたらどうなるのか/try-to-query-s3-glacier-from-athena
emiki
0
180
みんなのSRE 〜チーム全員でのSRE活動にするための4つの取り組み〜
kakehashi
PRO
2
140
モバイルゲームの開発を支える基盤の歩み ~再現性のある開発ラインを量産する秘訣~
qualiarts
0
1.1k
【CEDEC2025】『Shadowverse: Worlds Beyond』二度目のDCG開発でゲームをリデザインする~遊びやすさと競技性の両立~
cygames
PRO
1
290
バクラクによるコーポレート業務の自動運転 #BetAIDay
layerx
PRO
1
830
データ基盤の管理者からGoogle Cloud全体の管理者になっていた話
zozotech
PRO
0
330
専門分化が進む分業下でもユーザーが本当に欲しかったものを追求するプロダクトマネジメント/Focus on real user needs despite deep specialization and division of labor
moriyuya
0
1k
AWS DDoS攻撃防御の最前線
ryutakondo
0
100
Featured
See All Featured
RailsConf 2023
tenderlove
30
1.2k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
34
6k
The Power of CSS Pseudo Elements
geoffreycrofte
77
5.9k
VelocityConf: Rendering Performance Case Studies
addyosmani
332
24k
Statistics for Hackers
jakevdp
799
220k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
234
17k
How GitHub (no longer) Works
holman
314
140k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
110
19k
KATA
mclloyd
31
14k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.5k
A Tale of Four Properties
chriscoyier
160
23k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
130
19k
Transcript
#rggjp Rails Girls Gathering Japan 2022 競技プログラミングへの お誘い 私と競プロ友達になってください あのぶる
(@thatblue_plus)
#rggjp Rails Girls Gathering Japan 2022 自己紹介 • だいたい仙台出身、ほぼ仙台(Matz島の手前くらい)在住のソフトウェアエンジニア ◦
学生時代を過ごした会津若Matzは第二の故郷 ◦ スマホゲームのバックエンドを作るのがメインのお仕事(のはず) • Rails Girls関係のロール ◦ Sendai 1st, 2ndのオーガナイザー ◦ Sendai, More!の運営 ◦ Rails Girls Japan メンバー (2022/03~) New! • Sendai.rbの代表スタッフもしています
#rggjp Rails Girls Gathering Japan 2022 こんな悩みはありませんか プログラミングに慣れるために もっとたくさんコードを書きたいけど、 いい課題が見つからない…
#rggjp Rails Girls Gathering Japan 2022 それ、競技プログラミングで 解決できるかもしれません
#rggjp Rails Girls Gathering Japan 2022 競技プログラミングとは? 今回はアルゴリズム分野の技能を競うタイプについて扱います
#rggjp Rails Girls Gathering Japan 2022 プログラミングの技術で勝負する競技の一種 通称「競プロ」 プログラムを書いて答える問題が出題される 解答となるプログラムを書いて提出する
→主催者の用意したシステムで採点される 時間内に一番多く、早く解いた人の勝ち 5min 5min 10min 5min 10min 10min 5min 5min
#rggjp Rails Girls Gathering Japan 2022 例題 [AtCoder Beginner Contest
186 A - Brickより抜粋] トラックが1台あります。このトラックには合計でNキログラム以下の荷物を載せ ることができます。 このトラックに、1個Wキログラムのレンガを最大でいくつ載せることができま すか? 制約 • 1 ≤ N,W ≤ 1000 • N,W は整数である。
#rggjp Rails Girls Gathering Japan 2022 こんな感じで実行されるイメージ $ ruby brick.rb
1000 20 # NとWの入力 50 # 答えの出力
#rggjp Rails Girls Gathering Japan 2022 解答例 n, w =
gets.chomp.split.map(&:to_i) puts n / w
#rggjp Rails Girls Gathering Japan 2022 でも、難しいんじゃない?
#rggjp Rails Girls Gathering Japan 2022 モノによりますが初心者でも楽しむことが出来ます • AtCoderのAtCoder Beginner
Contest(通称: ABC) ◦ AtCoderはおそらく日本の競技プログラミングコンテストサイトを代表するサービス ◦ Beginner Contestと言いつつ上級者向けの問題も混じっているので取捨選択が必要 ▪ 問題の選び方は後ほど ◦ ほぼ毎週コンテストを開催しているので、過去問で慣れた後、実際に参加することもできる ◦ Rubyは2.7対応 • Aizu Online Judgeの問題 ◦ 福島県にある会津大学という大学が運営しているサイト ◦ 競技プログラミングの入門記事を読んでいると、学習用として頻繁にお勧めされる (多分これ、一部の問題は本当に授業の演習課題として使ってたことがあるんじゃないかな…?) ◦ Rubyは2.4対応 • yukicoderの問題 ◦ 模試・勉強会の場を提供する位置づけで運営されているサイト ◦ 自由に問題の投稿ができる ◦ 概ね週1回の頻度でコンテストが開催されている ◦ Rubyは3.1対応
#rggjp Rails Girls Gathering Japan 2022 競技プログラミング問題のいいところ • やることがはっきりしている •
問題がたくさん用意されている • 問題の難易度も色々揃っている • 解けたらサイトに提出すれば正しそうかどうかジャッジしてくれる • 自力で解けなかったら解説もある • どうしても分からなかったら他の人の正解コードを読んで勉強できる • いろんなプログラミング言語で挑戦できる • 過去問をちょっと解いてみるだけでも楽しい • 慣れてきたら実際にコンテストに参加すればそれはそれで楽しい
#rggjp Rails Girls Gathering Japan 2022 実際どんな問題があるのか (AtCoder Beginner Contestの例)
#rggjp Rails Girls Gathering Japan 2022 初級編「プログラミングの勉強頑張る!」 • A: Hello,
World+α、という感じの実装 ◦ これをスムーズに解けるようになるのが第一歩 ◦ たまに+αの部分が妙に癖のある問題があるので、難しく感じてもあまり気にせず • B: ループを含んだ実装 ◦ 問題文の指示の通りにコードを書けば解けるように出来ている ◦ ここまではアルゴリズムの知識がなくても練習次第で書けるようになる ◦ Webサービス開発の通常業務で発生する「ちょっとややこしめの実装」が概ねこのあたり (個人調べ) ◦ Rubyで解くと書き味の良さがよく活きる
#rggjp Rails Girls Gathering Japan 2022 中級編「アルゴリズムを学びたい!」 • C: 基本的なアルゴリズム知識とそれを使いこなすスキルが求められる問題
◦ 基本情報や応用情報が射程に入ってくるのであればいい勉強になると思います • D: もう少し突っ込んだアルゴリズム知識が必要になる ◦ ここまで安定して解けるようになったら一般的な(アルゴリズムを専門領域としない)ソフトウェアエン ジニアとしては十分だと思う ◦ いま私が目指しているのはこのあたり • E: 競技プログラミングで使うアルゴリズムをだいたい理解し、基本的な使い こなしが出来ている必要がある(らしい) ◦ この辺くらいで一般的なソフトウェアエンジニアとしてはアルゴリズムスキルのカンストと のこと ◦ 正直ここからは自力で解けたことがないので各種資料を読んだ理解に基づく説明になります
#rggjp Rails Girls Gathering Japan 2022 上級編「アルゴリズム王に、私はなる!!」 • F, G:
たぶん、普通の企業であれば出来上がってるサービスを使うような領域 ◦ 逆にそれを作る側の企業でのアルゴリズム開発に興味があるのなら、大変だと思いますが ここまで頑張ってみるのもあり • Ex: 世界大会とか目指すような人が解く問題なので、とりあえず気にしなく ていいです ◦ ここまで来ると正直”Beginner”とは…?と思うのですが、当初はD問題までだったところから 増えての現在なので、相応に経緯があるようです
#rggjp Rails Girls Gathering Japan 2022 実際やってみてどうなった?
#rggjp Rails Girls Gathering Japan 2022 個人の感想です Rubyのコードがさくさく 書けるようになりました! (個人比)
#rggjp Rails Girls Gathering Japan 2022 もうちょっと真面目に成長具合を説明すると…… 「A~C問題は概ね解き方が分かる」 「他の言語の経験はあるがRubyは初心者で、簡単な処理を書くのもるりま頼り」 という状態から3ヶ月ほど集中的にやってみた
• 実際、Rubyのコードはだいぶスムーズに書けるようになったと思う ◦ 単純に反復練習になっているので、競技プログラミングで頻出の範囲であれば基本的な文法 がスッと出てこなくてアワアワすることはなくなった • 「何とかコンテスト中に3問解けた…」から「4問解けた!」にたどり着ける ようになってきた ◦ 1問目~3問目の所要時間短縮+4問目の解答に必要なアルゴリズム知識の習得 ◦ 典型問題集があるので、まずはそれをコツコツ解いていくのが良さそう
#rggjp Rails Girls Gathering Japan 2022 最近の悩み 一人で黙々とやってるの ちょっと寂しい……
#rggjp Rails Girls Gathering Japan 2022 最近の悩み 競プロ友達が欲しい!
#rggjp Rails Girls Gathering Japan 2022 楽しいけど、難しいと思うことがないわけでもない • 問題文が数学の問題みたいに見えて、慣れるまでちょっと難しいと思うかも しれない
◦ 実際、C問題以降は整数の性質・集合・組み合わせあたりの数学知識は必要になってくる • ある程度反復練習が必要 ◦ なんの予行練習もなくいきなりコンテストに出ると実際大変 ◦ C問題以上を解こうと思ったらアルゴリズムやデータ構造の勉強が必要になってくる ◦ 最初にイメージした通りの結果が出るまでにある程度時間が掛かるので、割り切りポイント が分からないと心が折れやすくはある • 初心者から世界大会レベルの人まで一緒くたになってやっているので、上を 見るとキリがない ◦ さっきの8問を30分で解くような人たちと比べてしまうと大体の人は病みます
#rggjp Rails Girls Gathering Japan 2022 もちろんプログラマーの中でも 向き不向きのある分野で、 気楽に気長にやっていくのがコツ それはまさに沼のような深みですので
#rggjp Rails Girls Gathering Japan 2022 なので、一緒にやりませんか? Rails Girls 競プロ部とか
どうでしょう?
#rggjp Rails Girls Gathering Japan 2022 宣伝: 競プロの問題を体験できるイベント、来週開催! https://sendairb.connpass.com/event/267039/
#rggjp Rails Girls Gathering Japan 2022 私と競プロ友達になってください!