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
競技プログラミングことはじめ
Search
E869120
November 22, 2022
Programming
47
21k
競技プログラミングことはじめ
第1章 競技プログラミングとは?(p.7~)
第2章 AtCoderの始め方(p.43~)
第3章 競プロで必要な「アルゴリズムと思考力」(p.86~)
スライドのまとめ(p.154~)
E869120
November 22, 2022
Tweet
Share
More Decks by E869120
See All by E869120
90 分で学ぶ P 対 NP 問題
e869120
15
6.5k
中学生でもわかる深層学習
e869120
54
30k
わかりやすい説明のための 10 の鉄則
e869120
302
280k
150 分で学ぶ高校数学の基礎
e869120
294
330k
30 分でわかる!アルゴリズムの基本
e869120
77
45k
数理最適化ことはじめ / Introduction to Mathematical Optimization
e869120
76
43k
50分で学ぶアルゴリズム / Algorithms in 50 minutes
e869120
141
92k
Other Decks in Programming
See All in Programming
地域ITコミュニティの活性化とAWSに移行してみた話
yuukis
0
240
Enterprise Web App. Development (1): Build Tool Training Ver. 5
knakagawa
1
110
Make Parsers Compatible Using Automata Learning
makenowjust
1
4.6k
趣味全開のAITuber開発
kokushin
0
200
The Efficiency Paradox and How to Save Yourself and the World
hollycummins
0
110
Compose Hot Reload is here, stop re-launching your apps! (Android Makers 2025)
zsmb
1
510
State of Namespace
tagomoris
4
1.6k
Deoptimization: How YJIT Speeds Up Ruby by Slowing Down / RubyKaigi 2025
k0kubun
0
820
新しいPHP拡張モジュールインストール方法「PHP Installer for Extensions (PIE)」を使ってみよう!
cocoeyes02
0
380
リストビュー画面UX改善の振り返り
splcywolf
0
140
自分のために作ったアプリが、グローバルに使われるまで / Indie App Development Lunch LT
pixyzehn
1
160
「影響が少ない」を自分の目でみてみる
o0h
PRO
2
1.1k
Featured
See All Featured
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Code Review Best Practice
trishagee
67
18k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.4k
How STYLIGHT went responsive
nonsquared
99
5.5k
Build The Right Thing And Hit Your Dates
maggiecrowley
35
2.6k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.2k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
41
2.2k
Thoughts on Productivity
jonyablonski
69
4.6k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
23
2.6k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.8k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
Transcript
競技プログラミングことはじめ 2022 年 11 月 22 日 米田 優峻 [@E869120]
1 [完全版]
162 自己紹介 2 米田 優峻 (よねだ まさたか) • 2002年生まれ •
2021年東京大学入学 主な実績 • 国際情報オリンピック ‘18, ‘19, ‘20 金メダル • 著書『アルゴリズム×数学』 • 著書『競技プログラミングの鉄則』
162 はじめに 3 現在、競技プログラミング(競プロ)の 人気が高まっています
162 はじめに 4 特に、国内最大級の競技プログラミングサイト AtCoder の 参加登録数は 400,000 人を突破しています
162 はじめに 5 そこで本スライドでは、 競技プログラミングとはどういうものか? AtCoder に登録する方法 競プロで求められるスキル などを紹介します! AtCoder
で問題を解く方法
162 目次 6 第1章 競技プログラミングとは 競技プログラミングとは/AtCoderについて/参加のメリット 第2章 AtCoder の始め方 AtCoder
の登録方法/AtCoder で問題を解いてみよう 第3章 競プロで必要な “アルゴリズムと思考力” 競プロで必要なスキル/アルゴリズムの知識/数学的思考力 ・・・・・・・・・・・・ 7 ・・・・・・・・・・・・・・ 43 ・・・・ 86
第 1 章 競技プログラミングとは
1 162 -1 競技プログラミングとは 8 プログラミングの問題を解く競技 競技プログラミングとは…
1 162 -1 競技プログラミングとは 9 基本的には、このような流れで競技が行われる 参加者にいくつかの 問題が与えられる 問題 A
問題 C 問題 B 問題を解く プログラムを実装 試験時間内に 多く得点した方が上位 2 1 3
1 162 -1 競技プログラミングとは 10 基本的には、このような流れで競技が行われる 参加者にいくつかの 問題が与えられる 問題 A
問題 C 問題 B 問題を解く プログラムを実装 試験時間内に 多く得点した方が上位 2 1 3
1 162 -1 競技プログラミングとは 11 基本的には、このような流れで競技が行われる 参加者にいくつかの 問題が与えられる 問題 A
問題 C 問題 B 試験時間内に 多く得点した方が上位 2 1 3 問題を解く プログラムを実装
1 162 -1 競プロの問題 12 Q. どんな問題が出されるか?
1 162 -1 競プロの問題 13 ※ここで問題を解く必要はありません。どんな問題が出されるかのイメージをつかんだら、次のページに進んでかまいません。 整数 𝑵, 𝑲 が与えられます。
𝟏 以上 𝑵 以下の 3 つの整数を重複 なしで選び、合計を 𝑲 にする方法 は何通りですか? 答えを出力するプログラムを作成 してください。 ※ 𝑵, 𝑲 は 100 以下
1 162 -1 競プロの問題 14 N, K = map(int, input().split())
Answer = 0 for x in range(1, N+1): for y in range(x+1, N+1): z = N-x-y if y < z: Answer += 1 print(Answer) プログラムを書く (基本的にどんな言語でもOK) 正しい出力をする プログラムを提出すれば正解! ※ここで問題を解く必要はありません。どんな問題が出されるかのイメージをつかんだら、次のページに進んでかまいません。 整数 𝑵, 𝑲 が与えられます。 𝟏 以上 𝑵 以下の 3 つの整数を重複 なしで選び、合計を 𝑲 にする方法 は何通りですか? 答えを出力するプログラムを作成 してください。 ※ 𝑵, 𝑲 は 100 以下
1 162 -1 競プロの問題 15 普通に解くと計算に時間がかかるため 解法の工夫が要求される 面白い問題もある ※詳しくは 3
章で説明します
1 162 -1 競プロの問題 16 普通に解くと計算に時間がかかるため 解法の工夫が要求される 面白い問題もある ※詳しくは 3
章で説明します 競技プログラミングのイメージは つかめましたか?
1 162 -1 コンテストの種類 17 Q. どんなコンテストがあるのか?
1 162 -1 GCJ 年に一度の世界大会 ICPC 大学生向けのチーム戦 情報オリンピック 中高生向けの大会 コンテストの種類
18 AtCoder 日本最大手のコンテスト 世界には様々なコンテストがあります
1 162 -1 GCJ 年に一度の世界大会 ICPC 大学生向けのチーム戦 情報オリンピック 中高生向けの大会 コンテストの種類
19 AtCoder 日本最大手のコンテスト 次節では最大規模の AtCoder について紹介します 毎週開催されるので 初心者にもおすすめできる!
1.1 1.2 1.3 AtCoder について 競技プログラミングとは AtCoder のレーティング 1.4 競プロに参加するメリット
1 162 -2 AtCoder とは 21 日本最大手のプログラミングコンテスト 毎週土曜の 21 時からコンテストが開催される
※日曜の同じ時間帯に開催されることもあります
1 162 -2 AtCoder とは 22 100 分で 8 問を解き、合計得点を競う
※コンテストの約 3 分の 2 を占める AtCoder Beginner Contest の場合
1 162 -2 AtCoder の特徴 23 AtCoder の 4 つの特徴
1 162 -2 AtCoder の特徴 24 1 2 3 4
参加費 場所 開催頻度 問題文 AtCoder は無料 運動系の大会は有料のものも多い が、AtCoder は基本的に無料で 参加できる※ ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く
1 162 -2 AtCoder の特徴 25 1 2 3 4
参加費 場所 開催頻度 問題文 オンライン開催 自分の PC を持っていれば、ネッ ト上でどこでも参加できる ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く
1 162 -2 AtCoder の特徴 26 1 2 3 4
参加費 場所 開催頻度 問題文 ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く 毎週開催される 情報オリンピックなどと比べて開 催頻度が高いので、定期的に実力 を確認できる
1 162 -2 AtCoder の特徴 27 1 2 3 4
参加費 場所 開催頻度 問題文 ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く 日本語の問題文がある 海外のコンテストとは異なり、問 題文が日本語で提供される。英語 が読めない人でも安心
1 162 -2 AtCoder の特徴 28 1 2 3 4
参加費 場所 開催頻度 問題文 ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く 日本語の問題文がある 海外のコンテストとは異なり、問 題文が日本語で提供される。英語 が読めない人でも安心 AtCoder は初心者でも 参加しやすい!
1.1 1.2 1.3 AtCoder について 競技プログラミングとは AtCoder のレーティング 1.4 競プロに参加するメリット
1 162 -3 AtCoder のレーティング 30 AtCoder ではコンテストの成績に応じて レーティング が付けられる
1 162 -3 AtCoder のレーティング 31 コンテストの成績が 良ければ増加し コンテストの成績が 悪ければ減少する
1 162 -3 AtCoder のレーティング 32 また、レーティングに応じて色が付けられる たとえば、レーティングが 2800 以上であ
れば赤色になる オレンジ 黄色 青色 水色 緑色 茶色 灰色 赤 400 800 1200 1600 2000 2400 2800
1 162 -3 AtCoder のレーティング 33 初心者は、まず茶色を目指しましょう! オレンジ 黄色 青色
水色 緑色 茶色 灰色 赤 400 800 1200 1600 2000 2400 2800 注意 茶色は下から 2 番目の色ですが、上位 40% なのでかなりすごいです。エンジニアで茶色 になれない人も多いです。
1.1 1.2 1.3 AtCoder について 競技プログラミングとは AtCoder のレーティング 1.4 競プロに参加するメリット
1 162 -4 競プロのメリット 35 AtCoder などのコンテストに参加する メリットは何か? 3 つ紹介します
1 162 -4 競プロのメリット 36 1 2 3 プログラミング力 思考力
楽しさ 競プロの問題を解くには、当然プ ログラムを書く必要がある コンテストに参加していくと プログラムを書く能力が身に つく! →
1 162 -4 競プロのメリット 37 詳しくは 3 章で説明するが、競 プロの問題の中には思考力が要求 されるものもある
問題を解いていくうちに数学 的思考力が身につく! → 1 2 3 プログラミング力 思考力 楽しさ
1 162 -4 競プロのメリット 38 1 2 3 プログラミング力 思考力
楽しさ さらに、プログラマにとって必須 のアルゴリズムの知識も身につけ ることができる!
1 162 -4 競プロのメリット 39 AtCoder では同時に 5000 人以 上の参加者と対戦できる(リアル
タイムの順位表もある) ゲーム感覚で楽しんで参加で きる! → 1 2 3 プログラミング力 思考力 楽しさ
1 162 -4 競プロのメリット:結論 40 このように、競技プログラミングでは… プログラムを書く能力 アルゴリズムの知識 数学的思考力・論理的思考力 などを楽しんで身につけることができる!
1 162 -4 競プロのメリット:結論 41 このように、競技プログラミングでは… プログラムを書く能力 アルゴリズムの知識 数学的思考力・論理的思考力 などを楽しんで身につけることができる!
というわけで 競技プログラミングに 参加しましょう!
1 162 -4 競プロのメリット:補足 42 なお、競プロが就職・転職や コーディングテストに 役立つ場合もある※ ※もちろん会社や業種によります。 例:AtCoder
対応の就活サイト (https://jobs.atcoder.jp/)
第 2 章 AtCoder の始め方
2 162 -0 第 2 章の内容 44 第 2 章では、いよいよ
AtCoder で競プロを 始める方法を解説します AtCoder で 問題を解くには? AtCoder に 登録するには?
2.1 2.2 2.3 AtCoder で問題を解こう AtCoder の登録方法 次の一歩へ 2.4 コードテストについて
2 162 -1 AtCoder の登録方法 46 まず、https://atcoder.jp にアクセスしてください (AtCoder と検索すれば、一番上に出てくると思います)
Step 1
2 162 -1 AtCoder の登録方法 47 下のような画面が出るので、新規登録ボタンを押してください (スマホの場合:画面右上のメニューバーを開いて新規登録を押す) Step 2
2 162 -1 AtCoder の登録方法 48 次に、登録フォームを埋めてください (ユーザー名・パスワードなどを入れる必要があります) Step 3
2 162 -1 AtCoder の登録方法 49 フォームを埋め終わったら、新規登録ボタンを押してください Step 4
2 162 -1 AtCoder の登録方法 50 これで登録完了!
2.1 2.2 2.3 AtCoder で問題を解こう AtCoder の登録方法 次の一歩へ 2.4 コードテストについて
2 162 -2 AtCoder で問題を解こう 52 それでは、早速 AtCoder のチュートリアル問題を 1
問解いてみましょう!
2 162 -2 AtCoder で問題を解こう 53 Step 1 まず、https://atcoder.jp/contests/abs にアクセスします
(AtCoder Beginners Selection と検索すると出てきます)
2 162 -2 AtCoder で問題を解こう 54 Step 2 すると、上のような画面が出るので参加登録ボタンを押します 続いて、「問題」ボタンを押します
2 162 -2 AtCoder で問題を解こう 55 Step 3 問題一覧が出てくるので、とりあえず 一番上の「PracticeA
- Welcome To AtCoder」を開きます ※ 1 問目の「Welcome to AtCoder」はチュートリアル用に作られた問題です
2 162 -2 AtCoder で問題を解こう 56 Step 4 これで、解きたい問題を開くことができました。
2 162 -2 AtCoder で問題を解こう 57 それでは、問題文の意味を確認していきましょう
2 162 -2 AtCoder で問題を解こう 58 本文 制約 AtCoder の問題文は、本文・制約・入出力形式・例の
4 つの部分に分かれています 入出力形式 例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 6 test
2 162 -2 AtCoder で問題を解こう 59 本文では、どのような問題を解けばよいのかが 説明されています 制約 入出力形式
例 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 本文 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 6 test
2 162 -2 AtCoder で問題を解こう 60 制約では、入力としてどのようなデータが 与えられるかが記されています 本文 入出力形式
例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 制約 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 6 test つまり、𝒂 = 𝟏𝟎𝟏 のようなデータが与 えられることはないと思ってよい! ※2 章では制約をあまり気にしなくても良 いですが、3 章では重要になります。
2 162 -2 AtCoder で問題を解こう 61 入出力形式では、どういうフォーマットで入力・出力を 行えば良いかが記されています 本文 入出力形式
例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 制約 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 ※フォーマットに従わなければ不正解となる場合がありますので、注意してください たとえばこの問題では、入力として • 1 行目に 𝒂 が与えられる • 2 行目に 𝒃, 𝒄 が空白区切りで与えられる • 3 行目に 𝒔 が与えられる 6 test
2 162 -2 AtCoder で問題を解こう 62 本文 制約 例では、「どういう入力であればどういう出力が正しいか」の 具体例が示されています
入出力形式 例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 6 test
2 162 -2 AtCoder で問題を解こう 63 問題文は理解できましたか? それでは実際に解いてみましょう
2 162 -2 AtCoder で問題を解こう 64 Step 4 問題を解くプログラムを実装します 例:C++/Python
の場合、以下のコードを書けば良いです #include <iostream> #include <string> using namespace std; int main() { int a, b, c; string s; cin >> a >> b >> c >> s; cout << a+b+c << “ “ << s << endl; return 0; } C++ # 入力 a = int(input()) b, c = map(int, input().split()) S = input() # 出力 print(str(a+b+c) + “ “ + s) Python
2 162 -2 AtCoder で問題を解こう 65 Step 5 実装ができたら、問題文下部の提出欄にソースコードを貼り付け 提出ボタンを押しましょう
2 162 -2 AtCoder で問題を解こう 66 Step 6 すると、上のような提出画面が表示されます 最初は
WJ ですが、自動で採点されて約 10 秒で AC に変わります
2 162 -2 AtCoder で問題を解こう 67 「AC」と出れば正解です おめでとうございます!!!
2 162 -2 判定について 68 # 入力 a = int(input())
b, c = map(int, input().split()) S = input() # 出力 print(str(a*b*c) + “ “ + s) WA なお、不正解であれば「WA」という判定が出る (たとえば、a+b+c の代わりに a*b*c を出力するプログラムを提出すると WA)
2 162 -2 判定について 69 そのほかにも、上の表に示すような判定がある 正解 不正解(1 つ以上のケースで間違った出力をしている) 実行時間制限超過(詳しくは
3 章で説明します) 実行時エラー(0 割りなど) コンパイルエラー 採点中 AC WA TLE RE CE WJ
2.1 2.2 2.3 AtCoder で問題を解こう AtCoder の登録方法 次の一歩へ 2.4 コードテストについて
2 162 -3 次のステップへ 71 それでは、チュートリアル問題の次は どうすれば良いのか?
2 162 -3 チュートリアル問題の次は? 72 Step 1 プログラミングの基本文法に慣れていない人は C++ 入門用教材
APG4B を解く ※URL:https://atcoder.jp/contests/APG4b
2 162 -3 チュートリアル問題の次は? 73 Step 2 AtCoder Beginners Selections
を解いて 競プロの問題のイメージをつかむ ※URL:https://atcoder.jp/contests/abs
2 162 -3 チュートリアル問題の次は? 74 Step 3 これでコンテストに出る準備は万端! コンテストに出場しよう! 2
1 3
2 162 -3 コンテストについて 75 コンテストに関する注意
2 162 -3 コンテストについて 76 AtCoder には 4 種類のコンテストがありますが… 初心者には
ABC がオススメ! 注意1 AtCoder Beginner Contest (ABC) AtCoder Regular Contest (ARC) AtCoder Grand Contest (AGC) AtCoder Heuristic Contest (AHC)
2 162 -3 コンテストについて 77 ただし、ABC は Beginner Contest という名前ですが
それほど簡単ではないことに注意! 注意2 初心者は 8 問中 2 問解ければ十分です※ ※筆者(2022/11/21 時点で国内ランキング18位)でも全問正解できないことの方が多いです。 ※ ARC や AGC はさらに難しいです。 簡単だと思って参加したら解けなくて挫折する人が多いです Beginner Contest という名前が問題だと思うのですが…
2.1 2.2 2.3 AtCoder で問題を解こう AtCoder の登録方法 次の一歩へ 2.4 コードテストについて
2 162 -3 コードテストについて 79 最後に、AtCoder 上でプログラムを 実行できる便利な機能 コードテスト の使い方を紹介します
2 162 -3 コードテストについて 80 Step 1 まず、コンテストページ右上の コードテストをクリックします ※上の画像は、2.2
節で扱った AtCoder Beginners Selection の場合の例となっています。
2 162 -3 コードテストについて 81 Step 2 すると、このような画面が出て くるので、ソースコードと入力 を書きます
ここに ソースコードを書く ここに入力を書く
2 162 -3 コードテストについて 82 Step 3 それが終わったら、実行ボタン を押します ※右図のソースコードは、2
つの整数 𝒂, 𝒃 を入力し、𝒂 + 𝒃 を出力するものです
2 162 -3 コードテストについて 83 Step 4 数秒待つと、画面下部に実行結果 が出力されます ※たしかに正しい値
123+456=579 が 出力されているのがわかります
2 162 -3 コードテストについて 84 Step 4 数秒待つと、画面下部に実行結果 が出力されます ※たしかに正しい値
123+456=579 が 出力されているのがわかります コードテストの使い方は わかりましたか?
2 162 -3 コードテストについて 85 コードテストを使えば、手元に実行環境がなくても Web 上でプログラムを実装できます 必要な人はぜひ活用しましょう!
第 3 章 アルゴリズムと思考力
3 162 -1 ここまでの振り返り 87 第 1 章・第 2 章では、
競技プログラミングとは何か? AtCoder とは何か? AtCoder で問題を解く方法は? などを解説しました
3 162 -1 新たな疑問 88 それでは、競プロではどういうスキルが 求められるのか?
3 162 -1 競プロの流れ(再掲) 89 まず競プロでは、プログラムを実装する必要があります 参加者にいくつかの 問題が与えられる 問題 A
問題 C 問題 B 試験時間内に 多く得点した方が上位 2 1 3 問題を解く プログラムを実装
3 162 -1 競プロの流れ(再掲) 90 そのため、「プログラムを書く能力」が当然求められます 参加者にいくつかの 問題が与えられる 問題 A
問題 C 問題 B 問題を解く プログラムを実装 試験時間内に 多く得点した方が上位 2 1 3
3 162 -1 競プロで必要なスキル 91 しかし、プログラミング能力だけで 十分なのでしょうか?
3 162 -1 競プロで必要なスキル 92 競プロの難しい問題を解くためには 「アルゴリズム」と「数学的思考力」も重要になります 数学的思考力 アルゴリズムの知識 ?
※「アルゴリズム」という言葉の意味は、p.XXX で説明されています
3 162 -1 • 3.2 節/3.3 節では、アルゴリズムの知識や数学的思考力がどういう 問題で活躍するのかを紹介します • 皆さん、ぜひ楽しんでお読みください!
第 3 章の内容 93 ※難しかったら読み飛ばしても構いません。
3.1 3.2 3.3 アルゴリズムの知識 競プロで求められるスキル 数学的思考力
3 162 -2 アルゴリズムが重要となる例 95 まずは迷路の問題を考えてみましょう
3 162 -2 迷路の問題 96 1 手で上下左右に隣り合うマスに移動できる スタートからゴールへ 最短何手で移動できるか? ゴール
S G スタート ※ただし、迷路の大きさは 50×50 まで。
3 162 -2 迷路の問題 97 たとえば、全部の経路を調べれば 答えを求めることができる
3 162 -2 迷路の問題:全探索 98 ところが、スタート地点から出発する経路はたくさんある!
3 162 -2 迷路の問題:全探索 99 ところが、スタート地点から出発する経路はたくさんある! 約 150,000 通り
3 162 -2 迷路の問題:全探索 100 さらに迷路が大きくなると…
3 162 -2 迷路の問題:全探索 101 >15万通り
3 162 -2 迷路の問題:全探索 102 >1400万通り >15万通り
3 162 -2 迷路の問題:全探索 103 >1400万通り >380億通り >15万通り
3 162 -2 迷路の問題:全探索 104 >380億通り 実は、コンピュータの演算速度は 毎秒 1 億回程度
つまり単純に割り算しても 5 分以上かかることに! ※実行環境やプログラミング言語によって変わりますが、AtCoder 上で Python を動かした場合、毎秒 1 億回程度になります
3 162 -2 迷路の問題:全探索 105 >380億通り コンピュータの演算速度は 毎秒 1 億回程度
つまり単純に割り算しても 5 分以上かかることに! ※実行環境やプログラミング言語によって変わりますが、AtCoder 上で Python を動かした場合、毎秒 1 億回程度になります そして競プロの問題では、数秒以内で実行が終わらなければ 不正解となってしまう!
3 162 -2 迷路の問題:解法の工夫 106 そこで、解法を工夫すると とても簡単に答えを求めることができる
3 162 -2 迷路の問題:解法の工夫 107 0 スタートに 0 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 108 0 1 0 の隣に 1
を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 109 0 1 2 1 の隣に
2 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 110 0 1 2 3 2
の隣に 3 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 111 0 4 1 2 3
4 3 の隣に 4 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 112 0 4 5 1 2
3 4 5 4 の隣に 5 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 113 0 4 5 6 1
2 3 4 6 5 5 の隣に 6 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 114 0 4 5 6 1
2 3 7 4 7 6 5 6 の隣に 7 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 115 0 4 5 6 1
2 3 7 4 8 7 6 5 8 7 の隣に 8 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 116 0 4 5 6 1
2 3 7 4 8 9 7 6 5 9 8 9 8 の隣に 9 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 117 0 4 5 6 1
2 3 7 4 8 9 10 7 6 5 9 10 8 10 9 10 9 の隣に 10 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 118 0 4 5 6 1
2 3 7 11 4 8 9 10 7 6 5 9 10 8 11 10 9 11 10 11 11 10 の隣に 11 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 119 0 4 5 6 12
1 2 3 7 11 4 8 9 10 7 6 5 9 10 8 11 10 9 12 11 12 10 11 12 11 12 12 11 の隣に 12 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 120 0 4 5 6 12
13 1 2 3 7 11 4 8 9 10 7 6 5 9 10 8 11 10 9 13 12 11 12 13 10 11 12 13 11 12 13 12 13 12 の隣に 13 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 121 0 4 5 6 12
13 14 1 2 3 7 11 4 8 9 10 7 6 5 9 10 8 11 10 14 9 13 12 11 12 13 10 11 12 13 11 12 13 12 13 14 13 の隣に 14 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 122 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 7 6 5 9 10 8 11 10 14 15 9 13 12 11 12 13 10 11 12 13 11 12 13 12 13 14 15 14 の隣に 15 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 123 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 8 11 10 14 15 16 9 13 12 11 12 13 10 11 12 13 11 12 13 12 13 14 15 16 15 の隣に 16 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 124 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 17 8 11 10 14 15 16 9 13 12 11 12 13 17 10 11 12 13 11 12 13 17 12 13 14 15 16 16 の隣に 17 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 125 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 17 8 11 10 14 15 16 9 13 12 11 12 13 17 10 11 12 13 18 11 12 13 17 18 12 13 14 15 16 17 の隣に 18 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 126 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 17 8 11 10 14 15 16 9 13 12 11 12 13 17 10 11 12 13 19 18 11 12 13 17 18 19 19 12 13 14 15 16 18 の隣に 19 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 127 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 17 8 11 10 14 15 16 9 13 12 11 12 13 17 10 11 12 13 19 18 11 12 13 17 18 19 20 19 12 13 14 15 16 20 20 19 の隣に 20 を書く ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 迷路の問題:解法の工夫 128 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 17 8 11 10 14 15 16 9 13 12 11 12 13 17 10 11 12 13 19 18 11 12 13 17 18 19 20 19 12 13 14 15 16 20 20 19 の隣に 20 を書く ※書かれた数は、スタートからの最短手数を意味します。 ゴールまでの最短手数は 20 手!
3 162 -2 迷路の問題:解法の工夫 129 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 17 8 11 10 14 15 16 9 13 12 11 12 13 17 10 11 12 13 19 18 11 12 13 17 18 19 20 19 12 13 14 15 16 20 20 19 の隣に 20 を書く ※書かれた数は、スタートからの最短手数を意味します。 ゴールまでの最短手数は 20 手! この方法であれば コンピュータで 0.01 秒!
3 162 -2 迷路の問題:補足 130 0 4 5 6 12
13 14 1 2 3 7 11 15 4 8 9 10 16 7 6 5 9 10 16 17 8 11 10 14 15 16 9 13 12 11 12 13 17 10 11 12 13 19 18 11 12 13 17 18 19 20 19 12 13 14 15 16 20 20 なお、ゴール地点から始めて 20→19→18→ 17→… と数字が小さくなる方向に動くと、具体 的な最短経路がわかる ※書かれた数は、スタートからの最短手数を意味します。
3 162 -2 解法を思いつくために 131 さて、一体どうすれば こんな解法が思いつけるのか?
3 162 -2 解法を思いつくために 132 以下のような「典型的なアルゴリズム」を 知っているだけで結構変わる! 累積和 二分探索 動的計画法
深さ優先探索 幅優先探索 ダイクストラ法 素数判定法 ユークリッドの互除法 繰り返し二乗法
3 162 -2 解法を思いつくために 133 たとえば迷路の場合は「幅優先探索」を 知っていれば思いつける 累積和 二分探索 動的計画法
深さ優先探索 幅優先探索 ダイクストラ法 素数判定法 ユークリッドの互除法 繰り返し二乗法
3 162 -2 補足 134 補足:アルゴリズムとは?
3 162 -2 • 問題を解く手順(解法)のことを、プログラミングの文脈では アルゴリズムという • 基本的には、計算の速く終わる方が「良いアルゴリズム」 • たとえば迷路の問題の場合、経路を全部調べるアルゴリズムより、隣に数を書
いていくアルゴリズムの方が、良いといえる 補足:アルゴリズムとは? 135 ※なお、特に競プロ以外の文脈では、良いアルゴリズムの指標として、計算時間だけでなくメモリ使用量などが使われることもあります
3.1 3.2 3.3 アルゴリズムの知識 競プロで求められるスキル 数学的思考力
3 162 -3 数学的思考が重要になる例 137 まず、コマを移動させる問題を 考えてみましょう
3 162 -3 ピッタリ移動する問題 138 • 5 個のマスが一列に並んだマス目がある • 隣り合うマスへの移動をちょうど
𝑵 回行うことで、左端から右端に移動する ことはできるか? 5 個 ゴール スタート ※制約:𝑵 は 1 以上 100 以下 (入力は 𝑵 のみ)
3 162 -3 ピッタリ移動する問題 139 例:𝑵 = 𝟑 の場合 1
2 3 No… そもそもたどり着かない…
3 162 -3 ピッタリ移動する問題 140 1 2 3 4 5
6 よし、行けた! 例:𝑵 = 𝟔 の場合 Yes!
3 162 -3 ピッタリ移動する問題 141 1 2 3 5 4
1 回余ってしまう… 例:𝑵 = 𝟓 の場合 No…
3 162 -3 ピッタリ移動する問題:全探索 142 それでは、どうやって解けば良いか?
3 162 -3 ピッタリ移動する問題:全探索 143 まず、あり得る経路を全部調べれば、答えがわかる (例:𝑵 = 𝟓 の場合、上の
9 通りが全部ダメなので答えは No)
3 162 -3 ピッタリ移動する問題:全探索 144 まず、あり得る経路を全部調べれば、答えがわかる (例:𝑵 = 𝟓 の場合、上の
9 通りが全部ダメなので答えは No) 約 5,600億 通り しかし、𝑵 = 𝟓𝟎 になると コンピュータでも無理!
3 162 -3 ピッタリ移動する問題:全探索 145 まず、あり得る経路を全部調べれば、答えがわかる (例:𝑵 = 𝟓 の場合、上の
9 通りが全部ダメなので答えは No) 約 5,600億 通り しかし、𝑵 = 𝟓𝟎 になると コンピュータでも無理! そこで、「偶奇で場合分けする」という 数学的思考をすると簡単に解ける!
3 162 -3 工夫した解法 146 まず、𝑵 が偶数の場合 𝑵 = 𝟐
の場合は、手数的に無理だが 𝑵 ≥ 𝟒 の場合は、ゴールまで一直線に進んだ後、ゴール付近を 往復すれば良いので Yes
3 162 -3 工夫した解法 147 まず、𝑵 が偶数の場合 𝑵 = 𝟐
の場合は、手数的に無理だが 𝑵 ≥ 𝟒 の場合は、ゴールまで一直線に進んだ後、ゴール付近を 往復すれば良いので Yes 𝑵 = 𝟒 のとき 𝑵 = 𝟔 のとき 𝑵 = 𝟖 のとき
3 162 -3 工夫した解法 148 一方、𝑵 が奇数の場合 左から 1・3・5 マス目を青、2・4
マス目を白で塗ると…
3 162 -3 工夫した解法 149 一方、𝑵 が奇数の場合 左から 1・3・5 マス目を青、2・4
マス目を白で塗ると… 青 白 青 白 青 白 青 白 青 白 白 青 青 白 白 白 青 青 必ず「青→白→青→白→…」 という順番で移動 𝑵 が奇数のときは白色で終わる
3 162 -3 工夫した解法 150 一方、𝑵 が奇数の場合 左から 1・3・5 マス目を青、2・4
マス目を白で塗ると… 白 白 白 必ず「青→白→青→白→…」 という順番で移動 𝑵 が奇数のときは白色で終わる たしかに 𝑵 = 𝟓 のときは 全部白色で終わっている
3 162 -3 工夫した解法 151 一方、𝑵 が奇数の場合 左から 1・3・5 マス目を青、2・4
マス目を白で塗ると… 白 白 白 必ず「青→白→青→白→…」 という順番で移動 𝑵 が奇数のときは白色で終わる たしかに 𝑵 = 𝟓 のときは 全部白色で終わっている ところが、ゴールのマスは青色である 𝑵 が奇数のときは、答えは No
3 162 -3 工夫した解法 152 このように、偶奇で場合分けして考えると、簡単に答えがわかる 𝑵 が偶数の場合 𝑵 が奇数の場合
𝑵 = 𝟐 でなければ Yes 絶対に No
3 162 -3 工夫した解法 153 競技プログラミングでは、今回のように 数学的思考力 が必要な問題が出ることもある!
スライドのまとめ
4 162 • 競技プログラミングは、プログラミングの問題を速く正確に解く競技で あり、略して競プロと呼ばれることもある • 世界では様々な競プロの大会がある • AtCoder、情報オリンピック、ICPC、Google Code
Jam など • 第 2 章では、AtCoder の使い方を中心に説明した スライドのまとめ 155
4 162 スライドのまとめ 156 もちろん競プロでは、速くプログラムを書く能力も重要
4 162 スライドのまとめ 157 しかし競プロでは、数秒以内に実行が終わる 効率的なプログラムが求められる!
4 162 スライドのまとめ 158 したがって、より良い解法を考えるための アルゴリズムの知識と数学的思考力も同じくらい重要! ? (そして、解法を考える部分が一番面白い!)
4 162 スライドのまとめ 159 さて、アルゴリズムと思考力を 身につけるには?
4 162 本の紹介 160 競技プログラミングの鉄則 2022年9月発売/筆者が執筆 フルカラーの図が豊富で分かりやすい! AtCoder 自動採点システム付きの演習問題! C++/Python/Java
に対応! 特徴 1 2 3 興味のある方はぜひお読みください! ※なお、本の紙面には C++ しか載っていませんが、サポートページには Python/Java のプログラムがすべて載っています 発売2カ月で4刷
4 162 1. 米田優峻:『競技プログラミングの鉄則』(マイナビ出版、2022) 2. 米田優峻:『「アルゴリズム×数学」が基礎からしっかり身につく本』(技術評論社、2021) 3. 大槻兼資:『プログラミングコンテストAtCoder入門』(KADOKAWA、2022) 4. 米田優峻:『レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編:競プロを始めよう】』
(Qiita で公開) 5. 大槻兼資:『AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~』 (Qiita で公開) 6. テレ東BIZ:未経験者のアナタもハマる?競技プログラミング「AtCoder」って何だ?【橋本幸治の理系通信】 7. https://atcoder.jp/ 参考文献 161
最後までスライドをお読みいただき ありがとうございました