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
Google Code Jamの話 / About Google Code Jam
Search
Linus_MK
April 14, 2018
Programming
0
500
Google Code Jamの話 / About Google Code Jam
2018年4月14日 第39回 PORTもくもく会LTにて発表
同日開催されたGoogle Code Jamについてしゃべりました。
Linus_MK
April 14, 2018
Tweet
Share
More Decks by Linus_MK
See All by Linus_MK
マッシュアップ曲を聞いてビックリしたので、音楽のコードを分析してみた / Examined the Similarity of Two Tunes by Analyzing their Chords
linus_mk
2
1.4k
今年の振り返りと、最近のお悩みの話 / Review of This Year and My Recent Anxiety
linus_mk
0
710
scikit-learnとTFによる実践機械学習7 / Hands-On Machine Learning with Scikit-Learn and TensorFlow 7
linus_mk
0
2.9k
scikit-learnとTFによる実践機械学習4.1-4.2 / Hands-On Machine Learning with Scikit-Learn and TensorFlow 4.1-4.2
linus_mk
0
1.2k
Other Decks in Programming
See All in Programming
[FEConf 2025] 모노레포 절망편, 14개 레포로 부활하기까지 걸린 1년
mmmaxkim
0
1.5k
Honoアップデート 2025年夏
yusukebe
1
920
AIでLINEスタンプを作ってみた
eycjur
1
230
1から理解するWeb Push
dora1998
7
1.8k
MCPとデザインシステムに立脚したデザインと実装の融合
yukukotani
4
1.4k
Kiroの仕様駆動開発から見えてきたAIコーディングとの正しい付き合い方
clshinji
1
200
CSC305 Summer Lecture 12
javiergs
PRO
0
140
More Approvers for Greater OSS and Japan Community
tkikuc
1
110
OSS開発者という働き方
andpad
5
1.7k
Oracle Database Technology Night 92 Database Connection control FAN-AC
oracle4engineer
PRO
1
430
MCPで実現するAIエージェント駆動のNext.jsアプリデバッグ手法
nyatinte
7
1.1k
プロポーザル駆動学習 / Proposal-Driven Learning
mackey0225
2
960
Featured
See All Featured
How GitHub (no longer) Works
holman
315
140k
What's in a price? How to price your products and services
michaelherold
246
12k
jQuery: Nuts, Bolts and Bling
dougneiner
64
7.9k
Into the Great Unknown - MozCon
thekraken
40
2k
Build The Right Thing And Hit Your Dates
maggiecrowley
37
2.8k
Making the Leap to Tech Lead
cromwellryan
135
9.5k
YesSQL, Process and Tooling at Scale
rocio
173
14k
Visualization
eitanlees
148
16k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3k
Making Projects Easy
brettharned
117
6.4k
Code Review Best Practice
trishagee
70
19k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3.1k
Transcript
Google Code Jamの話 @Linus_MK 2018年4月14日 第39回 PORTもくもく会
自己紹介 twitter : @Linus_MK (ライナス) 音声信号処理のソフト開発 主にC/C++ 業務外: 機械学習の勉強はじめました 競技プログラミング(Ruby)←今日はこの話!
目次 Google Code Jamとは何か 実際にどんな問題が出てくるのか?
Google Code Jamとは何か 競技プログラミングの大会。Google主催、年1回 アルゴリズム系の問題が出題されて、時間内に解く (解くためのソースコードを書いて、システム上に提出する) システム上で正しいか判定して、正答ならば得点が入る 得点で順位をつける(同点なら提出が速い人が上位) →速く正確にコードを書く必要がある
各ラウンドとスケジュール 予選ラウンド 4月7日(土)08:00 – 4月8日(日)11:00 ラウンド1-A 4月14日(土) 10:00 – 12:30【今日でした】 ラウンド1-B 4月30日(月)
01:00 – 03:30 ラウンド1-C 5月5日(土) 18:00 – 20:30 ラウンド2 ラウンド3 決勝 8月 トロント(カナダ) 25 / 100点取れればOK (14000人が進出した) どれかの回で上位1500位以内 (4500人) 1000位以内 25位以内 ここまではネット上で開催される
今日の結果 ラウンド1-A 4月14日(土) 10:00 – 12:30 の俺 ラウンド1-C 5月5日(土) 18:00 – 20:30 でがんばります……
全然分からん (3問中1問も解けず)
どんな問題が出るの? 予選ラウンド(全4問)の最初の問題を紹介します (適宜省略したので正確なとこは原文を参照)
問題内容 宇宙からロボットが攻めてきた 以下のプログラムで攻撃してくる SとCからなる文字列 S(shoot):攻撃してダメージを与える C(charge):与えるダメージを2倍にする(最初は1) 例:S C C S S ダメージ4 ダメージ4 攻撃 ダメージ1
ダメージ 1→2 ダメージ 2→4 合計ダメージ 9
問題内容 防御シールドでDまでのダメージは耐えられる 攻撃プログラムを書き換えてダメージをD以下にしたい 操作:隣りあう文字を入れ替える (SCCSS → SCSCS) 入力:耐えられるダメージD、攻撃プログラム文字列P 出力:ダメージをD以下にするための最小操作回数 S C C S S ダメージ4 ダメージ4
ダメージ1 1→2 2→4 合計ダメージ 9 S C S C S ダメージ2 ダメージ4 ダメージ1 1→2 2→4 合計ダメージ 7
(だいぶアバウトな)解法 Sを最初(左)の方に、Cを最後(右)の方に移動したい 解法: 文字列の一番右側の「CS」を見つけて、「SC」に入れ替える ダメージを再計算 D以下ならOK、結果を出力して終了 Dより大きいならまだダメ、操作回数++ 最初に戻る 正確な方針はGoogleのAnalysisを参照 S C S C S ダメージ2
ダメージ4 ダメージ1 1→2 2→4 合計ダメージ 7 この「CS」を入れ替え るとダメージ2→1 この「CS」を入れ替え るとダメージ4→2
まとめ 競技プログラミングは楽しいよ (Google Code Jam以外にも色々あります。調べてみてね)