狠狠撸

競プロは
人生の役に立つ
NTTデータ数理システム
大槻兼資
2023/2/5
@JOI 本選講演
1

? 積極的に声やチャットで喋ってもらえたら嬉しいです
最初に
2
? JOI 本選で仲間をたくさん作ろう！
/ 133
? リラックスしよう！楽しもう！
? JOI 頑張ってください！
? JOI 本選進出おめでとうございます！

? 2014年：東京大学大学院情報理工学系研究科
数理情報学専攻修士課程修了
自己紹介 (本業編)
? 2015年?：NTT データ数理システム
? 専門は数理工学全般
? アルゴリズム
? 探索, ネットワーク, etc…
? 数理最適化
? シフトスケジューリングなど
? 機械学習
? チャットボットなど
http://www.dis.uniroma1.it/challenge9/download.shtml 3 / 99

自己紹介 (本業編)
? アルゴリズムの楽しさを伝える活動をしています！
? 本を 3 冊出版
? Qiita でアルゴリズムの記事を多数執筆

5
競プロは役に立つ！
? 競プロで世界が広がる！
? 競プロ的な問題は社会にもたくさん！
? 竞プロで人生が切り拓かれる！

6
? 競プロで世界が広がる！

7
競プロで世界が広がる！
高校
大学
社会
?JOI
?JOI 春合宿
?ICPC
?大学主催コンテストや合宿
?ひたすら精進に打ち込む青春
?AtCoder コンテストは一生楽しめる！
?競プロしなければなかった出会い沢山
?社会人も関わるイベントも沢山

8
JOI 春合宿
https://kininarukotomatome.com/olympiad-informatics/
https://www.ioi-jp.org/joi/2020/index.html
? 対面のコンテストは空気感が違う！
? コンテスト後の感想戦が格別！
? ライバルから刺激を受ける！

9
大学入学後も競プロは続く！
高校
大学
社会
?JOI
?JOI 春合宿
?ICPC

10
ICPC も楽しい！
? 3 人 1 組のチーム戦！！！
/iwiwi/wakate-web-14323842
? 競プロサークルのある大学もたくさん！
? 合宿やコンテストの開催側にもなれる！

11
競プロで世界が広がる！
高校
大学
社会
?JOI
?JOI 春合宿
?ICPC

12
AtCoder は一生楽しめる！
? AtCoder がずっと続くことを祈りましょう！
? 毎週末、コンテスト後には Twitter が盛り上がる！
https://togetter.com/li/1469550

13
イベント開催もたくさん！
? comb naf
? GigaCode
? 競プロキャンプ
? フォルシアゆるふわコンテスト
? プランクトンサミット
? CPSCO
……などなど、コロナ禍後も少しずつ復活の兆し

14
? comb naf
? GigaCode
? CPSCO

15
? comb naf
? GigaCode
? CPSCO

16
? 一緒にいっぱい楽しもう！！！！！！

17
? 竞プロで人生が切り拓かれる！

18
競プロで自己実現！
? アルゴリズム研究者になった人！
? AI 研究開発に繋げた人！
? 競プロで築いた人脈で起業した人！
? AtCoder Jobs 経由で就職?転職した人！
? 本を書いた人！
……などなど、競プロで人生が変わるかもしれない！

19
アルゴリズムを学ぶ動機は様々
? 競技プログラミングで勝ちたい！
? コンピュータサイエンスの重要な一分野として
学んでおきたい
? ソフトウェアエンジニアとしてステップアップしたい
? 就職で有利にしたい！
どんな人にもオススメ！！

20
アルゴリズムで身に付く力
? 問題を理解する力 (理解力)
? ロジカルに考える力 (思考力)
? コーディング力 (技術力)
? アルゴリズムを説明する力 (説明力)
? 何かを楽しんで主体的に学んだ経験そのもの
一生モノのスキル

21
? 競プロ的な問題は社会にもたくさん！

22
アルゴリズムによる問題解決
数理モデル化
AtCoder
みたいな問題
解
解釈?意思決定
アルゴリズム

23
アルゴリズムは分野横断的
? AI や量子コンピュータなどの、分野の流行に依らない
一生モノのスキル
? むしろ AI を学ぶための強力な下地となる
グラフ
動的計画法
○○法
電気機械化学生物経済 ○○
? さまざまな分野の問題が、アルゴリズムの目で見ること
によって本質的に同じ問題になったりなる！
/ 133

24
実務で使ったアルゴリズムたち
? DP (動的計画法)
? ナップサック DP
? 区間 DP
? O(3^N) の bit DP
? セグメント木
? 遅延評価つきセグメント木
? セグメント木上の DP
? フロー
? 二部マッチング
? ABC-G でもありそうな最大フロー問題
? ヒューリスティクス系
? 焼きなましやビームサーチ
? 負閉路があるかもしれない最短路問題

25
実務で使ったアルゴリズムたち
? DP (動的計画法)
? ナップサック DP
? 区間 DP
? O(3^N) の bit DP
? セグメント木
? 遅延評価つきセグメント木
? セグメント木上の DP
? フロー
? 二部マッチング
? ABC-G でもありそうな最大フロー問題
? ヒューリスティクス系
? 焼きなましやビームサーチ
? 負閉路つきの最短路問題

DP (動的計画法) とは
26
問題を一連の部分問題に分割し、
各部分問題の解をメモ化しながら順に求めていく手法
? とても抽象的で汎用的
? 適用範囲が広い
? ただし一見わかりにくい
/ 133

動的計画法の例題
27
足場を「ジャンプ」しながら左端から右端へ行きたい
AtCoder Educational DP Contest A - Frog
ただし「隣の足場」か「1 個飛ばしの足場」にのみ進める
ジャンプの所要時間は「足場の高さの差」
左端から右端までの最短所要時間を求めよ
4m 7m
7 - 4 = 3 秒！
3m
/ 133

28
例:
?足場が 7 個
?(2, 9, 4, 5, 1, 6, 10)
/ 133

29
例:
?足場が 7 個
?(2, 9, 4, 5, 1, 6, 10)
/ 133

30
例:
?足場が 7 個
?(2, 9, 4, 5, 1, 6, 10)
+4
+1 +1
+2
最短: 8 秒
/ 133

グラフの問題と考える
31
例:
0 1 2 3 4 5 6
7
2
5 1 4 5 4
4
3
1 9
?足場が 7 個
?(2, 9, 4, 5, 1, 6, 10)
/ 133

32
グラフ
? 物事の関係性を「丸」と「線」を用いて表したもの
? コンピュータサイエンスのあらゆる領域で使われる
頂点辺
/ 133

? あれもこれも実はグラフ！
? さまざまな分野の問題をグラフに関する問題として
見通よく汎用的に扱える！
33
アルゴリズムの精神
グラフ
/ 133

34
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
? ノード 0 からノード 6 への最短経路を求める！
/ 133

35
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
? ノード 0 からノード 6 への最短経路を求める！
? 答えは、2 + 1 + 1 + 4 = 8
/ 133

問題を次のように分解する
36
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
? ノード 1 へ至る最小コストを求める小問題
? ノード 6 へ至る最小コストを求める小問題 / 133

37
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6

38
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6

39
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6

40
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6

41
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6

42
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6

メモ化用の DP テーブル
43
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
メモ
/ 133

頂点 0 への最小コスト (初期条件)
44
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
0
メモ
/ 133

頂点 1 への最小コスト
45
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
0
7
7
メモ
/ 133

46
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
0 7
2
5
2
12 vs. 2
メモ
/ 133

47
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
0 7
4
1
2
3 vs. 11
3
メモ
/ 133

48
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
メモ
0 7
3
4
2
7 vs. 5
3 5
/ 133

49
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
0 7
1
5
2
10 vs. 4
3 5 4
メモ
/ 133

50
0
7
2
5 1 4 5 4
4
3
1 9
1 2 3 4 5 6
0 7
9
4
2
8 vs. 14
3 5 4 8
メモ

実装上は
51
? メモ化用の DP テーブルを配列でもつ
dp[v] ← 頂点 0 から頂点 v へ至る最短コスト
i-2 i-1 i
dp[i] = min(dp[i-1] + f(i-1, i),
dp[i-2] + f(i-2, i)
/ 133

動的計画法の着眼
52
? メモ化：何度も参照される小さな問題の結果を保存して
すぐに参照できるようにする (キャッシュ)
問題を一連の部分問題に分割し、
各部分問題の解をメモ化しながら順に求めていく手法
? 部分問題への分割：同じ構造を持つ小さな問題 (部分問
題) の結果を使うことで大きな問題が解ける
? ノード 1, 2, 3, 4, 5, 6 への最短経路を順に求めた
/ 133

実務でも登場した問題 2 つ紹介
53
? JOI 本選 2016 A 問題 - オレンジの出荷
? AtCoder ARC 070 E - NarrowRectangles

54
大きさが A[0], A[1], …, A[N-1] のオレンジがある
0 1 2 3 4 5 6 7 8 9
前から順に、箱に詰めていく
各箱のコストは、
「K + (箱内の A の最大値 - 箱内の A の最小値) × 個数」
各箱のコストの総和を最小化せよ
3 5 4 9 11 8 10 1 7 8
K = 5
/ 133
JOI の問題：オレンジの出荷 (改)
JOI 本選 2016 A 問題

55
0 1 2 3 4 5 6 7 8 9
3 5 4 9 11 8 10 1
K = 5
7 8
基本コスト
/ 133

56
0 1 2 3 4 5 6 7 8 9
3 5 4 9 11 8 10 1 7 8
K = 5
例
/ 133

57
0 1 2 3 4 5 6 7 8 9
3 5 4 9 11 8 10 1 7 8
K = 5
例
5 + (9 - 3) × 4
= 29
5 + (11 - 8) × 3
= 14 5
5 + (8 - 7) × 2
= 7
/ 133

58
0 1 2 3 4 5 6 7 8 9
3 5 4 9 11 8 10 1 7 8
K = 5
例
5 + (9 - 3) × 4
= 29
5 + (11 - 8) × 3
= 14 5
5 + (8 - 7) × 2
= 7
コスト: 55
/ 133

59
0 1 2 3 4 5 6 7 8 9
3 5 4 9 11 8 10 1 7 8
K = 5
? Frog 問題と同様に「前から何個かのオレンジ」に
ついての小問題に分割していく
/ 133

60
0 1 2 3 4 5 6 7 8 9
3 5 4 9 11 8 10 1 7 8
K = 5
? メモ化用の配列を用意する
/ 133

61
0 1 2 3 4 5 6
3 5 4 9 11 8 10
K = 5
? メモ化用の配列を用意する
たとえばこのマスには
前から 7 個のオレンジ
についての答えを格納
/ 133

62
0 1 2 3 4 5 6 7 8 9
3 5 4 9 11 8 10 1 7 8
K = 5
? 前から 0 個のオレンジについての答えは 0
0
/ 133

63
前から 0 個
K = 5
0
/ 133

64
前から 1 個
0
3
K = 5
0 5
+5
1
1 個のオレンジ {3}
を箱詰めするコストは 5
/ 133

65
前から 2 個について考える
0
3
K = 5
0 5
1
5
? 最後の箱をどうするかで場合分けして考える
? 最後の箱が {3, 5} である場合
? 最後の箱が {5} である場合
/ 133

66
0
3
K = 5
0 5
1
5
+9
? 最後の箱が {3, 5} のとき：コストは 0 + 9 = 9
/ 133

67
0
3
K = 5
? 最後の箱が {3, 5} のとき：コストは 0 + 9 = 9
0 5
1
5
+5
? 最後の箱が {5} のとき：コストは 5 + 5 = 10
/ 133

68
0
3
K = 5
? 最後の箱が {3, 5} のとき：コストは 0 + 9 = 9
0 5
1
5
? 最後の箱が {5} のとき：コストは 5 + 5 = 10
9
+9
/ 133

69
K = 5
0 5 9
0 1 2
3 5 4
? 最後の箱が {3, 5, 4} である場合
/ 133

70
K = 5
? 最後の箱が {3, 5, 4} のとき：コストは 0 + 11 = 11
0 5 9
0 1 2
3 5 4
+11
/ 133

71
K = 5
? 最後の箱が {3, 5, 4} のとき：コストは 0 + 11 = 11
0 5 9
0 1 2
3 5 4
? 最後の箱が {5, 4} のとき：コストは 5 + 7 = 12
+7
/ 133

72
K = 5
0 5 9
0 1 2
3 5 4
+5
? 最後の箱が {3, 5, 4} のとき：コストは 0 + 11 = 11
? 最後の箱が {5, 4} のとき：コストは 5 + 7 = 12
? 最後の箱が {4} のとき：コストは 9 + 5 = 14
/ 133

73
K = 5
0 5 9
0 1 2
3 5 4
? 最後の箱が {3, 5, 4} のとき：コストは 0 + 11 = 11
? 最後の箱が {5, 4} のとき：コストは 5 + 7 = 12
? 最後の箱が {4} のとき：コストは 5 + 7 = 14
11
+11
/ 133

74
K = 5
0 5 9
0 1 2
3 5 4
? 最後の箱が {3, 5, 4, 9} である場合
? 最後の箱が {5, 4, 9} である場合
3
9
11
/ 133

75
K = 5
0 5 9
0 1 2
3 5 4
3
9
11
+29
? 最後の箱が {3, 5, 4, 9} のとき：コストは 0 + 29 = 29
/ 133

76
K = 5
0 5 9
0 1 2
3 5 4
3
9
11
? 最後の箱が {3, 5, 4, 9} のとき：コストは 0 + 29 = 29
+20
? 最後の箱が {5, 4, 9} のとき：コストは 5 + 20 = 25
/ 133

77
K = 5
0 5 9
0 1 2
3 5 4
3
9
11
? 最後の箱が {3, 5, 4, 9} のとき：コストは 0 + 29 = 29
? 最後の箱が {5, 4, 9} のとき：コストは 5 + 20 = 25
+15
? 最後の箱が {4, 9} のとき：コストは 9 + 15 = 24
/ 133

78
K = 5
0 5 9
0 1 2
3 5 4
3
9
11
? 最後の箱が {3, 5, 4, 9} のとき：コストは 0 + 29 = 29
? 最後の箱が {5, 4, 9} のとき：コストは 5 + 20 = 25
? 最後の箱が {4, 9} のとき：コストは 9 + 15 = 24
+5
? 最後の箱が {9} のとき：コストは 11 + 5 = 16
/ 133

79
K = 5
0 5 9
0 1 2
3 5 4
3
9
11
? 最後の箱が {3, 5, 4, 9} のとき：コストは 0 + 29 = 29
? 最後の箱が {5, 4, 9} のとき：コストは 5 + 20 = 25
? 最後の箱が {4, 9} のとき：コストは 9 + 15 = 24
? 最後の箱が {9} のとき：コストは 11 + 5 = 16
16
+5
/ 133

80
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
/ 133

81
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
? 最後の箱が {9, 11} のとき最適：コストは 11 + 9 = 20
+9
20
/ 133

82
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20
5
8
/ 133

83
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20
5
8
? 最後の箱が {8} のとき最適：コストは 20 + 5 = 25
25
+5
/ 133

84
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
/ 133

85
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
? 最後の箱が {9, 11, 8, 10} のとき最適：コストは 11 + 17 = 28
+17
28
/ 133

86
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
28
7
1
/ 133

87
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
28
7
1
+5
33
/ 133

88
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
28
7
1
33
8
7
/ 133

89
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
28
7
1
33
8
7
+5
38
/ 133

90
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
28
7
1
33
8
7
38
9
8
/ 133

91
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
28
7
1
33
8
7
38
9
8
? 最後の箱が {7, 8} のとき最適：コストは 33 + 7 = 40
40
+7
/ 133

92
最適解
K = 5
0 5 9
0 1 2
3 5 4
3
9
11 16
4
11
20 25
5 6
8 10
28
7
1
33
8
7
38
9
8
40
/ 133

93
オレンジの出荷は「区間分割」
0 1 2 3 4 5 6 7 8 9
? 系列データをいくつかの区間に分ける問題に一般化
? 区間分割の仕方を最適化する
? さまざまな分野の問題が、区間分割問題へと帰着される
/ 133

94
http://chasen.naist.jp/chaki/t/2009-09-30/doc/mecab-cabocha-nlp-seminar-2009.pdf
僕は君を愛している
僕は君を愛している
単語ごとに区切る
/ 133
実例 (1)：分かち書き

95
実例 (2)：タイムスケジューリング
? 各客になるべく早く荷物を届け終えたい！
? 制約 (1)「何時から何時の間に届けてほしい」
? 制約 (2)「?分間に 1 回は休憩が必要」 (by 法律)
→ どこで休憩をとるかを最適化したい！
休憩時間ごとに区切る

96
? 発電の on と o? のタイミングを最適化する
on o? on o?
? 需要供給バランスの考慮などもあって、各区間のコス
ト関数 f(i, j) はとても複雑なものになる
? 「?時間以上連続稼働」といった制約も考慮
/ 133
実例 (3)：発電計画問題

97
?さまざまな長さのパネルが順に並んでいる
?それをいくつかのグループに分ける方法を最適化する
/ 133
実例 (4)：パネルグループ分け

実務でも登場した問題 2 つ紹介
98
? AtCoder ARC 070 E - NarrowRectangles

ARC 070 E - NarrowRectangles
99
? 幅 1 の長方形が縦に並んでいる
? 各長方形を左右に動かして繋がっているようにしたい
? 総移動距離の最小値を求めよ

実例 (5)：発電量調節問題
100
? 毎分ごとに発電量を決めたい
? ただし急激な変化はできない
? 長方形の紙を繋げるという制約に対応する

101
アルゴリズムは分野横断的！
? JOI の問題も、まさにそういう問題たち
グラフ
動的計画法
○○法
電気機械化学生物経済 ○○
? さまざまな問題が、アルゴリズムの目で見ることに
よって本質的に同じ問題になったりなる！
/ 133

102
全体のまとめ
? JOI 頑張ってください！
? JOI 本選進出おめでとうございます！
? 大学入学後も競プロ人生は続く！
? 仲間をたくさん作ろう！
? 競プロが実務やキャリア形成で役に立つことも

狠狠撸

竞プロは人生の役に立つ！

Recommended

More Related Content

What's hot (20)

Similar to 竞プロは人生の役に立つ！ (11)

More from Kensuke Otsuki (11)

Recently uploaded (6)

竞プロは人生の役に立つ！