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
420
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.2k
今年の振り返りと、最近のお悩みの話 / Review of This Year and My Recent Anxiety
linus_mk
0
650
scikit-learnとTFによる実践機械学習7 / Hands-On Machine Learning with Scikit-Learn and TensorFlow 7
linus_mk
0
2.6k
scikit-learnとTFによる実践機械学習4.1-4.2 / Hands-On Machine Learning with Scikit-Learn and TensorFlow 4.1-4.2
linus_mk
0
1.1k
Other Decks in Programming
See All in Programming
Amazon Neptuneで始める初めてのグラフDB ー グラフDBを使う意味を考える ー
satoshi256kbyte
2
260
Boost Performance and Developer Productivity with Jakarta EE 11
ivargrimstad
0
490
Desafios e Lições Aprendidas na Migração de Monólitos para Microsserviços em Java
jessilyneh
2
150
仮想ファイルシステムを導入して開発環境のストレージ課題を解消する
segadevtech
2
550
状態管理ライブラリZustandの導入から運用まで
k1tikurisu
3
470
The Shape of a Service Object
inem
0
520
Google Sign-inの移行から始めるCredential Manager活用
clockvoid
0
310
React + TextAliveでカッコいいLyric Applicatioinを作ろう!!
tosuri13
0
400
How to Break into Reading Open Source
kaspth
2
220
今インフラ技術をイチから学び直すなら
yuhta28
1
140
o1モデルのプロンプトエンジニアリングって?
ktc_wada
0
270
Modern Angular with the NGRX Signal Store New Rules for Your Architecture @BASTA! 2024 in Mainz
manfredsteyer
PRO
0
150
Featured
See All Featured
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
225
22k
The Art of Programming - Codeland 2020
erikaheidi
48
13k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
363
22k
Producing Creativity
orderedlist
PRO
340
39k
Faster Mobile Websites
deanohume
304
30k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
43
2k
GraphQLとの向き合い方2022年版
quramy
43
13k
jQuery: Nuts, Bolts and Bling
dougneiner
61
7.4k
Building a Scalable Design System with Sketch
lauravandoore
459
32k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
354
29k
What’s in a name? Adding method to the madness
productmarketing
PRO
21
3k
Facilitating Awesome Meetings
lara
49
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以外にも色々あります。調べてみてね)