狠狠撸

プログラミングコンテスト
基礎テクニック
情報知識ネットワーク研究室 M2 谷陽太
12017/06/12, 2018/04/09 HCPC勉強会

目次
? テクニックの前に
? HCPC勉強会に来たときの心得
? 役立つ本の紹介
? 時間計算量の気持ち
? C++の便利機能入門
? 全探索
? 線形探索
? 深さ優先探索
? 簡単な算数
? 最大公約数と最小公倍数
? 素数判定
? 貪欲法
? シミュレーション 2
C言語の基礎的なプログラミングが
できることを前提に進めます
(Python勢やJava勢の人、ゴメンネ！)

目次
? 全探索
? 線形探索
? 簡単な算数
? 素数判定
? 貪欲法

HCPC勉強会に来たときの心得
分からなくなったら
必ずその場で質問すること！
4

HCPC勉強会に来たときの心得
分からなくなったら
必ずその場で質問すること！
5
以上！

役立つ本の紹介
もし、プロコンのために
1冊だけ本を読むとしたら……
プログラミングコンテスト
チャレンジブック
? 通称 ?蟻本?
? 基礎的なものから上級テクニックまで
例題と合わせて紹介されている
? 先輩に頼めば貸してくれる
? ただ、いきなり読むにはちょっとムズいかも
6

時間計算量 (Time Complexity) の気持ち
時間計算量: この方法で問題を解くと、
実行にどのくらい時間かかるの？という指標
プロコンでは、実行時間に関する制限があるので、
時間計算量を見積もることが大切 (1～2秒程度のことが多い)
7

時間計算量 (Time Complexity) の気持ち
時間計算量: この方法で問題を解くと、
実行にどのくらい時間かかるの？という指標
プロコンでは、実行時間に関する制限があるので、
時間計算量を見積もることが大切 (1～2秒程度のことが多い)
? ?このループは何回回ってるかな？?
?この関数は何回実行されてるかな？? という感じで見積もる
? だいたいN回の計算で終わることを O(N)時間と書く
8

例でみる時間計算量
? O(N)時間の例:
? O(N1
)時間の例:
? O(logN)時間の例:
? O(1)時間の例:
9

Oは大雑把のオー (と覚えればOK)
? 時間計算量は、細かな違いを無視して大雑把に見積もる
例1: ループ1周毎が重くても、例2: O(N1
+ N) みたいになったら、
O(N+N+N) みたいになっても、明らかに他より計算が軽い項は
定数倍は気にせず O(N) 無視して O(N1
)
10

実際の実行時間の概算
? 時間計算量を求めたら、実際の実行時間を概算しよう！
プロコンの問題には、入力される数値の制約が必ず書いてあるので、
それの最大値を、さっき求めた計算量にぶち込んでみる
11

実際の実行時間の概算
? 時間計算量を求めたら、実際の実行時間を概算しよう！
プロコンの問題には、入力される数値の制約が必ず書いてあるので、
それの最大値を、さっき求めた計算量にぶち込んでみる
基準: 今のパソコンは1秒間に?? ?
回程度の計算が可能
12
時間計算量プロコン的にOKなNの範囲
O(N1) N ≤ 10: 程度
O(NlogN) N ≤ 10; 程度
O(N) N ≤ 10< 程度
O(1) なんでもござれ

C++の便利機能入門
C++には、Cには無かった便利機能が満載
13

→ なので使おう！
14

→ なので使おう！
? たくさん紹介したいところだけど、今回は2つだけ紹介
15
いろいろ知りたい人は
HCPCのホームページへ！
HCPC活動記録 (初めてのSTL)
http://hcpc.web.fc2.com/activities.html

C++の便利機能その1: cin / cout
? 標準入出力が手軽にできる！
? scanf/prinf: 型によって %d とか %f とかを使い分けないといけない
? cin/cout : 型を意識する必要がない！便利！
16

C++の便利機能その2: vector
? 可変長配列！
17
C言語での配列の
完全上位互換と考えてOK

目次
? 全探索
? 線形探索
? 簡単な算数
? 素数判定
? 貪欲法

Q1.
3つの整数a, b, cが与えられるので、
aからbまでの中に、cの約数がいくつあるか求めよう！
? Constraints
1 ≤ ?, ?, ? ≤ 1000
a ≤ ?
? Time Limit
1 sec
19
5 6 7 8 9 10 11 12 13 14
例: a = 5, b = 14, c = 80 の場合 → 3つ

Q1.
? Constraints
1 ≤ ?, ?, ? ≤ 1000
a ≤ ?
? Time Limit
1 sec
20
5 6 7 8 9 10 11 12 13 14
例: a = 5, b = 14, c = 80 の場合 → 3つ
aからbまで順番に見ていって
cを割り切れるかチェックすればいい！
この手法を線形探索とよぶ

Q1.
? Constraints
1 ≤ ?, ?, ? ≤ 1000
a ≤ ?
? Time Limit
1 sec
21
5 6 7 8 9 10 11 12 13 14
例: a = 5, b = 14, c = 80 の場合 → 3つ
aからbまで順番に見ていって
cを割り切れるかチェックすればいい！
この手法を線形探索とよぶ

実装例
? 時間計算量: O(b)時間
b ≤ 1000 なので間に合う！
基本的に線形探索は
ループを回すだけなので
実装が簡単
22

Q2.
地図が描かれたH×Wの盤面が与えられるので、
家から魚屋まで辿り着けるかどうか判定しよう！
? Input
1行目 H W
2行目盤面の情報 ?(Q,Q) ?(Q,1) ? ?(Q,S)
:
H+1行目盤面の情報 ?(T,Q) ?(T,1) ? ?(T,S)
? Constraints
1 ≤ H, W ≤ 500
? Time Limit
2 sec
23
家
魚

地図が描かれたH×Wの盤面が与えられるので、
家から魚屋まで辿り着けるかどうか判定しよう！
? Sample Input
7 9
## . ##### .
. . . . s . . . .
. ## . # . ## .
. . # . # . ###
# . # . . . . . .
# . #### . ##
# . . . g . . . #
24
家
魚
Q2.
. : 通路
# : 壁
s : 家
g : 魚屋

どうやって解けばいいだろう？
? 例えば、この地図がダンジョンだったとしよう
あなたは勇者なので、
このダンジョンのすべての宝箱を
開けたいと思っている
25
勇
宝
宝宝
宝

Q. どうやって宝箱を探す？
26
勇
宝
宝宝
宝

A. こんな感じで探す！
27
勇
宝
宝宝
宝

A. こんな感じで探す！
この手法を
深さ優先探索とよぶ
28
勇
宝
宝宝
宝

深さ優先探索 (Depth First Search) の動き
方針: ダンジョンの壁沿いにどんどん突き進む！
行き止まりにぶつかったら、
ちょっと戻って別の道を行く！
29
家
魚
優先順位
上, 右, 下, 左の場合

30
★
魚
優先順位
最初に、スタート地点へ
探索済みフラグを立てる

31
？
★
魚
優先順位
優先順位に従って上を見るが
壁なので行けない

32
★ ！
魚
優先順位
次に右を見る → 行ける！

33
★
魚
優先順位
進む

34
★
魚
優先順位
進んだら、
その地点を ?探索済み? にする

35
？
★ ！
魚
優先順位
優先順位に従って
上を見るが行けず、
次に右を見ると行けそう

36
★
魚
優先順位
右に進んで、
そこを ?探索済み? にする

37
？
★ ！
魚
優先順位
同様に進む

38
？
★ ！
魚
優先順位
同様に進む

39
！
★
魚
優先順位
同様に進む

40
？ ★
？
魚
優先順位
4方向どこも行けなくなったら……

41
★
魚
優先順位
一歩戻る

42
★
！
魚
優先順位
この地点で上はもう試したので
右から順に試す
→ 下に行けそう

43
？
？ ★
？
魚
優先順位
進む → 再び行き止まり

44
？ ★
魚
優先順位
戻る

45
？ ★
？
魚
優先順位
戻る

46
？ ★
？
魚
優先順位
戻る

47
★
！
魚
優先順位
戻る

48
？
★ ？
！
魚
優先順位
進む

49
？
★ ？
！
魚
優先順位
進む

50
？
★ ！
魚
優先順位
進む

51
？
★ ！
魚
優先順位
進む

52
？
★ ！
魚
優先順位
進む

53
？
？ ★
？
魚
優先順位
進む

54
？ ★
？
魚
優先順位
戻る

55
★
！
魚
優先順位
戻る

56
？
★ ？
魚！
優先順位
進む

57
？
魚 ★ ！
優先順位
進む

58
？
魚？ ★ ？
優先順位
進む

59
魚！ ★
優先順位
戻る

60
？
！ ★ ？
優先順位
進む

61
★
優先順位
進む

62
★
優先順位
進む → あ、ここ魚屋じゃん

63
★
優先順位
進む → あ、ここ魚屋じゃん
ゴール地点に着いたら or
全地点を探索したら終了

深さ優先探索の実装方法
各地点で同じ処理をやっているが、進む方向が4つある
→ 普通のループでは厳しそう
64

→ 関数の再帰呼び出しを使おう！ (関数が自分自身を呼び出す方法)
? まずは、右図の関数の実行イメージをつかもう
65

例: a = 2の場合のイメージ
66
Hello と出力し、func(1) を実行
func(1)が終わったので、 World と出力し終了
func(2)
最初のif文に引っかかり、何もせず終了
func(1)
func(0)

67
func(2)
func(1)
func(0)

68
func(2)
func(1)
func(0)

69
func(2)
func(1)
func(0)

70
func(2)
func(1)
func(0)

実装例 (1/2)
71
? main関数部
入力を受け取るのに
二重ループ
→ O(HW)

実装例 (2/2)
? 探索部
この関数が
各地点につき
1回実行される
→ O(HW)
72

実装例 (2/2)
? 探索部
この関数が
各地点につき
1回実行される
→ O(HW)
合計 O(HW)
73

実装上のテクニック
? 方位配列 (命名僕):
?自分からみた4方向? をforループで手軽に回せる！
? 地図領域を余分に確保:
一番外側を壁にすることで配列外アクセスを防げる！
? 参照渡し:
これをやらないとやばい！
74

実装上のテクニック
? 方位配列 (命名僕):
?自分からみた4方向? をforループで手軽に回せる！
? 地図領域を余分に確保:
一番外側を壁にすることで配列外アクセスを防げる
? 参照渡し:
これをやらないとやばい！
75
深さ優先探索の仲間に
?幅優先探索? というのもあるので
気になった人はホームページへ！
HCPC活動記録 (最短路?最小全域木)
http://hcpc.web.fc2.com/activities.html

目次
? 全探索
? 線形探索
? 簡単な算数
? 素数判定
? 貪欲法

Q3.
2つの自然数x, yが与えられるので、最大公約数を求めよう！
? Input
x y
? Constraints
1 ≤ x, y ≤ 10]
? Time Limit
1 sec
77

Q3.
? Input
x y
? Constraints
1 ≤ x, y ≤ 10]
? Time Limit
1 sec
78
1つずつ順番に
「これxとyの公約数？」って
試していけばいいのでは？

Q3.
? Input
x y
? Constraints
1 ≤ x, y ≤ 10]
? Time Limit
1 sec
79
線形探索じゃ
間に合わない！
1つずつ順番に
「これxとyの公約数？」って
試していけばいいのでは？

公約数の特徴
? xとyの公約数は、必ずx%yの約数になっている (逆も然り)
→ つまり、xとyの最大公約数は、
yとx%yの最大公約数に一致する！
80
x=8
y=6
x%y=2

ユークリッドの互除法 (Euclidean Algorithm)
「aとbの最大公約数は
bとa%bの最大公約数である」
を、そのまま再帰で書くだけ
(bが0になったときのaが答え)
81

Q. 時間計算量はいくつになるの？
82

Q. 時間計算量はいくつになるの？
ちょっと解析してみよう
83

ユークリッドの互除法の解析
ここで着目すべき性質はコレ
?%? <
?
?
84
gcd(a, b)
gcd(b, a % b)
gcd(a % b, b % (a % b))
…

?%? <
?
?
? 仮にこれが満たされなかったら……
85
gcd(a, b)
gcd(b, a % b)
gcd(a % b, b % (a % b))
…
a
b
a%b
もう1個入る

?%? <
?
?
86
gcd(a, b)
gcd(b, a % b)
gcd(a % b, b % (a % b))
…
a
b
a%b
もう1個入る
再帰を2段階進むごとに
引数の値が半分以下に
→ 関数の呼び出し回数は高々2濒辞驳补程度

?%? <
?
?
87
gcd(a, b)
gcd(b, a % b)
gcd(a % b, b % (a % b))
…
a
b
a%b
もう1個入る
再帰を2段階進むごとに
引数の値が半分以下に
→ 関数の呼び出し回数は高々2濒辞驳补程度
→ O(loga)時間

ところで、最小公倍数は？
88

? xとyの最大公約数をGCD(x, y)
xとyの最小公倍数をLCM(x, y) とすると
LCM(x, y)GCD(x, y) = xy という性質がある
導出のポイント: x=nGCD(x, y), y=mGCD(x, y) と書いたとき
nとmは互いに素である
89

? xとyの最大公約数をGCD(x, y)
xとyの最小公倍数をLCM(x, y) とすると
LCM(x, y)GCD(x, y) = xy という性質がある
導出のポイント: x=nGCD(x, y), y=mGCD(x, y) と書いたとき
nとmは互いに素である
→ 最大公約数さえ求まれば、あとはO(1)で求まる！
90

Q4.
n個の自然数が与えられるので、
そのうち素数だったものの個数を求めよう！
? Input
1行目 N
2行目 1番目の自然数 ?Q
:
N+1行目 N番目の自然数 ?j
? Constraints
1 ≤ N ≤ 10;
1 ≤ ?k ≤ 10;
? Time Limit
1 sec
91

普通の素数判定
? 普通の素数判定は、
線形探索で O( ?) でできる
? a=bc という合成数だった場合
bとcの一方は必ず ?以下
92

普通の素数判定
? 普通の素数判定は、
線形探索で O( ?) でできる
? a=bc という合成数だった場合
bとcの一方は必ず ?以下
今回はこれをN回やる必要があるので O(N ?)
およそ?? ?
回の計算 → 厳しい
もっと高速なアルゴリズムが必要
93

エラトステネスの篩 (Sieve of Eratosthenes)
? 方針: あらかじめ ?素数かどうかテーブル? を作っておけば、
あとはそのテーブルを O(1) で参照すればいい
94
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
F F T T F T F T F F F T F T F F F T F T F F F T F

とはいえ、このテーブルが高速に作れなければ意味がない
95
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

ポイント: a以下の合成数は必ず ?以下の約数を持つ
96
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

ポイント: a以下の合成数は必ず ?以下の約数を持つ
→ ?以下の全自然数の倍数をfalseにしておけばいい
97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

テーブル構築の動き
? ? ≤ 80 の場合
98
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)

? ? ≤ 80 の場合
99
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)まず1だけfalseに初期化

? ? ≤ 80 の場合
100
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)次に2をチェック → 素数らしい

? ? ≤ 80 の場合
101
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)2の倍数をすべてfalseに

? ? ≤ 80 の場合
102
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)次に3をチェック → 素数らしい

? ? ≤ 80 の場合
103
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)3の倍数をすべてfalseに

? ? ≤ 80 の場合
104
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)4は素数じゃないらしいのでスルー

? ? ≤ 80 の場合
105
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)5は素数らしいので、その倍数を全部false

? ? ≤ 80 の場合
106
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)6はスルー

? ? ≤ 80 の場合
107
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)7は素数らしいので、その倍数を全部false

? ? ≤ 80 の場合
108
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)8はスルー

? ? ≤ 80 の場合
109
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
(青背景: true / 黄背景: false)80 < 9 なので終了

実装例
? テーブルの構築時間は
O(alogloga)時間
であることが知られている
? 調和級数の性質を用いると
O(aloga) 以下であることは
簡単に証明できる
? 素数の逆数和の発散速度の
性質を用いると
O(alogloga) が証明できるらしい
(誰かこの証明理解したら教えてね)
110

目次
? 全探索
? 線形探索
? 簡単な算数
? 素数判定
? 貪欲法

Q5.
1円玉?5円玉?10円玉?50円玉?100円玉?500円玉が、
それぞれ?Q枚??o枚??Qp枚??op枚??Qpp枚??opp枚ある
なるべく少ない枚数の硬貨でA円のものを買いたい！
最低何枚の硬貨で買い物ができるか
? Input
A
?Q ?o ?Qp ?op ?Qpp ?opp
? Constraints
1 ≤ A, ?k ≤ 10]
? Time Limit
1 sec
112

Q5.
? Input
A
? Constraints
1 ≤ A, ?k ≤ 10]
? Time Limit
1 sec
113
500円から順番に
使えるだけ使っていけばいい！
この手法を貪欲法とよぶ

Q5.
? Input
A
? Constraints
1 ≤ A, ?k ≤ 10]
? Time Limit
1 sec
114
500円から順番に
使えるだけ使っていけばいい！
この手法を貪欲法とよぶ

実装例
? 時間計算量: O(1)
正確には
O(硬貨の種類数)
115

目次
? 全探索
? 線形探索
? 簡単な算数
? 素数判定
? 貪欲法

Q6.
H 5の盤面に石が埋め込まれて、以下の手順で進行する
1. 同じ色の石が3つ以上水平に並んでいたら、その石は消える
2. 石が消滅したマスの上に石があれば、空きを埋めるように石が落ちる
3. すべての石が落ちきった後、1の条件を満たす石があれば1に戻る
最終的に、消滅した石の数字の合計がスコアになる
パズルの盤面が与えられるので、得られるスコアを求めよう！
117
? Input
1行目行数 H
2行目行1の石 ?Q,Q ?Q,1 ?Q,r ?Q,: ?Q,o
:
H+1行目行Hの石 ?T,Q ?T,1 ?T,r ?T,: ?T,o
? Constraints
1 ≤ H ≤ 10
1 ≤ ?k,s ≤ 9
? Time Limit
8 sec

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
118

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
119
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
スコア: 0

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
120
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
スコア: 0

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
121
5 9
5 5 5 5 9
4 6 6 9 9
3 3 3 6 9
2 2 2 9 9
スコア: 3

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
122
5 9
5 5 5 5 9
4 6 6 9 9
3 3 3 6 9
2 2 2 9 9
スコア: 3

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
123
9
9 9
5 9 6 9
4 6 6 9 9
スコア: 38

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
? Sample Output
38
124
9
9 9
5 9 6 9
4 6 6 9 9
スコア: 38

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
? Sample Output
38
125
9
9 9
5 9 6 9
4 6 6 9 9
スコア: 38
この様子をひたすら再現すればいい！
この手法をシミュレーションとよぶ

Q6.
? Sample Input
5
5 9 5 5 9
5 5 6 9 9
4 6 3 6 9
3 3 2 9 9
2 2 1 1 1
? Sample Output
38
126
9
9 9
5 9 6 9
4 6 6 9 9
スコア: 38
この様子をひたすら再現すればいい！
この手法をシミュレーションとよぶ

実装例
128
? ?? ?? ? + ? ? ?
= ?(? ?)

まとめ
プロコンで使う基礎テクニックを
学ぶことができた！
? とはいえ、頭では分かっていても、
実際にコードが書けるかどうかは別問題！
? 今日の内容に関連する問題を付録につけておいたので、
頑張って解こう！
129

付録 (1/3)
このスライドの写経で解ける問題
? 約数の数
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_D
http://atc001.contest.atcoder.jp/tasks/dfs_a
? 最大公約数
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B&lang=jp
? 素数判定 (MAX_Nを修正する必要あり)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C&lang=jp
? 連鎖消滅パズル
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1193&lang=jp
130

付録 (2/3)
頑張って解こう！
? 線形探索
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp
? Block
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0207
? 島の数
? おつり
131

付録 (3/3)
頑張って解こう！！
? 整数の和
? 竹の花
? Old Bridges
? Ennichi
132

狠狠撸

プログラミングコンテスト基础テクニック

Recommended

More Related Content

More from HCPC: 北海道大学競技プログラミングサークル (20)

Recently uploaded (11)

プログラミングコンテスト基础テクニック