【AtCoder】 灰色→茶色になるための4つの攻略法

※2019年11月くらいの情報です。

どうもザウルスです！🦖
AtCoderで色をつけたいと思ったことありませんか？

灰色はコンテストに参加すればなれるので、努力の証の色って感じがしなくてずっと灰色のままだとなかなかモチベーションを維持することが難しいですよね。

この記事では競技プログラミング初めての人がレートを上げることを第一に考え、茶色になるまでに行ってきたことを説明します。

私は2019年8月18日に初めてAtCoderに参加して同年11月9日に茶色になることができました。
茶色になるまでに参加したコンテストの回数は8回です。

茶色になるために私は以下のことに気を使っていました。

①文法を忘れてもすぐ参照できるようにする
②AB問題よりC問題を重視　紙とペンで頑張る
③コンテストにたくさん参加する
④ローカル環境を構築しタイムロスを減らす

この4つを行うことで、毎試合コンスタントにレートを上げ茶色になることに成功しました。
いずれも難しいことではなく、また勉強時間も長くかからないので忙しい方にもオススメできます。
１つのやり方だと思って参考にしていただけると嬉しいです＾＾

1. プログラミング言語の文法を最低限勉強し、すぐに参照できるようにする！

ここでのポイントは文法を"覚える"のではなく"参照できるようにする"というところです。

まず茶色になるために最低限勉強しておかないといけない文法は以下の4つです。

・入出力 (c++では cinとcout)
・if文
・for文
・配列

プログラミングを始めたての人はどれくらい文法を勉強すれば十分なんだろう・・・と悩むこともあると思います。

でも大丈夫です！この4つの構文が使えるようになるだけでB問題までは絶対解け、C問題にも太刀打ちできます。

ここまで勉強したらどんどんコンテストに参加しちゃいましょう！

次に"参照できるようにする"ということです。

プログラミングは少しでも書き方が異なるとエラーになってしまうため正しい構文で書くことはとても重要です。

しかしプログラミングの勉強を始めたばかりの人もそうでない人も、構文を完璧に覚えるのは大変です。

なので、よく使う構文はメモ帳やエディタにあらかじめ書いておいて、いつでも参照できるようにしましょう。

私がメモしているものを抜粋してみます。

//標準入力　スペースか改行で区切ってくれる
int a, b, c;
cin >> a >> b >> c;

//標準出力
cout << "a" << "b";               //こういう書き方もできる
cout << "a" << 100 << "b";        //こういう書き方もできる

//for文
for (int i = 0; i < N; i++) {
}

//配列
vector<int> vec;          //配列の宣言
vec = { 10, 20, 30 };    //配列への代入
vec.size()                //配列の要素数 上の場合3が帰ってくる
vec.at(i)                 //配列のi番目にアクセス
vector<vector<int>> vec(10, vector<int>(10));   //二次元配列の宣言

私はコンテスト中にcinやcoutで>>か<<どちらを使うのか迷ってしまったり、二次元配列の宣言の仕方をド忘れしたりしたことがあります。

そこで不安な気持ちになったり、書いたコードが合っているか調べるのは時間がもったいないです。

メモを残して参照できるようにしておくことでコピペによる時間短縮も見込め、何より自分が書いているコードは少なくとも文法によるミスは無いという安心感が持てます。

そのため集中して問題に取り組むことができ、良いパフォーマンスも発揮できるようになります。

ここまでできるようになることでまずはB問題まで確実に解けるようになることを目指しましょう。

2. AB早解きよりC問題を死ぬ気で取る！紙とペンを用意しよう

B問題が解けるようになった後の勉強法として、AB問題の過去問をたくさん解くというものがありますが、私はそれは最もよいやり方だとは思っていません。

理由は2つあります。

1つ目はレートの上がりやすさという面です。
AtCoderのコンテストでは順位が高い方が良いパフォーマンスが出てレートの伸びも良いです。従って5分でAB問題を解く人より、15分でAB問題を解きその後80分でC問題を解く人の方がレートが上がります。

2つ目は精神面です。
C問題を絶対解くぞ、というメンタルを持っておくことは大事だと思います。AB問題を早く解いてCは解けなかったらいいや、という心持ちだとせっかく100分もあるコンテストのうち初めの5分程度しかコミットすることができません。これは非常にもったいないです。


ではどうやってC問題を解くのか


私は紙とペンを使って問題の状況を頭でイメージして、それをアウトプットして可視化することで解ける可能性が上がるのではないかと考えています。
具体的には次の通りです。


0. 問題文を一通り最後まで読んで理解する (超大事!!)
1. サンプルケース付近の値を書いてみて法則性を探る
2. 簡単なケースをいくつか書いて法則を見つける
3. ギリギリのケースは場合分けを駆使する


実際の問題を使って解説していきます。
ABC140 C問題 Maximal Value

0. 問題文を一通り最後まで読んで理解する

C問題はこんな感じな問題が出ます。
先に結論から言ってしまうと、

問題文を読むコツは、分からないなって思っても "入力例 1" までとにかく読み進めることです。

C問題から問題文が少し複雑になります。AiやBiといった添字や数学チックな数式が登場し、この問題文だけを読んで状況を瞬時にイメージすることは困難です。でも頑張って入力例 1 まで読み進めましょう。

入力例 1 は比較的簡単なケースでかつ、具体的な数字でどうしてその出力になるのかを丁寧に解説してくれています。




1. サンプルケース付近の値を書いてみて法則性を探る

ここまで読んだらこの入力例 1 のサンプルケースを使って法則性を探っていきます。

今回の問題は数列Bが入力値を与えられていて、
Bi >= max(Ai, Ai+1)
これを満たす数列Aを考え、数列Aの総和を最大化することです。
数列の各要素に対して何が最大の値となるかを考える必要がありそうです。

入力例 1 の場合、答えとなる数列Aは (2, 2, 5) なのですが付近の値を紙に書いて、他にどのような値が考えられたのか、なぜ (2, 2, 5)が最大なのかを考えてみましょう。

上のように紙に書くとどうして数列Aが (2, 2, 5) になるのかその理由が見えてきます。

まずA1に関して、3以上の値を入れてしまうと、
B1 >= max(A1, A2)　➡️　2 >= max(3, A2)
このようになってしまいダメだということが分かります。よってA1は2が最大の値だということが分かります。A3についても同様に考えることでA3は5が最大だと分かります。

A2についてはもうちょっと頭をひねる必要があります。下の式をご覧ください。

B1 >= max(A1, A2)　　　 ・・・①
B2 >= max(A2, A3)　　　・・・②

A2に関しては、①と②の式よりB1の数字にもB2の数字にも影響を受けることになります。

B1に着目するとA2の最大値は2となります。B2に着目するとA2の最大値は5となります。どちらも満たす必要があるためA2の最大値は2となることが分かります。

以上より答えとなる数列Aの要素は (2, 2, 5) となります。

今の時点でなんとなく、数列Aの端の値は数列Bの端の値と同じになって、数列Aの端でない部分の値は 影響を受ける数列Bの2つの値の小さい方になるのかなぁという法則が頭の中に浮かぶと思います。

このように実際に紙に書いてみることで、問題の状況を目で見てイメージすることができます。さらに入力例に対してなぜその解答になるかという過程も順を追って理解することができます。




2. 簡単なケースをいくつか書いて法則を見つける

問題の状況がイメージできたら簡単なケースをいくつか書いてみます。
その際にポイントは2つあります。

1つ目は入力例は決め打ちでいいのですが、答えは先程なんとなく考えた法則通りになるのかならないのかに着目するということ。
2つ目は入力例を先程の法則に当てはまらないかもしれないな、と思うものにするということです。

2つ目に関して補足をすると、先程の入力例だと Bが(2, 5)と右に行くほど増加するものだったので、Bを(5, 2)と右に行くほど減少するものにしてみる、といった感じです。

このような異なる解き方になりそうなタイプの入力例を思いつく限り、なるべく自分で解く負担が少なそうなものを書いていきます。

ここまで書くと法則が見えてきます。

・数列Aの端の値は数列Bの端の値と同じ
・数列Aの端でない値は、影響を受ける数列Bの値のうち小さい値の方

先程考えていた法則と結果的に同じになりましたが、いくつかのケースを確かめることで、それがなんとなくから確信に変わります。

ちなみにこれ端の値に関しては影響を受ける数列Bの値が1つしかないため、法則は下のように見方を変えることもできます。

・数列Aの値は影響を受ける数列Bの値のうち最も小さい値


ここまでで丁寧に法則を見つけてきたのですが、これならなんとなく法則が分かった時点で実装した方がいいかと思うかもしれません。

しかし私は簡単なケースをいくつか書いて本当に自分の思う正解が正しいのか確かめた方がいいと思います。
合っていることに越したことはありませんが、もし間違っていた場合大幅なタイムロスとなってしまいます。

簡単なケースをいくつか紙に書いて解くことくらいだったらあまり時間もかからないので、色んなケースを確かめて間違える可能性を狭めておくことは非常にコスパのいいやり方だと私は思います。




3. ギリギリのケースは場合分けを駆使する

ここからは実装面でのお話になります。

今回、以下のものを実装すればいいことになりました。
・数列Aの値は影響を受ける数列Bの値のうち最も小さい値

これを実装しようとすると以下のやり方が考えられます。
Ai = min(Bi-1, Bi) 　 　      i = 1からi = n - 1まで n - 1回ループ

しかしこれではi = 1のときはB0が無くてエラーになってしまい、さらにAnの値は何もないということになってしまいます。

そんなときは場合分けをしましょう。答えを全て一般化して実装できればスマートでカッコイイというのはごもっともですが、i = 1のときとi = n - 1のときはそれぞれB1とBn-1を代入するという処理にすれば良いのです。

法則に当てはまらない部分は全部場合分けを駆使して実装することで、コードは多少長くなってしまいますがACは取ることができます。




ご覧ください。ここまで特に高度なスキルは使っていないことがわかると思います。
C問題のように問題文がちょっと複雑になってきても、ここまで述べたように

・紙で書いて答えが出るまでの具体的なプロセスをイメージ
・簡単なケースをいくつか確かめて法則を見つける
・法則通りに実装できない時はひたすら場合分け

この3点を意識して取り組めば、時間がかかっても正解することができるようになります。
そうすれば茶色にグンと近づくことができます。

3. コンテストは絶対出席する！ABCもAGCも！

コンテストには予定が許す限り全部出席しましょう。

実力がまだついていないから・・・前回のコンテスト以降1回も勉強していないから・・・とコンテストの参加に躊躇する必要はありません。

AtCoderでは初めの9戦はレートに大きなマイナス補正がかかります。

従って早く茶色になりたい場合、勉強することももちろん大事ですが、最初の9戦というマイナス補正状態をなるべく早く脱却することも有効な戦略です。

これは決して誇らしいことではないのですが、私はAtCoderを始めて間もない時期にAGCに参加して1問も正解できずに終わったことがあります。

しかしレートは落ちるどころか上がりました。
そのときの結果がこちらです。
※2020年6月現在AGCは灰色だとレートが変化しなくなりました。したがってAGC0完レート上げ戦法は今は使えません。

コンテストに出続けること、これも茶色になるための重要な戦略です。

4. VSCodeでローカルの環境を整える！

VSCodeはマイクロソフト社が出しているソースコードエディタ (以下エディタ) です。

エディタを使うことでAtCoder備え付けのコードテストを使うよりも効率よくコードを書くことができます。

エディタとコードテストとの決定的な違いは、コードを実行してから答えが出力されるまでのタイムラグがほぼないことです。

具体的にはC問題くらいなら実行したらその瞬間答えが出力されるくらい早い処理でコードを実行できます。そのため自分のコードが合っているかのテストにかける時間が大幅に短縮できます。

VSCodeのインストールは以下のリンクからできます。
https://azure.microsoft.com/ja-jp/products/visual-studio-code/


VSCodeのインストールが終わってやることは大きく2つです。

①#include <bits/stdc++.h>が使えるようになるための環境構築
②VSCode上のターミナル上で自分の書いたコードが実行できるようになる




①#include <bits/stdc++.h>が使えるようになるための環境構築

VSCodeをインストールしただけでは思うようにc++が実行できない状態にあります。そのために必要になってくるのが環境構築です。

環境構築は各PCのターミナルを操作して色々やるのですが、自力でやるにはまあまあハードルがあります。

そのため以下の記事を見ながらやるのがオススメです。
私はこの記事を見て、何も考えずにその通りにやったらうまくいきました。

@EngTksさん
Visual studio codeで競プロ環境構築[mac OS]

@AokabiCさん
Visual Studio Codeで競プロ環境構築(導入編)

どちらもqiitaの記事になります。私はmac OSを使っているので、Windowsの方はうまくできる確証はありません。




②VSCode上のターミナル上で自分の書いたコードが実行できるようになる

環境構築が終わったら、AtCoderに提出するときと同じ状況でコードを書くことができるようになります。

具体的なVSCodeの使い方をここでは説明します。
※mac OSでは動作確認済みです。

VSCodeを起動すると以下の画面が出てきます。

まずこの状態で command + shift + P の3つのキーを同時に押します。すると検索バーのようなものが出てきます。そこでshellなどと検索すると、このようなものが出てきます。

Shell Command: Install 'code' command in PATH

クリックするとインストールが行われ、以後ターミナルでcodeコマンドを打つことでVSCodeが起動します。

code a.cpp

このようにcodeの後にファイル名をつけると該当ファイルをVSCodeで開くことができます。(無い場合は新たに作成されます)

次にVSCode上で control + shift + @ の3つのキーを同時に押します。
すると・・・

VSCodeの中にターミナルを出すことができます。
これは非常に便利な機能で、VSCodeの上画面でコーディングを行い、下画面で実行することができます。
つまりコーディングの作業をVSCodeだけで完結させることができます。


コードを書いて実行するまでの流れを説明します。

① ターミナルで code a.cpp コマンドを実行しファイルを作る(この場合a.cppというファイルが生成される)
② コード書く
③ ターミナルで g++ a.cpp コマンドを実行
④ ターミナルで ./a.out コマンドを実行

④まで行うことで書いたコードが実行された状態になります。
そこから問題に合わせて入力値をターミナルで書いていくことで、書いたコードに応じた出力が得られることになります。


これでVSCode上でコードを書いてテストまで行うことができるようになりました。

コーディングを行い提出するまでの時間の短縮が見込めるので、結果的に問題を解く速度を上げることができます。

是非やってみることをオススメします。

5. おわりに

以上を行うことで、コンスタントにレートを上げて茶色になることは可能だと思います。

とはいえここまで書いた戦術は茶色かどんなに良く見積もっても緑になるかならないかまでの戦術だと思います。

それ以上を目指すためにはアルゴリズムの勉強などが必要不可欠になると思います。

私は今、アルゴリズムの勉強をするために以下のサイトを参考に問題を解いて勉強しています。

@drkenさん
AtCoder 版！蟻本 (初級編)

これからも緑、いや水色を目指して頑張っていきます。
また色が変わったらそのためにやってきたことを記事にしようと思います。

ここまで読んでくださりありがとうございました。

この記事が良かったなって思った方はフォローよろしくお願いします＾＾
https://twitter.com/zaurus_yusya

またツッコミなどありましたら、いつでもリプやDMお待ちしております＾＾

ではでは

【番外編】AtCoder Stalker作りました

AtCoderで友達やライバルが問題を解いたらLINEで通知してくれる
AtCoder Stalkerを作りました！！

こんな感じで通知が届きます。ライバルが精進している様子が分かるので、モチベーションアップになればと思います。

友達登録リンク＆QRコード
https://line.me/R/ti/p/@381fkvdg

詳しくはこちらを見てください！
https://note.com/zaurus/n/n3ca56c3305c7