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
AIコーディングAgentとの向き合い方
eycjur
0
260
JSONataを使ってみよう Step Functionsが楽しくなる実践テクニック #devio2025
dafujii
1
510
時間軸から考えるTerraformを使う理由と留意点
fufuhu
14
4.6k
Android 16 × Jetpack Composeで縦書きテキストエディタを作ろう / Vertical Text Editor with Compose on Android 16
cc4966
0
140
Deep Dive into Kotlin Flow
jmatsu
1
260
パッケージ設計の黒魔術/Kyoto.go#63
lufia
3
430
「手軽で便利」に潜む罠。 Popover API を WCAG 2.2の視点で安全に使うには
taitotnk
0
820
Cache Me If You Can
ryunen344
1
450
プロポーザル駆動学習 / Proposal-Driven Learning
mackey0225
2
1.1k
Go言語での実装を通して学ぶLLMファインチューニングの仕組み / fukuokago22-llm-peft
monochromegane
0
120
Zendeskのチケットを Amazon Bedrockで 解析した
ryokosuge
3
290
アプリの "かわいい" を支えるアニメーションツールRiveについて
uetyo
0
210
Featured
See All Featured
The Art of Programming - Codeland 2020
erikaheidi
55
13k
Building Better People: How to give real-time feedback that sticks.
wjessup
368
19k
Practical Orchestrator
shlominoach
190
11k
Intergalactic Javascript Robots from Outer Space
tanoku
272
27k
Unsuck your backbone
ammeep
671
58k
Site-Speed That Sticks
csswizardry
10
810
Embracing the Ebb and Flow
colly
87
4.8k
Designing for humans not robots
tammielis
253
25k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3k
Side Projects
sachag
455
43k
Code Reviewing Like a Champion
maltzj
525
40k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.6k
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以外にも色々あります。調べてみてね)