はてなブックマーク

こんにちは、大学 1 年になったばかりの E869120 です。 私は 5 年前に趣味で競技プログラミングを始め、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 5 月 5 日現在、AtCoder では赤（レッドコーダー）です。 今回は、アルゴリズムや競技プログラミングの問題を速く解くために必要な、効率的なデバッグの方法について記したいと思います。是非お読みください。 1. はじめに 皆さんがプログラミングの問題を解いていく際に、次のような場面に遭遇したことはありますでしょうか。おそらく、読者の大半が「はい」と答えると思います。 ソースコードに謎のミスを埋め込んでしまったせいで D 問題が解けない… ああ、プログラムを 1 文字変えただけで WA（不正解）が AC（正解）に変わった、悲しい… このように、プログラムにバグ（プログラム実装上のミス）を埋め込

0. はじめに こんにちは、大学 1 年生になったばかりの E869120 です。本記事は、 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 からの続きです！！！ ※前編・中編を読んでいなくても理解できる、独立したトピックになっているので、ご安心ください。 後編から読む方へ 21 世紀も中盤に入り、情報化社会が急激に進行していく中、プログラミング的思考やアルゴリズムの知識、そしてアルゴリズムを用いた問題解決力が日々重要になっています。 しかし、アルゴリズム構築能力・競プロの実力は、単純にプログラミングの知識を学ぶだけでは身につきません。近年、数学的なスキルが重要になりつつあります。実際、私はこれまでの経験で「数学の壁で躓いた競プロ参加者」をたくさん見てきました。そこで本記事では、 AtCoder のコン

競プロにおける「上達の壁」 そこで私は、主に以下の 3 点が競技プログラミングにおける上達の壁になっているのではないかと考えています。 基礎的なコーディングの知識。for 文・条件分岐・配列などを使った基本的なプログラムが書けるかどうか。（レーティング 1～99 程度） 競プロで戦うために必要な、最低限のアルゴリズムや数学の知識。例えば二分探索・動的計画法・グラフ理論・逆元といったものが挙げられる。（レーティング 100～1199 程度） アルゴリズムや数学的知識 [2. で扱ったもの] をどうやって実際の問題に応用するか、考察面・実装面両方含めた典型テクニック。（レーティング 200～1999 程度） 今はどの壁が問題か？ 現在、1. と 2. についてはかなり教材が整備されており、例えば 1. のプログラミングの基本を学ぶにあたっては、 C++入門 AtCoder Programmin

4. アルゴリズムと密接に関わる数学＜中級編＞ 2 章では問題文を読むために必要なテクニックを 12 個のポイントに絞ってまとめました。しかし、競プロに出題されるようなアルゴリズムだけを考えても、数学と結びつく場面はまだまだたくさんあります。例えば、 3-2. 節では、二分探索の計算量 $O(\log N)$ と対数関数の関係 3-6. 節・3-7. 節では、幾何計算と三角関数・ベクトルの関係 3-11. 節では、経路の数の計算とフェルマーの小定理の関係 について紹介してきました。4 章ではさらに追加で 8 個のトピックを紹介し、アルゴリズムを数学的側面から捉えていきたいと思います。皆さんにアルゴリズムと数学が如何に密接に関わっているかを体感してもらうことが最大の目標です。 なお、3 章・4 章の構成は次のようになっています。 4-12. 最大値検索に学ぶ、微分法（レベル：3） まず、次の

こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】　←　本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、

2. 情報オリンピックとは まず、本記事で紹介する「情報オリンピック」が一体どのような大会であるか、知りたい方も多いと思います。本章ではそれについて、分かりやすく紹介していきます。 2-1. 一体「情報オリンピック」とは何か？ 情報オリンピックとは、以下のような大会です。 日本情報オリンピック (JOI) は、高等学校 2 年生までの競技プログラマー日本一を決める大会である。（日本情報オリンピック実施要項から引用） つまり、小中学生・高校生で誰が一番プログラミングスキルが高いか、競う大会です。もし日本一（正確には日本で 4 位以内）になったら、世界大会である「国際情報オリンピック (IOI)」に招待され、世界で一番を決める大会に出場することができます。 日本情報オリンピックは歴史が浅く、1994 年に始まったものです。しかしながら、2019 年の情報オリンピックには約 1300 人1が参加

1. 探索アルゴリズムとは 探索アルゴリズムとは、以下のような手法のことを指します。 探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。(Wikipediaより) もう少し具体的に書くと、「あり得るパターンを全部列挙する」という手法のことを全探索といい、これが探索アルゴリズムの基本です。また、4 章で後述する二分探索などを用いて探索回数を減らすアルゴリズムも探索アルゴリズムの仲間です。 分かりやすいように、一個例を説明しましょう。 「おねえさん問題」に学ぶ、探索アルゴリズム ところで、以下の問題をご存知でしょうか。 $N \times N$ の碁盤目状道路がある。左上座標を $(0, 0)$、右下座標を $(N, N)$ とするとき、左上の座標から右下の座標まで、同じ交差点を通らずに行くような方法は何通りあるか。 例えば

そのうち、最初の 12 個（表の 1 ～ 3 行目）をマスターする方法は、中級編 2-2-2. 節で解説がされていますので、こちらをご覧ください。本節では、残りの 11 個を理解できる記事たちを紹介したいと思います。 座標圧縮 まとまった解説記事が見つからないので、こちらで簡潔に解説しておきます。 座標圧縮とは、とても大きい座標があって現実的に扱えないサイズである場合に、圧縮して計算量を抑えるというテクニックです。以下の画像のように、相対的な位置関係が崩れないように圧縮します。（一次元の場合でも、二次元の場合でも通用します。） 実装などを含めた詳しい部分は、以下の記事に書かれています。 座標圧縮について勉強した (java)| バイトの競プロメモ 座標圧縮| 個人的な競プロメモ 半分全列挙 $N$ 通りの全列挙を $O(\sqrt{N})$ 程度の計算回数で効率的に計算する手法です。以下の

※ ダイクストラ法・ワーシャルフロイド法は最短経路問題を解くアルゴリズムです。 ※ クラスカル法は最小全域木問題を解くアルゴリズムです。 それらのアルゴリズムが学習できる記事たちなどを紹介します。 全探索 全探索には、「全列挙」「ビット全探索」「順列全探索」「再帰関数を用いた全探索」など多くの種類に分かれます。しかし、基本的に以下の記事を読めば全部理解できます。 全列挙　たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 2 章 その他の全探索　たのしい探索アルゴリズムの世界【前編：全探索、bit全探索から半分全列挙まで】 の 3 章 二分探索 アルゴリズムの代表例ともいわれる二分探索は、以下の 2 記事で解説されています。 二分探索とは：アルゴリズムを勉強するなら二分探索から始めよう！ 『なっとく！アルゴリズム』より 競プロで使える二分探索：二分探索アルゴ

このように、競技プログラミングはコーディングの正確性が問われるコンテストです。 どんな問題が出されるか（２） 競プロは正確性だけではありません。例えば、以下の問題を考えてみてください。 $N$ 枚のカードが一列に並べられています。 左から $i$ 番目のカードには、整数 $A_i$ が書かれています。 あなたは $N$ 枚のカードの中から $2$ 枚同時に選び、取ることができます。取った $2$ 枚に書かれた整数の合計がちょうど $101$ となるような、カードの選び方の通り数を求めてください。 テストデータの制約：$1 \leq N \leq 10^{6}, 1 \leq A_i \leq 10^{9}$ 一番最初に考えられる解法は、以下のように「何枚目と何枚目を選ぶか全探索する」という方法だと思います。つまり、$1 \leq i < j \leq N$ を満たすすべての $(i, j)

2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路

ですが、以下のように思った人も多いと思います。 今回の 25 個の標準ライブラリはわかったけど、どういう問題やどういうアルゴリズムの実装で活用できるのか？？？ そこで本章では、どのような問題を解くときに C++ の標準ライブラリが使えるのか、11 個の例を紹介します。 5-1. バブルソートの実装 (swap) バブルソートは、アルゴリズム解説本や、大学の授業などでも教えられることが多いようです。以下のような発想に基づいたアルゴリズムです。 「配列の中から、大きさが逆転している部分があれば swap する」という操作を繰り返す。 最終的に、大きさが逆転している部分が無くなれば操作を終了する。 この「バブルソート」は、swap 関数 を使うことで実装しやすくなります。実装例は以下のようになります。 ソースコード #include <iostream> using namespace std;

(AtCoder Beginner Contest 152 で提出されたソースコードの分類) それほど C++ が、競プロやアルゴリズムの学習に人気であるのには、以下のような理由があるのです。 計算速度が 1 秒あたり $10^{8} ～ 10^{9}$ 回程度と、他のプログラミング言語に比べ高速だから。 基礎的文法の習得がそれほど難しくないから。 しかし、C++ の利点はこれだけではありません。元々用意されている標準ライブラリがあるのです。一方、標準ライブラリは C++ を学ぶ大きな障壁となるものの一つです。C++ を学ぶ上で標準ライブラリが上手く使えず挫折したという人も多いと思います。そこで本記事では、 競技プログラミングやアルゴリズムの実装に使える 25 個の C++ 標準ライブラリと、それらの各種アルゴリズム実装への応用例 を解説したいと思います！！！！！ 本記事を読んだら何ができ

1. はじめに こんにちは、高校 2 年生のE869120です。 私は、プログラミングの中でも競技プログラミング (競プロ) が好きで、AtCoder・CodeForces・国際情報オリンピック・パソコン甲子園などの各種大会・コンテストに出場しています。 さて、競プロをやっている人の中では、 作問をしたいけど、初心者なので作問が本当にできるのか不安だ。。。 といった考えや、 問題は思いついたけど、作問の方法やテクニックが分からないから作問できず困っています。。。 といった考えが近年多く見受けられます。1 それについて、「誰でも気軽に競プロ作問ができるようにしたい！」と思い、私は本記事を書くことにしました。 今回は、競技プログラミングの世界で、作問と出題準備をする方法について解説します。初心者でもわかるように解説しますので、是非お読みください！ 対象とする読者層 この記事は、競技プログラミン