目次
はじめに
今日からAtCoderド初心者日記と題して、私が奮闘する姿をQiitaに書いていこうと思う。
初心者目線では競技プログラミングがどう見えているのか、そんな事を上級者の方には温かく見守っていただき、初心者の方には共感してもらえれば幸いだ。
ド初心者とは言ってもどんなレベルなの？
AtCoder歴は約1か月。
レベル感としては、AtCoderの色はもちろん灰色で、A・B問題を解くのが精いっぱいといった具合だ。
使用言語はC++で、APG4bの第一章を終えた程度である。
C++の文法は全くわからない状態からのスタートではあったが以前プログラミングを少しかじっていたこともあり、短期間で基礎的な文法を網羅することができた。
AtCoderを始めたきっかけ
私がAtCoderを始めたきっかけとしてはChatGPTとの会話だ。
どうやら競技プログラミングというものがあるらしいと分かった。
それから会話を続けていくうちに日本国内で一番メジャーな競技プログラミングはAtCoderであるとか、色(レート)によっては就職に有利に働くことがあるだとか自分の知らない世界がそこには広がっていた。
しかし、最も大きな理由は単純に楽しそうだと感じたことである。
ABC(AtCoder Beginner Contest) の開催時間である土曜21時は、ゲーマーにとってのゴールデンタイムとも言える時間帯だ。
この時間を競技プログラミングに費やすことには多少の抵抗もあったが、逆説的に参加者が皆熱中していることを考えれば、自分も挑戦してみる価値があると判断した。
初めての参加
初めて1週間目の頃ABC438をunratedでの参加、結果A問題すら解けずに見事に惨敗となった。
今問題を見てみると大したことはないが当時の自分にとっては難しかったのだろう
この問題はA問題ではあるが少しだけ考える必要があるため少し面倒である。
この問題の解説をしても仕方がないので次に進もうと思う。
失敗を経てから次の行動
ABCでの惨敗からいろいろ調べて、AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～に取り組むことにした。
正直、まだ7問目までしか解けていなく「これのおかげでA,B問題を難なく解けるようになった！」といった感触はなかったが、ある程度はできるようになってきた。
また、解説が非常に丁寧で初心者にもわかりやすく非常に優れた教材である。
Pythonなどのほかの言語で解いてる記事もあり、C++以外の言語を使用している方でも安心して取り組める。
話は変わるが、私は本が大好きでよく小説を読んでいる。
本好きの性として本屋があれば引き込まれるように入ってしまうというものがある。
いつも行っている本屋に何気なく入ってみたところ、競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~という本に出合った。
いわゆる鉄則本というやつである。
あちこちで絶賛されていて、amazonの評価がかなり高かったこともあり奮発して購入することにした。
鉄則本を解いてみる
鉄則本を買ったこともありここで競技プログラミングのモチベーションがピークに達していた。
第1章
第一章は計算量の説明や全探索、2進数が扱われていた。
いずれも、アルゴリズムの基本であるためあまり苦戦することはなかった。
しいて言えばA05 Three Cardsの計算量オーダーをO(N²)で実行するのに少し苦戦した。
この問題を何も考えずに3重ループの全探索でやろうとすると次のようになる
int count = 0;
for (int a = 1; a <= N; a++) {
for (int b = 1; b <= N; b++) {
for (int c = 1; c <= N; c++) {
if (a + b + c == K) count++;
}
}
}
これを計算しようとすると計算量オーダーO(N³)となり、N = 3000なら27億回もかかってしまい、これでは当然TLE(時間制限超過)となってしまう。
これをO(N²)にするためには a + b の値によって c の値が一つに決まることを利用する必要がある。
実装は次の通りである。
for (int a = 1; a <= N; a++) {
for (int b = 1; b <= N; b++) {
int c = K - a - b;
if (1 <= c && c <= N) count++;
}
}
初心者の私はちょっとした工夫をするだけで計算量がぐっと減ることにすごく感心した。
アルゴリズムをこれから勉強するにあたってこのような計算量を減らす工夫がいくつも待ち構えていることを考えるととても胸が高鳴る。
さて、続いて第二章に移ろう。
第2章
第2章、ここから少し苦戦するようになってきた。
第2章では累積和を学習した。累積和を一言で言い表すなら、合計の配列を用いてある区間の和を一瞬で求めるアルゴリズムである。
意気揚々と学習を進めていき、1次元の累積和はお手の物。
しかし、問題は2次元の累積和である。
まず、2次元データの入力を受け取る方法がわからない。2次元配列ってどうやって書くんだ？など全く手につかなかった。調べてみると次のように書くらしい
vector<vector<int>> a(h, vector<int>(w,0));
//h(行),w(列)
うーん...長い！こんなもの覚えてられるかとなり、配列はvectorを使っていた私も普通の書き方に乗り換えることとなった。
int a[1509][1509];
//h,w≦1500
かなりシンプルになったのではないだろうか。
ここではh,wが1500以下という制約があるため、1509と少し余裕を持たせた大きさにしている。
次に0インデックス、1インデックスの話をしようと思う。
累積和において、インデックス設計は計算のしやすさを大きく左右するからだ。
C++では配列は0から始まる。(ほとんどのプログラミング言語はそうだと思うが)
私はいままでfor文を0インデックスで書いていた。理由はかっこいいからだ。
しかし、自分には0インデックスで累積和を扱うのは少し難しく感じられた。
自分が1次元の累積和を1インデックスでとる際次のように実装するだろう。
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
//元の配列：a
//累積和配列：s
これを0インデックスで実装してしまうとループの一番最初で
s[0] = s[-1] + a[1];
となって、存在しない配列にアクセスしてしまう。
この記事を書く上でいろいろ調べていくうちに理解したのだが
s[i] = s[i - 1] + a[i];
を漸化式のように見て
s[i+1] = s[i] + a[i];
とすれば0インデックスでも簡単に実装でき、配列sに入っている数字自体も人間が直観的に判断できる1インデックスとなる。
こういった気づきがあり、記事を書きアウトプットすることで理解を深めることが出来た。気づきの種はどこにあるか分からないからこそ、アウトプットを通じてそれを探すことが重要だ。
話を戻し、二次元配列における躓きポイントを挙げてみる。
次の画像は二次元配列を利用する問題の入力である。
これを見て自分の中で1つの違和感が湧いてきた。
「x,y座標が逆では？」
調べてみると
h(height) = 行（たて）
w(width) = 列（よこ)
とx,y座標とはまた違った概念であると分かった。
この辺は慣れるまでに少し時間がかかりそうだ。
まとめ
本記事ではAtCoderに挑戦し始めた初心者が、プログラミングの難しさに直面した体験を記録してきた。
アルゴリズムという面では理解に苦しむものはなかったものの、インデックス設計など基礎的な部分で躓くことが多かったのが印象的だ。
これからも、こういった学習の過程、成長していく様を発信していきながら自身の成長につなげていきたい。