プログラミング初心者が入茶した話

あいさつ

はじめまして。friedriceと申します。今回ABC385にて入茶しました!
初の参加がABC359だったので半年でいけたことになります。
今回この記事を書いた理由は少しでも灰コーダーの皆さんや茶コーダーの皆さんの力になりたいと思ったからです。初投稿なので誤字脱字がたくさんあると思いますがお許しください。

著者の紹介

中学1年生
数学検定2級保持
小学4年生の時くらいからScratchをしている
コマンドプロンプトがちょっとできる

初めてのコンテストに参加するまで

僕はatcoderを始める前、競技プログラミングには全く興味はありませんでしたが、数学にはとても興味がありました。youtubeで数学系の動画を見ていたとき、数学とプログラミングをゆっくりで解説しているえびまラボさん(これ以降：えびまさん)の動画を発見しました。えびまさんの動画を見ているうちに、競技プログラミングについて知りました。そして、atcoderをやってみようと思い、環境整備を始めました。でも上手くいかなかったので、悩んでいたところ、atcoderのサイトにはコードテストなるものがあることを知りました。これで環境整備しなくても土俵に立てる!(環境整備はまたいつかします)…プログラミング言語分からない(絶望)。幸い、atcoderには初心者向けの言語学習の教材があるので、それを使ってc++を勉強しました。

初めてのコンテスト(ABC359)

結果から言います。0完でした。
A問題のWAコードがこちら

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  
  int i = 0;
  int c = 0;
  while (i < N) {
   string text;
   if (text == "Takahashi") {
    c++; 
   }
   i++;
  }
  cout << c << endl;
}

これはひどい(for文を使っていないこと、)入力処理をしていないことが問題点でした。もっとc++を勉強する必要がありました。ちなみにこのときのパフォーマンスは35で、レートが2になりました。

レート100まで

順調にc++の勉強を進めていき、レートが100を超えたときには2完を3回出していました。
でも一向にC問題が解けませんでした。ここのことはあまり覚えてないのでこれくらいです。
レートが100を超えたコンテスト(ABC368)のB問題ACコード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  int ans = 0;
  for(int i = 0; i < 10000; i++) {
    sort(A.begin(), A.end());
    if(A.at(N - 2) <= 0) {
      break;
    }
    reverse(A.begin(), A.end());
    A.at(0)--;
    A.at(1)--;
    ans++;
  }
  cout << ans << endl;
}

レート200まで

C問題をACするには有名なアルゴリズムを覚えなければならないかなとおもい、以下のアルゴリズムを覚えました。

• 二分探索
• DFS
• bit全探索
• 累積和、imos法
  そしてレートが200を超えたABC373にて、初の3完を達成しました!
  →初の茶パフォ(610)も出ました!
  ABC373のC問題ACコード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int ans = 0;
  int max_A = -1000000000;
  vector<int> A(N);
  for(int &o : A) {
    cin >> o;
    max_A = max(o, max_A);
  }
  int max_B = -1000000000;
  vector<int> B(N);
  for(int &o : B) {
    cin >> o;
    max_B = max(o, max_B);
  }
  cout << max_A + max_B << endl;
}

そして、大槻兼資さんの「アルゴリズム的思考が身につく!プログラミングコンテストatcoder入門」という本(自分では鹿本と呼んでいます)を買いました。分かりやすかったのでスキルアップにつながりました。

レート300まで

茶色に行くまでの段階の中で、一番のレート停滞期だったと思います。
ABC376では、1完しかできず、初めてレートが下がりました。(下がると言ってもレートが1減るだけでしたが)その時くらいに蟻本を買ったと思います。が、ちゃんと読むことになるのはもっと先だと思います。ABC378からレート300になるまで、2連続で茶パフォを出すことができました!
勉強したアルゴリズムはこちら

• BFS
• ダイクストラ法
• 繰り返し二乗法
• 基本的なDP(EDPCやABC埋めで鍛えました)
• エラトステネスの篩、素数判定
  レートが300を超えたコンテスト(ABC379)のC問題のACコード(汚めですが許してください)

#include <bits/stdc++.h>
using namespace std;

int64_t f(int64_t x) {
  return x * (x + 1) / 2;
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<int64_t> x(M);
  vector<int64_t> a(M);
  int64_t sum = 0;
  for(int64_t &o : x) {
    cin >> o;
  }
  for(int64_t &o : a) {
    cin >> o;
    sum += o;
  }
  vector<pair<int64_t, int64_t>> XA(M);
  for(int i = 0; i < M; i++) {
    XA.at(i) = make_pair(x.at(i), a.at(i));
  }
  sort(XA.begin(), XA.end());
  XA.push_back(make_pair(N + 1, 0));
  if(sum == N) {
    bool tmp = true;
    if(XA.at(0).first > 1) {
      tmp = false;
    }
    int64_t ans = 0;
    for(int i = 0; i < M; i++) {
      if(XA.at(i + 1).first - XA.at(i).first <= XA.at(i).second) {
        int a = XA.at(i + 1).first - XA.at(i).first;
        XA.at(i + 1).second += XA.at(i).second - a;
        ans += f(a - 1) + (XA.at(i).second - a) * a;
      }
      else {
        tmp = false;
      }
    }
    if(tmp) {
      cout << ans << endl;
    }
    else {
      cout << -1 << endl;
    }
  }
  else {
    cout << -1 << endl;
  }
}

茶色になるまで

安定して茶パフォを出せるようになりました(またレートが下がったこともありましたが)。新たなアルゴリズムは特に学んでないです。やったことはライブラリの整備です。

• mod$998244353$やmod$1000000007$をする構造体(AtCoder libraryをインクルードすればできます)
• long long型をllと書く短縮記法
• エラトステネスの篩をして素数を列挙する関数
• $a^N$を繰り返し二乗法で求める関数
  を実装しました。
  茶色になったABC385のC問題ACコード(考察が上手くいかず、setとmapでゴリ押しした結果1976msでのギリACなりました。計算量解析って大事ですね)

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using mint = atcoder::modint998244353;
using maxt = atcoder::modint1000000007;
vector<ll> Era(int N) {
  vector<ll> ans(0, 0);
  vector<bool> isprime(N + 1, true);
  isprime.at(1) = false;
  for(int i = 1; i <= N; i++) {
    if(isprime.at(i)) {
      ans.push_back(i);
      for(int j = 2 * i; j <= N; j += i) {
        isprime.at(j) = false;
      }
    }
  }
  return ans;
}
ll POW(ll a, int N) {
  if(N == 1) {
    return a;
  }
  ll ans = POW(a, N / 2) * POW(a, N / 2);
  if(N % 2 == 1) {
    ans *= a;
  }
  return ans;
}
//ライブラリここまで

int main() {
  int N;
  cin >> N;
  set<int> h;
  map<int, set<int>> tower;
  for(int i = 1; i <= N; i++) {
    int H;
    cin >> H;
    tower[H].insert(i);
    h.insert(H);
  }
  int ans = 1;
  for(int o : h) {
    int diff = *rbegin(tower[o]) - *begin(tower[o]);
    for(int i = 1; i <= diff; i++) {
      for(int ind : tower[o]) {
        int tmp = 1;
        while(tower[o].count(ind + i)) {
          tmp++;
          ind += i;
        }
        ans = max(ans, tmp);
      }
    }
  }
  cout << ans << endl;
}

茶色になっての感想、そして緑に向けて

正直、C++とは無縁だった僕がここまでいけてとても嬉しいです。
緑になるには、4完や速解きが大事になると思うので、そこを磨いていきたいです。(ABC埋めなど)あとは環境整備をちゃんとやります(そしてライブラリ整備)目標としては、2年生になるまでに入緑したいと思っています。
緑になったらまた記事を書きます。読んでいただきありがとうございました!