Python AtCoder入門 第0講 はじめに

Python AtCoder入門 第0講 はじめに 〜 AtCoderの世界へようこそ Pythonの入門書を1冊終えた。 print も if も for も書ける。 では、次に何を作ればいいのでしょうか。 1

文法を覚えた、その次へ 多くの人がここで立ち止まります。 文法は習った でも何を作ればいいかわからない 作りたいものも特にない そのうち for 文の書き方を忘れていく そんな人におすすめしたいのが、 競技プログラミング（Competitive Programming） です。 2

日本の競技プログラミングといえば 日本で競技プログラミングといえば、 AtCoder です。 問題を読み、考え、プログラムを書き、自動採点に提出する。 この流れを繰り返しながら、Pythonを「使える道具」に変えていきます。 3

0-1 AtCoderとは何か AtCoderは、日本語で参加できるプログラミングコンテストのサイトです。 毎週末のように、 ABC（AtCoder Beginner Contest） が開催されています。 初心者から世界トップクラスの選手まで、同じ問題に同時に挑みます。 4

コンテストの流れ 1. 決められた時刻に問題が公開される 2. 問題文を読む 3. 解き方を考える 4. プログラムを書く 5. コードを提出する 6. 自動採点の結果を確認する 7. AC なら正解 やることは、とてもシンプルです。 5

コンテストに参加しなくても学べる AtCoderは無料で利用できます。 また、必ずしも本番コンテストに参加する必要はありません。 過去問だけ解く 時間を気にせず考える 解説を読んで復習する こうした練習だけでも十分に上達できます。 6

ABCの問題構成 ABCの問題は、易しい順に並びます。 A問題 B問題 C問題 D問題 … 本書では、 A問題とB問題を確実に解けるようになること を目標にします。 7

A問題 A問題では、 入力を受け取る 簡単な計算をする 条件分岐をする 答えを出力する といった処理が中心です。 数行で書ける問題も珍しくありません。 8

B問題 B問題では、 N個のデータを処理する リストを使う 文字列を操作する 条件に従ってシミュレーションする といった処理が増えてきます。 本書で特に重点的に練習する領域です。 9

C問題以降 C問題以降では、 効率のよい解き方 が重要になります。 たとえば、 全探索 累積和 二分探索 幅優先探索 動的計画法 などです。 ただし、本書ではまずその前段階を固めます。 10

レーティングと「色」 AtCoderでは、コンテストの成績に応じてレーティングが付きます。 色 レーティング 目安 灰色 0〜399 参加を始めたばかり 茶色 400〜799 A・B問題が安定 緑色 800〜1199 C問題も解ける 水色 1200〜1599 アルゴリズムを使いこなせる 11

最初の目標は「茶色」 始めたばかりの人は灰色です。 最初の目標は、 茶色 です。 そして、灰色から茶色へ上がるために必要なのは、天才的なひらめきではありません。 12

必要なのは「基礎を迷わず書ける力」 たとえば、 N個の数を受け取って、条件を満たすものを数える この程度の処理を、 詰まらず 迷わず バグらせず 数分で 書けるようになる。 まずは、そこを目指します。 13

0-2 なぜ競技プログラミングをやるのか 競技プログラミングで身につく力は、 そのままプログラミング全般の土台になります。 特に重要なのは次の3つです。 1. 手が動くようになる 2. 効率を考えるようになる 3. 問題を解くこと自体が面白い 14

① 「手が動く」ようになる 初心者と経験者の差は、 知識量だけではありません。 大きな差が出るのは、 頭の中の考えをコードにする速度 です。 15

繰り返すことで、コードが自然に出てくる 競技プログラミングでは、 問題を読む 解き方を考える コードにする 提出する という作業を何度も繰り返します。 その結果、 if や for 、リスト操作が自然に出てくるようになります。 16

読むだけでは身につかない 入門書を読んで理解することは大切です。 しかし、 「読んでわかる」と「書ける」は別物 です。 最終的に手を動かせるようにしてくれるのは、 自分で書いた量 です。 17

② 「動けばいい」からの卒業 AtCoderには、 実行時間制限 があります。 多くの問題では、数秒以内に処理を終える必要があります。 18

同じ答えでも、処理方法で差が出る 「10万個のデータを処理してください」 という問題で、 素直に書くと間に合わないことがあります。 そこで初めて、 同じ答えを、もっと少ない手数で出せないか？ と考えるようになります。 19

効率を考える習慣 この視点は、競技プログラミングだけのものではありません。 大量データを扱うとき、 無駄な処理を減らす 同じ計算を繰り返さない 適切なデータ構造を選ぶ といった考え方につながります。 20

③ 単純に、面白い 問題文を読む。 よくわからない。 小さな例を書いてみる。 手で答えを出してみる。 規則が見えてくる。 そして、 「あ、こうすればいいのか！」 となる。 21

ACの気持ちよさ ひらめきをコードにして提出する。 そして画面に、 AC と表示される。 この達成感が、競技プログラミングの大きな魅力です。 しかも、遊んだ分だけプログラミングの力が残ります。 22

0-3 なぜPythonで始めるのか AtCoderでは多くの言語が使えます。 本書では、 Python を使います。 灰色から茶色を目指す段階では、Pythonに大きなメリットがあります。 23

Pythonは「書きたいこと」を短く書ける たとえば、 「リストの中身を全部足す」 なら、 sum(A) と書くだけです。 余計な記述が少ないため、 問題を考えることに集中できます。 24

データ構造が最初から揃っている Pythonには、 リスト 辞書 集合 タプル が標準で用意されています。 競技プログラミングでは、これらを非常によく使います。 25

標準ライブラリも強力 さらに、 collections itertools などの標準ライブラリを使うと、 面倒な処理を簡潔に書ける場合があります。 本書の後半では、こうした道具も扱います。 26

大きな整数でも壊れない 多くの言語では、 整数が扱える範囲を超えると、 オーバーフロー が起こることがあります。 Pythonでは、非常に大きな整数もそのまま扱えます。 27

Pythonなら巨大な整数も計算できる たとえば、 2 ** 100 10 ** 1000 のような値も扱えます。 初学者にとって、 整数の上限をあまり気にしなくてよい というのは大きなメリットです。 28

Pythonは遅い？ 「Pythonは遅いのでは？」 と心配する人もいます。 しかし、A・B問題の学習段階では、 まず気にするべきなのは実行速度ではありません。 29

まず速くするべきは「自分のコーディング」 重要なのは、 あなたがコードを書く速度 です。 入力をすぐ書ける 条件分岐を迷わない リスト操作が自然に書ける こうした力のほうが、最初はずっと重要です。 30

0-4 本書の対象読者 本書は、次のような人を想定しています。 Pythonの入門書を1冊終えた 次に何をすればよいかわからない AtCoderに登録したが入力でつまずいた A問題は解けるがB問題で止まる リストや辞書をなんとなく使っている 31

前提にする知識 次の内容は、すでに学んだことがある前提です。 変数 if for print 基本的な四則演算 完全な未経験者向けではありません。 32

本書のゴール 全16講を終えたとき、次の状態を目指します。 1. 入力形式を見ただけで受け取りコードを書ける 2. リスト・タプル・文字列・辞書・集合を使い分けられる 3. ABCのA・B問題を安定してACできる 33

本書ではアルゴリズムを扱わない 本書では、 本格的なアルゴリズム学習は扱いません。 なぜなら、 その前に身につけるべきことがあるからです。 34

「解法を理解する」と「コードにする」は別 解説を読んで、 なるほど、そう解けばいいのか と理解できても、 それをコードにできなければACにはなりません。 初心者がつまずきやすいのは、 理解した解法をコードにする段階 です。 35

まずPythonを「道具」にする 本書では、 Pythonを迷わず使えるようにすること だけに集中します。 ここが固まっていれば、 その後のアルゴリズム学習はかなり楽になります。 36

0-5 本書の構成 本書は、4つの部で構成します。 第1部：問題を解く準備 第2部：データをまとめて扱う 第3部：道具を増やす 第4部：総仕上げ 37

第1部 問題を解く準備 対象： 第1講〜第4講 扱う内容： 入出力 四則演算 条件分岐 ループ AtCoderで問題を解くための基本装備を整えます。 38

第2部 データをまとめて扱う 対象： 第5講〜第9講 扱う内容： リスト タプル 内包表記 文字列 2次元リスト 関数 B問題で必要になる処理を身につけます。 39

第3部 道具を増やす 対象： 第10講〜第14講 扱う内容： 辞書 集合 collections itertools ソート クラス 正しい道具を選び、短く読みやすいコードを書けるようにします。 40

第4部 総仕上げ 対象： 第15講 実際のA問題・B問題を使って、 実戦演習 WAの確認方法 デバッグ 提出前チェック を行います。 41

読み進め方 基本的には、 第1講から順番に 進めてください。 各講は、前の講で学んだ内容を土台にしています。 42

各講の構成 各講は、おおむね次の流れです。 1. 解説 2. コード例 3. 章末まとめ 4. 練習問題 5. 解答 コード例は、そのまま実行できる形で提示します。 43

コードには名前をつける 本書では、コード例にファイル名をつけます。 たとえば、 hello.py for.py input.py のようにします。 どのプログラムを実行しているのか、迷わないようにするためです。 44

練習問題は必ず自分で解く 読むだけでは、なかなか身につきません。 必ず、 自分でコードを書く ようにしてください。 解答を見る前に、まずは一度自力で挑戦しましょう。 45

0-6 ジャッジ結果を知る AtCoderでは、提出後に自動採点されます。 よく見る結果は次の5つです。 AC WA TLE RE CE 46

AC Accepted 正解 すべてのテストケースを通過しています。 制限時間内に、正しい答えを出せています。 47

WA Wrong Answer 不正解 出力結果が正解と一致していません。 原因は、解法ミスだけとは限りません。 48

WAのよくある原因 解き方そのものが間違っている 特定ケースだけずれる N = 1 で壊れる 出力形式が違う Yes と YES を間違える 余計な文字を出力している 出力形式も厳密に確認します。 49

TLE Time Limit Exceeded 実行時間制限超過 処理が時間内に終わっていません。 答えの考え方や処理方法を見直す必要があります。 50

RE Runtime Error 実行時エラー プログラムが途中で停止しました。 Pythonでは、いくつか典型的なエラーがあります。 51

よくあるRE IndexError ZeroDivisionError ValueError たとえば、 A[N] のようにリストの範囲外へアクセスすると、 IndexError になります。 52

CE Compilation Error Pythonでは主に、 インデントのずれ 括弧の閉じ忘れ 文法ミス などが原因です。 提出前に一度実行するだけでも、多くを防げます。 53

WAやREは学習材料 最初は、 WAやREが続いて当然 です。 WAは、 見落としているケースがありますよ というフィードバックだと考えてください。 54

TLEもヒントになる TLEは、 もっと効率のよい書き方がありますよ というサインです。 エラーや不正解も、すべて学習材料になります。 55

0-7 提出環境とテンプレート AtCoderでは、提出するときに言語を選びます。 Pythonでは主に、 CPython PyPy3 が使われます。 56

CPython 公式のPython実装 普段のPython環境に近い動きをします。 学習目的でも、そのまま使えます。 57

PyPy3 PyPy3は、Pythonコードを高速に実行できることがあります。 特に単純なループ処理で有利になる場合があります。 本書では、基本的にPyPy3を使う方針にします。 58

コードテストを使う AtCoderには、 コードテスト があります。 ブラウザ上でコードを実行できます。 手元に開発環境を作らなくても練習できます。 59

提出前の習慣 提出する前に、 1. 入力例を入れる 2. 実行する 3. 出力例と一致するか確認する 4. 問題なければ提出する この習慣だけで、無駄なWAはかなり減ります。 60

最初のプログラム ファイル名： double.py 標準入力から整数を1つ受け取り、 2倍して出力します。 # double.py # Read a single integer from standard input N = int(input()) # Calculate the answer answer = N * 2 # Print the answer to standard output print(answer) 61

入力例 入力： 5 出力： 10 たったこれだけです。 62

AtCoderの基本形 ほとんどの問題は、 入力 → 計算 → 出力 という形です。 難しい問題でも、この骨格は変わりません。 63

難しくなるのは「計算」の部分 最初と最後は、ほぼ同じです。 入力を受け取る 答えを出力する 難しくなるのは、その間の 「計算する」部分 です。 64

コメントを英語で書く理由 本書のコード例では、 コメントを英語で書きます。 学習段階では、コードの意図を言葉にすることが理解につながります。 65

英語に慣れておく プログラミングでは、 コード ドキュメント ライブラリ名 エラーメッセージ の多くが英語です。 短いコメントを書く習慣だけでも、抵抗感は少しずつ減っていきます。 66

0-8 挫折しないためのマインドセット 最後に、大切な心構えを3つ紹介します。 1. 20分考えてわからなければ解説を見る 2. 意地悪な入力を自分で考える 3. 人と比べず、昨日の自分と比べる 67

① 20分考えてわからなければ解説を見る 一つの問題に何日も悩み続ける必要はありません。 初学者の段階では、 知らない書き方を自力で発明するのは難しい からです。 68

解説を見ることは悪くない 次の流れがおすすめです。 1. 問題を読む 2. 小さな例を書く 3. 20分ほど考える 4. 手が止まったら解説を見る 5. 解説を閉じる 6. 最初から自分で書き直す 7. ACを取る 69

成長するのは「書き直したとき」 解説を読んで、 なるほど で終わってはいけません。 理解したあと、 自分の手で最初から書き直す ことが重要です。 70

② 意地悪な入力を自分で考える 提出前に、自分のコードを疑ってください。 たとえば、 N = 1 答えが0 答えがマイナス すべて同じ値 最小値 最大値 などを試します。 71

出力形式も確認する 特にAtCoderでは、 問題文と一字一句同じ形式で出力する ことが大切です。 Yes YES yes は別物です。 72

インデックスにも注意 Pythonのリストは、 0始まり です。 人間が数える「1番目」と、 Pythonの A[0] を混同しないようにしましょう。 73

③ 人と比べない AtCoderには順位表があります。 SNSを見ると、中高生が高速で問題を解いていることもあります。 しかし、比べる必要はありません。 74

比べる相手は昨日の自分 見るべきなのは、 先週30分かかった問題が10分で解けた 昨日書けなかったコードが今日は書けた TLEだったコードがACになった といった変化です。 75

小さな成長を積み重ねる 競技プログラミングは、 正しい練習を積めば少しずつ上達する ゲームです。 一歩ずつ積み重ねれば、 やがて茶色に届きます。 76

第0講まとめ この講で伝えたかったことは、次の5つです。 1. AtCoderはPython練習に向いている 2. 最初の目標はA・B問題 3. Pythonの基礎を迷わず書ける力が重要 4. WAやREも学習材料 5. コードには hello.py のように名前をつける 6. 解説を読んだら自分で書き直す 77

次回予告 次はいよいよ、 第1講 入出力 です。 すべての問題の入り口である、 「入力を受け取る」 ところから徹底的に練習します。 78