青コーダーになるまでにやったこと〜灰編〜

1 自己紹介

こんにちは、千反田えるです。

昨年の4月に競技プログラミングを始めて1年と3か月、7/7にやっとのことで青コーダーとなることができました。 f:id:ChitandaEru:20180709144635p:plain

名前とアイコンが違いますが、これも千反田えるです。千反田えると思えば千反田えるなのです。いいですか？

それはそれとして、青に行くのに49回もかかっています。これは私の周りを見ても比較的遅いですね、というかレートを1600上げるのに1年3か月もかかっているのです。

これは単純に精進不足もあってそれが大半な気もするのですが、競技プログラミングをするために知っておいた方がいいことがあって、それを知らなかったことがレート向上の妨げになっていたような気がするのです。

ということで、今回は青に行くため、というよりレート1600を叩き出すために「ここだけ気をつけよう」という点を何回かに分けて説明していきたいと思います。皆さんもこれを読んでとっとと私を抜かしましょう。

2 灰色編-高難度より早解き-

最初にAtCoderのレートのつき方について確認しておきましょう。

Atcoderはコンテスト中に解いた問題の合計得点、解いた時間の順に順位が決定され、それを元にパフォーマンスを決定、パフォーマンスと今までのコンテスト参加回数等を加味してレートが変動する、といった仕組みになっています。

で、ここで大事なことが１つあって、それは「遅刻して参加しても別にその分の時間は考慮されない」ということですね。

・・・は？と思われた方もいるかもしれませんが、実際私は数ヶ月経つまで毎回2-30分は遅れて参加していましたし、その分の時間差は補ってくれるものと信じて疑っていませんでした。~~鉄緑会~~家の農作業の手伝いで忙しかったので、仕方のないことではあるのですが。ということで、頑張って定時にコンテストに参加するようにしましょう。これは「早解き」の最初の一歩です。

で、ここからは「コンテストに定時参加してるのにレートが上がらないんですが...」みたいな人に教える「早解き」のコツです。

そもそも、「早解き」というのは、「高難度」よりもやりやすいものです。高難度というのは考察で詰まる、実装で詰まる等々解き難いところが多数存在するのに対して、早解きはすでにわかっているものを解くだけです。

蟻本という競技プログラミングのスタンダードみたいな本の功罪として、競技プログラミングをするにはあのレベルの複雑な知識を要求されると勘違いしがちというものがありますが、実際はそんなこともなく、簡単な入出力、四則演算とif,forがかければABCのA,Bに関してはほとんどの場合で解くことが可能です。なので、灰色ならばまずやるべきはA,Bの早解きです。

とりあえずAに関しては競技プログラミングの基礎ともいえる内容です。最低でも5分以内を指標に練習を積むべきです。逆に、それ以上のタイム短縮はさして意味がないと思います。そこまでタイムが縮まればあとはコンテストの中での反復で何もしないでもタイムは縮まっていきますし、それ以上Aに時間をかけて精進するのは時間の無駄である場合が多いです。

で、Bですね。Bには元来200点が配置されるのが慣例です。ここで、私が考える「200の難しい要素」を上げていきます。

・string

多分初心者は大抵ここで詰まると思います。整数値と違って、何をどうすればいいのかわからない。数字を文字列として読み込む、なんて日にはもうお手上げです。

stringを扱う際によく使う書き方を2つほど上げます。

・size()

#include<iostream>
using namespace std;
int main(){
    string s;cin>>s;
    cout<<s.size()<<endl;
    return 0;
}

よくあるやつですね。似たものにlengthがありますが、1年ほど前にそれが原因のバグを生産してから二度と使っていません。というかやや性質が使うものなので、基本的にはsizeで大丈夫だと思います。
文字列の長さを返すだけの関数ですが、1文字ずつ見ていくときには必ずと言っていいほど使う汎用性の高い関数です。
・'a'

#include<iostream>
using namespace std;
int main(){
    string s;cin>>s;
    int num[26]={};
    for(int i=0;i<s.size();i++){
        num[s[i]-'a']++;
    }
    for(int i=0;i<26;i++){
        cout<<num[i]<<" ";
    }cout<<endl;
    return 0;
}

個人的にですが、汎用性は異様に高いのに驚くほど周知がされていないテクニックの一つ。a-zから'a'を引くことで0-25の数字に変換することができます。僕はこれを知るまでは26倍の計算量でループを回していたものですが、こんな便利グッズがあるんだったらさっさと言えよって感じです。
他にも、これを応用して

#include<iostream>
using namespace std;
int main(){
    string s;cin>>s;
    for(int i=0;i<s.size();i++){
        s[i]+=1;
    }
    cout<<s<<endl;
    return 0;
}

といった感じで、sの文字を一つずつ前に進めることができます。例えば、aはbになりますし、xはyになります。(このコードだとzが{になるので、特殊処理を加える必要はありますが)

Cが解きたいそこのあなたへ
ということで、ここまでA,Bの解き方について見ていきました。これさえできれば詰まるABはほとんどないでしょう。
それで、問題はCです。灰色の時点でも、やはりCが解ければレートの大幅な上昇が見込めます。もうCが解ければ茶色に上がれるときだってあるでしょう。これのコツを書こうと思ったのですが、いかんせんもうかなり字数も多く、ネタ切れも怖いので、今回はこの辺に。