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
460
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.3k
今年の振り返りと、最近のお悩みの話 / Review of This Year and My Recent Anxiety
linus_mk
0
690
scikit-learnとTFによる実践機械学習7 / Hands-On Machine Learning with Scikit-Learn and TensorFlow 7
linus_mk
0
2.8k
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
20250326_生成AIによる_レビュー承認システムの実現.pdf
takahiromatsui
17
5.5k
WordPress Playground for Developers
iambherulal
0
120
OUPC2024 Day 1 解説
kowerkoint
0
400
ニックトレイン登壇資料
ryotakurokawa
0
140
なぜselectはselectではないのか
taiyow
2
310
データベースエンジニアの仕事を楽にする。PgAssistantの紹介
nnaka2992
9
4.2k
PHPでお金を扱う時、終わりのない 謎の1円調査の旅にでなくて済む方法
nakka
3
1.1k
PHPUnit 高速化テクニック / PHPUnit Speedup Techniques
pinkumohikan
1
1.2k
RubyKaigiで手に入れた HHKB Studioのための HIDRawドライバ
iberianpig
0
1k
リアクティブシステムの変遷から理解するalien-signals / Learning alien-signals from the evolution of reactive systems
yamanoku
2
980
snacks.nvim内のセットアップ不要なプラグインを紹介 / introduce_snacks_nvim
uhooi
0
340
Going Structural with Named Tuples
bishabosha
0
170
Featured
See All Featured
Music & Morning Musume
bryan
46
6.4k
Producing Creativity
orderedlist
PRO
344
40k
Fontdeck: Realign not Redesign
paulrobertlloyd
83
5.4k
Art, The Web, and Tiny UX
lynnandtonic
298
20k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
RailsConf 2023
tenderlove
29
1k
How to Ace a Technical Interview
jacobian
276
23k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
4
470
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
31
4.7k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
51
2.4k
Building an army of robots
kneath
304
45k
The Invisible Side of Design
smashingmag
299
50k
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以外にも色々あります。調べてみてね)