Upgrade to Pro — share decks privately, control downloads, hide ads and more …

競技プログラミングことはじめ

E869120
November 22, 2022

 競技プログラミングことはじめ

第1章 競技プログラミングとは?(p.7~)
第2章 AtCoderの始め方(p.43~)
第3章 競プロで必要な「アルゴリズムと思考力」(p.86~)
スライドのまとめ(p.154~)

E869120

November 22, 2022
Tweet

More Decks by E869120

Other Decks in Programming

Transcript

  1. 162 自己紹介 2 米田 優峻 (よねだ まさたか) • 2002年生まれ •

    2021年東京大学入学 主な実績 • 国際情報オリンピック ‘18, ‘19, ‘20 金メダル • 著書『アルゴリズム×数学』 • 著書『競技プログラミングの鉄則』
  2. 162 目次 6 第1章 競技プログラミングとは 競技プログラミングとは/AtCoderについて/参加のメリット 第2章 AtCoder の始め方 AtCoder

    の登録方法/AtCoder で問題を解いてみよう 第3章 競プロで必要な “アルゴリズムと思考力” 競プロで必要なスキル/アルゴリズムの知識/数学的思考力 ・・・・・・・・・・・・ 7 ・・・・・・・・・・・・・・ 43 ・・・・ 86
  3. 1 162 -1 競技プログラミングとは 9 基本的には、このような流れで競技が行われる 参加者にいくつかの 問題が与えられる 問題 A

    問題 C 問題 B 問題を解く プログラムを実装 試験時間内に 多く得点した方が上位 2 1 3
  4. 1 162 -1 競技プログラミングとは 10 基本的には、このような流れで競技が行われる 参加者にいくつかの 問題が与えられる 問題 A

    問題 C 問題 B 問題を解く プログラムを実装 試験時間内に 多く得点した方が上位 2 1 3
  5. 1 162 -1 競技プログラミングとは 11 基本的には、このような流れで競技が行われる 参加者にいくつかの 問題が与えられる 問題 A

    問題 C 問題 B 試験時間内に 多く得点した方が上位 2 1 3 問題を解く プログラムを実装
  6. 1 162 -1 競プロの問題 13 ※ここで問題を解く必要はありません。どんな問題が出されるかのイメージをつかんだら、次のページに進んでかまいません。 整数 𝑵, 𝑲 が与えられます。

    𝟏 以上 𝑵 以下の 3 つの整数を重複 なしで選び、合計を 𝑲 にする方法 は何通りですか? 答えを出力するプログラムを作成 してください。 ※ 𝑵, 𝑲 は 100 以下
  7. 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 以下
  8. 1 162 -1 GCJ 年に一度の世界大会 ICPC 大学生向けのチーム戦 情報オリンピック 中高生向けの大会 コンテストの種類

    19 AtCoder 日本最大手のコンテスト 次節では最大規模の AtCoder について紹介します 毎週開催されるので 初心者にもおすすめできる!
  9. 1 162 -2 AtCoder とは 22 100 分で 8 問を解き、合計得点を競う

    ※コンテストの約 3 分の 2 を占める AtCoder Beginner Contest の場合
  10. 1 162 -2 AtCoder の特徴 24 1 2 3 4

    参加費 場所 開催頻度 問題文 AtCoder は無料 運動系の大会は有料のものも多い が、AtCoder は基本的に無料で 参加できる※ ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く
  11. 1 162 -2 AtCoder の特徴 25 1 2 3 4

    参加費 場所 開催頻度 問題文 オンライン開催 自分の PC を持っていれば、ネッ ト上でどこでも参加できる ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く
  12. 1 162 -2 AtCoder の特徴 26 1 2 3 4

    参加費 場所 開催頻度 問題文 ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く 毎週開催される 情報オリンピックなどと比べて開 催頻度が高いので、定期的に実力 を確認できる
  13. 1 162 -2 AtCoder の特徴 27 1 2 3 4

    参加費 場所 開催頻度 問題文 ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く 日本語の問題文がある 海外のコンテストとは異なり、問 題文が日本語で提供される。英語 が読めない人でも安心
  14. 1 162 -2 AtCoder の特徴 28 1 2 3 4

    参加費 場所 開催頻度 問題文 ※3 カ月に一度開催される「アルゴリズム実技検定」を受験する場合を除く 日本語の問題文がある 海外のコンテストとは異なり、問 題文が日本語で提供される。英語 が読めない人でも安心 AtCoder は初心者でも 参加しやすい!
  15. 1 162 -3 AtCoder のレーティング 32 また、レーティングに応じて色が付けられる たとえば、レーティングが 2800 以上であ

    れば赤色になる オレンジ 黄色 青色 水色 緑色 茶色 灰色 赤 400 800 1200 1600 2000 2400 2800
  16. 1 162 -3 AtCoder のレーティング 33 初心者は、まず茶色を目指しましょう! オレンジ 黄色 青色

    水色 緑色 茶色 灰色 赤 400 800 1200 1600 2000 2400 2800 注意 茶色は下から 2 番目の色ですが、上位 40% なのでかなりすごいです。エンジニアで茶色 になれない人も多いです。
  17. 1 162 -4 競プロのメリット 36 1 2 3 プログラミング力 思考力

    楽しさ 競プロの問題を解くには、当然プ ログラムを書く必要がある コンテストに参加していくと プログラムを書く能力が身に つく! →
  18. 1 162 -4 競プロのメリット 37 詳しくは 3 章で説明するが、競 プロの問題の中には思考力が要求 されるものもある

    問題を解いていくうちに数学 的思考力が身につく! → 1 2 3 プログラミング力 思考力 楽しさ
  19. 1 162 -4 競プロのメリット 38 1 2 3 プログラミング力 思考力

    楽しさ さらに、プログラマにとって必須 のアルゴリズムの知識も身につけ ることができる!
  20. 1 162 -4 競プロのメリット 39 AtCoder では同時に 5000 人以 上の参加者と対戦できる(リアル

    タイムの順位表もある) ゲーム感覚で楽しんで参加で きる! → 1 2 3 プログラミング力 思考力 楽しさ
  21. 2 162 -0 第 2 章の内容 44 第 2 章では、いよいよ

    AtCoder で競プロを 始める方法を解説します AtCoder で 問題を解くには? AtCoder に 登録するには?
  22. 2 162 -2 AtCoder で問題を解こう 55 Step 3 問題一覧が出てくるので、とりあえず 一番上の「PracticeA

    - Welcome To AtCoder」を開きます ※ 1 問目の「Welcome to AtCoder」はチュートリアル用に作られた問題です
  23. 2 162 -2 AtCoder で問題を解こう 58 本文 制約 AtCoder の問題文は、本文・制約・入出力形式・例の

    4 つの部分に分かれています 入出力形式 例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 6 test
  24. 2 162 -2 AtCoder で問題を解こう 59 本文では、どのような問題を解けばよいのかが 説明されています 制約 入出力形式

    例 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 本文 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 6 test
  25. 2 162 -2 AtCoder で問題を解こう 60 制約では、入力としてどのようなデータが 与えられるかが記されています 本文 入出力形式

    例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 制約 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 6 test つまり、𝒂 = 𝟏𝟎𝟏 のようなデータが与 えられることはないと思ってよい! ※2 章では制約をあまり気にしなくても良 いですが、3 章では重要になります。
  26. 2 162 -2 AtCoder で問題を解こう 61 入出力形式では、どういうフォーマットで入力・出力を 行えば良いかが記されています 本文 入出力形式

    例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 制約 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 ※フォーマットに従わなければ不正解となる場合がありますので、注意してください たとえばこの問題では、入力として • 1 行目に 𝒂 が与えられる • 2 行目に 𝒃, 𝒄 が空白区切りで与えられる • 3 行目に 𝒔 が与えられる 6 test
  27. 2 162 -2 AtCoder で問題を解こう 62 本文 制約 例では、「どういう入力であればどういう出力が正しいか」の 具体例が示されています

    入出力形式 例 整数 𝒂, 𝒃, 𝒄 と文字列 𝒔 が与えられる。 𝒂 + 𝒃 + 𝒄 の計算結果 と文字列 𝒔 を並べて 出力せよ。 • 𝒂, 𝒃, 𝒄 は 𝟏 以上 𝟏𝟎𝟎 以下の整数 • 𝒔 は 𝟏𝟎𝟎 文字以下 入力: 𝒂 𝒃 𝒄 𝒔 出力: 𝒂 + 𝒃 + 𝒄 と 𝒔 を空白区切り で出力 入力: 1 2 3 test 出力: 6 test
  28. 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
  29. 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)
  30. 2 162 -3 チュートリアル問題の次は? 73 Step 2 AtCoder Beginners Selections

    を解いて 競プロの問題のイメージをつかむ ※URL:https://atcoder.jp/contests/abs
  31. 2 162 -3 コンテストについて 76 AtCoder には 4 種類のコンテストがありますが… 初心者には

    ABC がオススメ! 注意1 AtCoder Beginner Contest (ABC) AtCoder Regular Contest (ARC) AtCoder Grand Contest (AGC) AtCoder Heuristic Contest (AHC)
  32. 2 162 -3 コンテストについて 77 ただし、ABC は Beginner Contest という名前ですが

    それほど簡単ではないことに注意! 注意2 初心者は 8 問中 2 問解ければ十分です※ ※筆者(2022/11/21 時点で国内ランキング18位)でも全問正解できないことの方が多いです。 ※ ARC や AGC はさらに難しいです。 簡単だと思って参加したら解けなくて挫折する人が多いです Beginner Contest という名前が問題だと思うのですが…
  33. 2 162 -3 コードテストについて 84 Step 4 数秒待つと、画面下部に実行結果 が出力されます ※たしかに正しい値

    123+456=579 が 出力されているのがわかります コードテストの使い方は わかりましたか?
  34. 3 162 -1 ここまでの振り返り 87 第 1 章・第 2 章では、

    競技プログラミングとは何か? AtCoder とは何か? AtCoder で問題を解く方法は? などを解説しました
  35. 3 162 -2 迷路の問題:全探索 104 >380億通り 実は、コンピュータの演算速度は 毎秒 1 億回程度

    つまり単純に割り算しても 5 分以上かかることに! ※実行環境やプログラミング言語によって変わりますが、AtCoder 上で Python を動かした場合、毎秒 1 億回程度になります
  36. 3 162 -2 迷路の問題:全探索 105 >380億通り コンピュータの演算速度は 毎秒 1 億回程度

    つまり単純に割り算しても 5 分以上かかることに! ※実行環境やプログラミング言語によって変わりますが、AtCoder 上で Python を動かした場合、毎秒 1 億回程度になります そして競プロの問題では、数秒以内で実行が終わらなければ 不正解となってしまう!
  37. 3 162 -2 迷路の問題:解法の工夫 108 0 1 0 の隣に 1

    を書く ※書かれた数は、スタートからの最短手数を意味します。
  38. 3 162 -2 迷路の問題:解法の工夫 109 0 1 2 1 の隣に

    2 を書く ※書かれた数は、スタートからの最短手数を意味します。
  39. 3 162 -2 迷路の問題:解法の工夫 110 0 1 2 3 2

    の隣に 3 を書く ※書かれた数は、スタートからの最短手数を意味します。
  40. 3 162 -2 迷路の問題:解法の工夫 111 0 4 1 2 3

    4 3 の隣に 4 を書く ※書かれた数は、スタートからの最短手数を意味します。
  41. 3 162 -2 迷路の問題:解法の工夫 112 0 4 5 1 2

    3 4 5 4 の隣に 5 を書く ※書かれた数は、スタートからの最短手数を意味します。
  42. 3 162 -2 迷路の問題:解法の工夫 113 0 4 5 6 1

    2 3 4 6 5 5 の隣に 6 を書く ※書かれた数は、スタートからの最短手数を意味します。
  43. 3 162 -2 迷路の問題:解法の工夫 114 0 4 5 6 1

    2 3 7 4 7 6 5 6 の隣に 7 を書く ※書かれた数は、スタートからの最短手数を意味します。
  44. 3 162 -2 迷路の問題:解法の工夫 115 0 4 5 6 1

    2 3 7 4 8 7 6 5 8 7 の隣に 8 を書く ※書かれた数は、スタートからの最短手数を意味します。
  45. 3 162 -2 迷路の問題:解法の工夫 116 0 4 5 6 1

    2 3 7 4 8 9 7 6 5 9 8 9 8 の隣に 9 を書く ※書かれた数は、スタートからの最短手数を意味します。
  46. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  47. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  48. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  49. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  50. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  51. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  52. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  53. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  54. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  55. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  56. 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 を書く ※書かれた数は、スタートからの最短手数を意味します。
  57. 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 手!
  58. 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 秒!
  59. 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→… と数字が小さくなる方向に動くと、具体 的な最短経路がわかる ※書かれた数は、スタートからの最短手数を意味します。
  60. 3 162 -2 解法を思いつくために 132 以下のような「典型的なアルゴリズム」を 知っているだけで結構変わる! 累積和 二分探索 動的計画法

    深さ優先探索 幅優先探索 ダイクストラ法 素数判定法 ユークリッドの互除法 繰り返し二乗法
  61. 3 162 -2 解法を思いつくために 133 たとえば迷路の場合は「幅優先探索」を 知っていれば思いつける 累積和 二分探索 動的計画法

    深さ優先探索 幅優先探索 ダイクストラ法 素数判定法 ユークリッドの互除法 繰り返し二乗法
  62. 3 162 -2 • 問題を解く手順(解法)のことを、プログラミングの文脈では アルゴリズムという • 基本的には、計算の速く終わる方が「良いアルゴリズム」 • たとえば迷路の問題の場合、経路を全部調べるアルゴリズムより、隣に数を書

    いていくアルゴリズムの方が、良いといえる 補足:アルゴリズムとは? 135 ※なお、特に競プロ以外の文脈では、良いアルゴリズムの指標として、計算時間だけでなくメモリ使用量などが使われることもあります
  63. 3 162 -3 ピッタリ移動する問題 138 • 5 個のマスが一列に並んだマス目がある • 隣り合うマスへの移動をちょうど

    𝑵 回行うことで、左端から右端に移動する ことはできるか? 5 個 ゴール スタート ※制約:𝑵 は 1 以上 100 以下 (入力は 𝑵 のみ)
  64. 3 162 -3 ピッタリ移動する問題 139 例:𝑵 = 𝟑 の場合 1

    2 3 No… そもそもたどり着かない…
  65. 3 162 -3 ピッタリ移動する問題 140 1 2 3 4 5

    6 よし、行けた! 例:𝑵 = 𝟔 の場合 Yes!
  66. 3 162 -3 ピッタリ移動する問題 141 1 2 3 5 4

    1 回余ってしまう… 例:𝑵 = 𝟓 の場合 No…
  67. 3 162 -3 ピッタリ移動する問題:全探索 144 まず、あり得る経路を全部調べれば、答えがわかる (例:𝑵 = 𝟓 の場合、上の

    9 通りが全部ダメなので答えは No) 約 5,600億 通り しかし、𝑵 = 𝟓𝟎 になると コンピュータでも無理!
  68. 3 162 -3 ピッタリ移動する問題:全探索 145 まず、あり得る経路を全部調べれば、答えがわかる (例:𝑵 = 𝟓 の場合、上の

    9 通りが全部ダメなので答えは No) 約 5,600億 通り しかし、𝑵 = 𝟓𝟎 になると コンピュータでも無理! そこで、「偶奇で場合分けする」という 数学的思考をすると簡単に解ける!
  69. 3 162 -3 工夫した解法 146 まず、𝑵 が偶数の場合 𝑵 = 𝟐

    の場合は、手数的に無理だが 𝑵 ≥ 𝟒 の場合は、ゴールまで一直線に進んだ後、ゴール付近を 往復すれば良いので Yes
  70. 3 162 -3 工夫した解法 147 まず、𝑵 が偶数の場合 𝑵 = 𝟐

    の場合は、手数的に無理だが 𝑵 ≥ 𝟒 の場合は、ゴールまで一直線に進んだ後、ゴール付近を 往復すれば良いので Yes 𝑵 = 𝟒 のとき 𝑵 = 𝟔 のとき 𝑵 = 𝟖 のとき
  71. 3 162 -3 工夫した解法 149 一方、𝑵 が奇数の場合 左から 1・3・5 マス目を青、2・4

    マス目を白で塗ると… 青 白 青 白 青 白 青 白 青 白 白 青 青 白 白 白 青 青 必ず「青→白→青→白→…」 という順番で移動 𝑵 が奇数のときは白色で終わる
  72. 3 162 -3 工夫した解法 150 一方、𝑵 が奇数の場合 左から 1・3・5 マス目を青、2・4

    マス目を白で塗ると… 白 白 白 必ず「青→白→青→白→…」 という順番で移動 𝑵 が奇数のときは白色で終わる たしかに 𝑵 = 𝟓 のときは 全部白色で終わっている
  73. 3 162 -3 工夫した解法 151 一方、𝑵 が奇数の場合 左から 1・3・5 マス目を青、2・4

    マス目を白で塗ると… 白 白 白 必ず「青→白→青→白→…」 という順番で移動 𝑵 が奇数のときは白色で終わる たしかに 𝑵 = 𝟓 のときは 全部白色で終わっている ところが、ゴールのマスは青色である 𝑵 が奇数のときは、答えは No
  74. 4 162 本の紹介 160 競技プログラミングの鉄則 2022年9月発売/筆者が執筆 フルカラーの図が豊富で分かりやすい! AtCoder 自動採点システム付きの演習問題! C++/Python/Java

    に対応! 特徴 1 2 3 興味のある方はぜひお読みください! ※なお、本の紙面には C++ しか載っていませんが、サポートページには Python/Java のプログラムがすべて載っています 発売2カ月で4刷
  75. 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