うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

yukicoder で testlib を使うためのメモ


この記事は

この記事は yukicoder での作問において testlib を用いて簡単に正確な入力の検証、およびスペシャルジャッジ作成をしよう、という記事です。 また、ローカルでの作業に Rime を使うことを想定しています。

実際のコードについては以下を参照してください

github.com


testlib とは?

testlib は、Codeforcces の admin の MikeMirzayanov 氏が作ったライブラリ(C++ のヘッダーファイル)です。

github.com

codeforces.com

主に以下を行う際に便利な関数が含まれています。

  • 入力生成器 (generator) の作成
  • 入力検証器 (validator) の作成
  • 出力検証器 (checker / judge) の作成

入力検証器、出力検証器は作らなくても問題を出題することはできますが、問題を用意する際には必ず用意するべきだと考えています。

なぜ入力検証器が必要なのか

入力検証器とは、生成した(または手で作った)入力ファイルが入力フォーマットを満たしているかを判定するプログラムのことを指します。

競技プログラミングに参加する人の多くは C++ を使っており、問題の準備において writer / tester による想定解が C++ のみしか用意されない、ということも少なくありません。 ところで C++ の istream(std::cin 等)は半角スペース、改行等を自動で読み飛ばしてくれます。

よって、例え制約等は assert 等でチェックしていたとしても、以下のようなケースを検出することができません。 そして、そのようなケースで正常に動作しないような言語は存在するため、コンテスト中に指摘された場合は入力を修正してリジャッジを行う必要が出てきます。 (以下は全て実際のコンテストで遭遇したことがあります)

  • 行頭または行末に不要な半角スペースが含まれている
  • 問題文中では空白区切りで入力されると書かれているが、実際には改行区切りで入力される

なぜ出力検証器が必要なのか

出力検証器とは、提出されたプログラムの出力が正答であるかを判定するプログラムのことを指します。

基本的には事前に用意した想定出力との diff を取ることで判定することができますが、最近は多くのジャッジで不要な半角スペースや改行を許容するジャッジになっていることが多く、これはそのような判定プログラムを書くことで実現しています。 また、想定出力が複数あるような場合は単純な diff では判定できないため、その場合も判定プログラムを書く必要があります。

これも C++ 等で普通に書けば良いような気がしますが、以下のようなケースで正常に判定できないことがあります。

  • プログラムの出力が足りない場合
    • std::cin は EOF に到達した状態でさらに値を読んでもなんらかの値を返すため
  • 実数が出力されるべきところで nan と出力された場合
    • 実際に、誤差ジャッジにおいて nan と出力して AC となってしまったような問題が存在しました

現在 testlib に関する詳細なドキュメントは存在しません(上に貼った Codeforces のページが一番詳しく、それ以上の情報は実際の実装を読むしかありません)。

自分もそこまで詳しくはないので、誰か複数人で非公式 doc でも用意できればいいんですが……


Rime とは?

Rime は、JAG(日本の ICPC の OB/OG 会)が作成した、プログラミングコンテストの問題作成支援ツールです。 ドキュメントやブログ記事が詳しいので詳しくは以下を見てください。

github.com

rime.readthedocs.io

beet-aizu.hatenablog.com

なぜ Rime なのか

Rime 以外にも作問支援ツールは多く存在するため、特に Rime を使う必要はありません。他の作問支援ツールについてはいくつかは以下の issue で触れられています。

github.com

その中で、今回は以下の理由から Rime を用いました(別に他のツールでも良いと思います)。

  • 大学合宿コンテスト等の有志コンテストの準備においてよく用いられている
  • 他の作問支援ツールに比べて機能が多い

yukicoder で testlib を用いる

最近、yukicoder の環境で testlib.h が使えるようになりました(ありがとうございます!!)。

ただ、実際には testlib (or Rime) で想定されている用い方と yukicoder の仕様が異なるケースも多く、そのまますぐスペシャルジャッジ等に使えるというわけではありません。

よって、この記事では以下を実現することを目的とします。

  • yukicoder 上で testlib を用いたジェネレータ、スペシャルジャッジ、リアクティブジャッジ、スコアリングジャッジを作る
    • バリデーターについては現状 yukicoder でバリデーターを登録する機能がないため、通常の AC コードの入力を受け取る部分を testlib に置き換えることで対応する必要があります。
  • yukicoder と Rime で同じコードでジェネレータ、スペシャルジャッジ、リアクティブジャッジ、スコアリングジャッジが動くようにする
    • ジェネレータについては、同じケースが生成されるようにする

詳しくは以下の README を参照してください!(あとでもう少し情報を追加するかもしれません)

github.com

各バケットに区間のindexを持たせる平方分割


結論

まぁ本質以外もちょこちょこ書きかえなきゃいけなくて結局そこでバグらせるんですが……



この記事について

この記事は、平方分割の簡単かもしれない実装方法を紹介するものです。

平方分割って何? という人には、以下の 3 つの記事がわかりやすいのでおすすめです。

www.slideshare.net caddi.tech kujira16.hateblo.jp

(本当はこの記事でも平方分割についてわかりやすい包括的な説明をしようと思っていたのですが力尽きました…)



実装方法

多くの記事では、主に以下のような実装がなされることが多いです。

[TODO: ここによくある実装を書く]

ただ、どうしてもインデックスをいじりつつ更新等をしていくことになるため、実装が煩雑になったりバグの原因になったりすることが多いです。

例えば、区間更新、区間 Max を平方分割で解くときに、区間 Max のクエリに対し、区間の一部が被っているバケットについてはそのバケット内の全ての値を更新した上で Max を求め、区間に完全に包含されているバケットについては値の更新はせずに区間に対する更新を適用した上での Max を求める、と言った処理をすることになり、それをインデックスをいじっている中で行うのはかなりつらいです(個人の感想です)。


実装方針

ここで、以下のような実装をすることを考えます。

  • 問題を解く関数側では、とりあえずそのバケット区間に包含されているかは全く気にせず全てのバケットに対し更新、計算を行わせる。
  • バケット側で区間との包含関係(全く被っていない、完全に包含されている、一部が被っている)を求め、それぞれに応じた処理を行う。

これはかなりセグメント木に似てますね。 実際に平方分割は、セグメント木が 2 分木なのに対する √N 分木と考えることができるので、同じような実装ができるのも妥当とも言えそうです。


具体的な実装

ここでは、区間 Add 区間 Min の以下の問題を例にコードを示していきます。

なお、この問題は遅延セグメント木などを用いることでより良い計算量で解くことが可能であることに注意してください。

onlinejudge.u-aizu.ac.jp

骨組み

今回は、平方分割 class sqrt_decomp の中に、1 つのバケットを表すような class bucket を用意します。

class sqrt_decomp {
  class bucket {
    int l, r;
    vector<int> v;

  public:
    bucket(const vector<int>& a, int l, int r) : l(l), r(r) {
      v = vector<int>(r - l);
      for (int i = 0; i < r - l; ++i) {
        v[i] = a[i + l];
      }
    }
  };

  vector<bucket> v;

public:
  sqrt_decomp(const vector<int>& a, int bucket_size) {
    v = vector<bucket>();
    for (int i = 0; i < (int)a.size(); i += bucket_size) {
      v.emplace_back(a, i, min(i + bucket_size, (int)a.size()));
    }
  }
};

更新クエリ

まずは更新を書いてみます。

a_l, a_{l+1}, ... , a_{r-1}x を加算するクエリを考えます。

バケット全体が更新区間に含まれる場合

まず、そのバケット全体が更新区間に含まれている場合を考えます。そのとき、当然その区間の値には全て x が加算されます。 ただ、そのバケット内の値を一つずつ変更していくと結局全体の計算量 {O(NQ)} になってしまうので、「そのバケット全体にいくつ加算されたか」という情報を持っておくことにします。

int add_val;

void update_all(int x) {
  add_val += x;
}

バケットの一部が更新区間に含まれる場合

次に、そのバケットの一部が更新区間に含まれる場合を考えます。 この場合は、以下の 3 つの処理を順番に行う必要があります(演算の性質によっては一部の更新をサボれることもありますが、ここでは割愛します)。

  1. バケット全体に対する更新を適用する (reflect_update)
  2. 今回のクエリでの更新を適用する
  3. バケット全体に対する回答クエリで答えるべき値(今回は最小値)を求める (reflect_calc)

1 番でバケット全体に対する更新を適用したら、きちんと「そのバケット全体にいくつ加算されたか」を初期化することを忘れないようにしましょう。

vector<int> v;
int min_val;
int add_val;

void reflect_update() {
  for (auto& i : v) {
    i += add_val;
  }
  add_val = 0;
}

void reflect_calc() {
  min_val = INT_MAX;
  for (auto& i : v) {
    min_val = min(min_val, i);
  }
}

void update_partial(int l, int r, int x) {
  reflect_update();
  for (int i = l; i < r; ++i) {
    v[i] += x;
  }
  reflect_calc();
}

呼び出し方法

上で作った関数を呼び出せば更新クエリは完了です。

呼び出し元からはそのバケットとクエリ区間との位置関係は気にせず全てのバケットに対して更新を走らせて、実際にどういった更新を行うかは中で判定するようにすると、問題に応じて書きかえる部分がシンプルになるので楽だと思います。

int l, r;
void update(int s, int t, int x) {
  if (r <= s || t <= l) {
    return;
  } else if (s <= l && r <= t) {
    update_all(x);
  } else {
    update_partial(max(s, l) - l, min(t, r) - l, x);
  }
}

ここまで書いたコードを全て bucket class の中に放り込み、sqrt_bucket class の方に全ての bucket に対して update を走らせる関数を書けば変更クエリは完成です。

vector<bucket> v;
void update(int l, int r, int x) {
  for (auto& i : v) {
    i.update(l, r, x);
  }
}

回答クエリ

次に回答クエリ(今回は最小値)を書いていきます。

a_l, a_{l+1}, ... , a_{r-1} の最小値を求めるクエリを考えます。

バケット全体が回答区間に含まれる場合

バケット全体がクエリの区間に含まれている場合、予め計算した最小値に対し、バケット全体への加算を足し合わせればその部分の最小値が得られます。

int min_val;
int add_val;
int calc_all() {
  return min_val + add_val;
}

バケットの一部が回答区間に含まれる場合

バケットの一部がクエリの区間に含まれている場合、更新の時と同じように以下のような 3 つの処理を順番に行います。

  1. バケット全体に対する更新を適用する (reflect_update)
  2. バケット全体に対する回答クエリで答えるべき値(今回は最小値)を求める (reflect_calc)
  3. 今回のクエリの区間に対する答えるべき値(最小値)を求める
vector<int> v;
int calc_partial(int l, int r) {
  reflect_update();
  reflect_calc();
  int res = INT_MAX;
  for (int i = l; i < r; ++i) {
    res = min(res, v[i]);
  }
  return res;
}
実は…?

実は回答クエリにおいて必ずしもバケット全体に更新を適用する必要はなく、以下のようにクエリと被っている区間のみ一時的に更新を評価するだけでも良いです。

この場合、更新クエリが一部分に被ったときにのみしか更新が伝播しないため、上記の実装よりも若干高速になることが多いです。

vector<int> v;
int calc_partial(int l, int r) {
  int res = INT_MAX;
  for (int i = l; i < r; ++i) {
    res = min(res, v[i] + add_val);
  }
  return res;
}

呼び出し方法

更新クエリと同様に、クエリ区間との位置関係は気にせず全てのバケットに対してクエリを走らせる方針を取ります。

int l, r;
int calc(int s, int t) {
  if (r <= s || t <= l) {
    return INT_MAX;
  } else if (s <= l && r <= t) {
    return calc_all();
  } else {
    return calc_partial(max(s, l) - l, min(t, r) - l);
  }
}

ここまで書いたコードを全て bucket class の中に放り込み、sqrt_bucket class の方に全ての bucket に対して calc を走らせる関数を書けば回答クエリも完成です。

vector<bucket> v;
int calc(int l, int r) {
  int res = INT_MAX;
  for (auto& i : v) {
    res = min(res, i.calc(l, r));
  }
  return res;
}

提出例

以上のコードをまとめたものが以下になります。 コード自体は長いけど部分部分は簡単……?

class sqrt_decomp {
  class bucket {
    int l, r;
    vector<int> v;
    int min_val;
    int add_val;

    void reflect_update() {
      for (auto& i : v) {
        i += add_val;
      }
      add_val = 0;
    }

    void reflect_calc() {
      min_val = INT_MAX;
      for (auto& i : v) {
        min_val = min(min_val, i);
      }
    }

    void update_partial(int l, int r, int x) {
      reflect_update();
      for (int i = l; i < r; ++i) {
        v[i] += x;
      }
      reflect_calc();
    }

    void update_all(int x) {
      add_val += x;
    }

    int calc_partial(int l, int r) {
      reflect_update();
      reflect_calc();
      int res = INT_MAX;
      for (int i = l; i < r; ++i) {
        res = min(res, v[i]);
      }
      return res;
    }

    int calc_all() {
      return min_val + add_val;
    }

  public:
    bucket(const vector<int>& a, int l, int r) : l(l), r(r), add_val(0) {
      v = vector<int>(r - l);
      for (int i = 0; i < r - l; ++i) {
        v[i] = a[i + l];
      }
      reflect_calc();
    }

    void update(int s, int t, int x) {
      if (r <= s || t <= l) {
        return;
      } else if (s <= l && r <= t) {
        update_all(x);
      } else {
        update_partial(max(s, l) - l, min(t, r) - l, x);
      }
    }

    int calc(int s, int t) {
      if (r <= s || t <= l) {
        return INT_MAX;
      } else if (s <= l && r <= t) {
        return calc_all();
      } else {
        return calc_partial(max(s, l) - l, min(t, r) - l);
      }
    }
  };

  vector<bucket> v;

public:
  sqrt_decomp(const vector<int>& a, int bucket_size) {
    v = vector<bucket>();
    for (int i = 0; i < (int)a.size(); i += bucket_size) {
      v.emplace_back(a, i, min(i + bucket_size, (int)a.size()));
    }
  }

  void update(int l, int r, int x) {
    for (auto& i : v) {
      i.update(l, r, x);
    }
  }

  int calc(int l, int r) {
    int res = INT_MAX;
    for (auto& i : v) {
      res = min(res, i.calc(l, r));
    }
    return res;
  }
};

提出例です https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_H/review/4879712/rian_tkb/C++17


抽象化について

せっかくなので抽象化して中身をいじらずに様々な問題に適用できるようにしたいのですが、平方分割は遅延セグメント木などに比べて自由度が高く、上手い抽象化方法が考えれらていない状態です。 上手い抽象化が出来た方はぜひ教えていただけると助かります。



類題

  • 区間代入区間 Min (AOJ)
  • 区間 Add 区間 Sum (AOJ)
  • 区間代入区間 Sum (AOJ)
    • 上のコードとほぼ同じようなコードで AC できると思います。
    • こちらも遅延セグメント木で解くことができます。
  • Range K-th Smallest (Library Checker)
    • 蟻本の平方分割の項に載っている問題です。が、制約がかなり大きいので通りません(かなり頑張って高速化をすれば通るかもしれませんが…)
    • 記事中では reflect_calc において「答えそのもの」を求めていますが、実は「答えを高速に求めるための情報」を求めるようにすることでより多様な問題に対応することができ、この問題もそのような問題の一つです。
    • この問題では「バケット内の値をソートしたもの」を求めておくことで、「そのバケット内に x 以下の数が何個存在するか」という、クエリに依存する値を高速に求めることができます。
    • TLE ですがコードです https://judge.yosupo.jp/submission/25166
    • 素直に領域木を書いたりウェーブレット行列を使ったりしましょう。
  • HUPC2020 day1-G Freqs (AOJ)
    • Range K-th Smallest で用いた「x 以下の数が何個存在するか」というクエリに chmin, chmax, add で更新しつつ答える問題です。
    • そのバケット全体に chmin, chmax, add が飛んできても元の要素の順序関係が崩れないので、各要素に更新を伝播しなくとも二分探索で「x 以下の数が何個存在するか」を求めることができます。
    • そのバケットの一部分に chmin, chmax, add が飛んできたら、そのバケット全体を更新してからもう一度ソートしたものを再計算すれば良いです。その操作にかかる計算量は {O(\sqrt{N}\log{N})} で、一部分に更新クエリが被るようなバケットの個数は 1 つの更新クエリに対し高々 2 個なので、クエリあたりの計算量は {O(\sqrt{N}\log{N})} となり、間に合います。
    • バケット 1 つあたりのサイズに対して {\log} がかかるため、バケットサイズは 100 ~ 200 程度にすると速いです(計算量的には変わらないはず…?)。
    • コードです https://onlinejudge.u-aizu.ac.jp/solutions/problem/3170/review/4880051/rian_tkb/C++17
  • Range Chmin Chmax Add Range Sum (Library Checker)
    • segment tree beats で解けることで有名な問題です。
    • 上の問題のコードを少し変えるとこちらも解くことができます。
    • 「ソートしたもの」の他に「ソートしたものにおける累積和」を持っておくことで、「chmin, chmax により値が変わらなかったもの」の総和を {O(1)} で求めることができ、上の問題と同じ計算量で解くことができます。
    • コードです https://judge.yosupo.jp/submission/25173

AtCoder Text(cat) 傾向と対策

これは IQ1 Advent Calendar 2019 の 2 日目の記事です
adventar.org


これは 2019/12/02 当時の情報で、ここから更新する気はあまりないです。
ここには 103 問存在していると思います

AC 時の得点が一意である問題

AC 時の得点が一意でない問題

答えが一意である問題

  • そんなものはない

答えが一意でない問題

ジャッジが正常でない問題

ジャッジが壊れている問題

ジャッジが用意されていない問題

その他

ラソンならば Text(cat) で AC できる?

その他

  • 一部の問題はジャッジが壊れて WA や IE しか出ない状態になっていたりしており(おそらく言語アップデートの影響?)、本来 Text(cat) で AC できるのにできないようになっている問題が存在する
  • Text(cat) の言語 ID は 2 種類存在する
    • 言語アップデート時に振り直されており、アップデート前は 17、アップデート後は 3027
  • Text(cat) で AC 可能な問題を探すため、全問題に対し Text(cat) の AC 提出があるかクローリングするプログラムを書いた
    • AtCoder への負荷を減らすため最低限 O(問題数) くらいの fetch しかしないようにはしているが、それでも問題数が多いのでどうしようかなとなっています

東京工業大学プログラミングコンテスト2019 (TTPC2019) の運営

東京工業大学プログラミングコンテスト2019 (TTPC2019) がどのように運営されたかを書いていこうと思います。
atcoder.jp

メンバー

主犯

  • riantkb

Writer/Tester

カッコ内は今回のコンテストで使用された問題における writer/tester 数

  • rickytheta (3/2)
  • riantkb (3/11)
  • noshi91 (1/6)
  • goodbaton (2/1)
  • abc050 (3/1)
  • mikit (1/1)
  • kcvlex (0/7)
  • arkark (1/1)
  • ninja7 (1/2)

オンサイトお手伝い

  • Ashurnasirpal
  • monman53

テストプレイ (OB)

  • camypaper
  • tokoharu

体制

Writer 陣のレートが低くなかったため、基本的には原案者がそのまま作問までやる方針になりました。
各問題 Tester は最低でも 1 人、基本的には 2 人以上つくようにして、また少なくとも 1 人は橙以上が Writer または Tester に含まれるようにしました。

全ての問題のテストは Rime を使って行われ、かつ全ての問題に対し testlib.h を用いた generator/validator が用いられました。

github.com
rime.readthedocs.io

Rime, testlib に対する知見がかなり溜まったので、そのうち余裕があったら何か記事を書くかもしれません(一生書かなさそう)。

みんなレートは高いんですが作問経験がほぼなかったので(しいて言うと自分が yukicoder で 15 問くらい作ったことがあるのと別の場所で作問のおしごとをしたことがあるくらい)、基本的に自分が問題準備のやり方を整備してみんなに準備してもらい、細かい問題文の修正などについては全て自分がやるようにしました(これは自分に半角英数字の前後は必ず半角スペースを開けたい、みたいなこだわりが色々多かったのも理由にあります)。

オンサイトイベント

tsukammo さんに多大なご協力をいただき、オンサイトイベントを同時に開催できることになりました。本当にありがとうございました!!!

atnd.org

活用したサービス

TTPC2019 において活用されたのは主に以下のサービスです

Slack

主に以下のようなチャンネルが存在していました。

  • #general, #random
  • #problem_idea(問題案の投下)
  • #meeting-日付(Slack 上でのミーティング)
  • #nittei_chosei(ミーティングの日程調整)
  • #githubGitHub へのコミットやコメントなどが垂れ流される)
  • #ci(Travis CI のテスト結果が垂れ流される)
  • #ttpc2019_0831(当日の連絡用)
  • #jikkyo(コンテスト中の実況)

問題案については最終的には 30 問ちょいくらいありました。

Google スプレッドシート

色々な用途で使用されましたが、一番大きく使用されたのは問題案整理だと思います。

#problem_idea に書かれた問題案をシートに書いて、難易度や推薦度などの投票をしていました(結局この投票はそこまで意味を持たなかったですが…)

f:id:riantkb:20190902005907p:plain

あとはテスター進捗状況を管理したりするのに使われていました。

GitHub

問題準備には GitHub のプライベートリポジトリが使われました。

実際の使い方としては、問題を 1 問準備するときはその問題用のブランチを master から切ってその中で準備をし、ある程度完成したら master にプルリクを飛ばす、というようにしていました。
問題文や制約の修正提案などはプルリクのコメントで行われていたような気がします(ほんまか?)。
ちなみにマージされる条件は定義されておらず、コンテストが終わってこの記事を書いている現時点でもマージされていません。

各問題の作業ブランチが分離しているためわかりやすく作業もしやすい反面、generator/validator を書いているときに他の問題からコピーしてこようとするときや、実際にサーバーに問題をアップロードするときなどに面倒だったので一長一短だったような気もします。

Travis CI

rime test を CI で回していました。
どうせ GitHub にコミットする前に手元でテストをするのでそこまで必要感はなかったのですが、Tester の中で PC のスペックが異なるときの実行時間計測などにおいて一つの指標になった(有用かは置いておいて)のでまぁあってよかったかなという気持ちです。

Google スライド

解説を書くのに使いました。
各々で同時に編集ができるので、各問題で別々に作ってあとでマージする手間が省けて良いと思います。
数式が書けないのと PDF にエクスポートする時に微妙に崩れるのが難点。

所感

  • 問題案は集めまくって損することはないのでどんどん溜めたほうがよい
  • Java, C#, Python あたりをそこそこ自由に書ける人がいるとよい
  • きちんとスケジュールを立てて計画的に準備すべき(TTPC2019 では失敗しました)
  • 誰か 1 人はものぐさでなく、外部とちゃんと連絡を取ったり会議の調整とか進捗を煽ったりできる人間がいるとよい
    • しかし、それが 1 人だけだとその人に仕事の 95% くらいが集中して危険



おまけ(大まかな流れ)

2月初め

TTPC Slack, GitHub リポジトリが作られる

ゴールデンウィーク

作問合宿(大学に集まって問題アイデアを出しまくる会)が開かれる
確か N法陣、Inversion Numbers of Tree あたりはこの時に作られた気がします

7月中旬〜後半

日程が決まる
オンサイト会場も決まる
コンテスト時間は 4 時間のつもり
この頃から毎週末に Slack 上で meeting を始める
問題の準備の仕方が確立する(やっと!?)

8月初め

オンサイトの atnd を公開し、参加者の募集を始める
丸 1 日くらいで埋まってウケる
参加者に銀冠がいてウケる

8/18 あたり

大まかな採用問題が決まる
問題準備とテスターをがんばる

8/25 あたり

採用問題に嘘が見つかり冷える
制約を変更することで事なきを得る
採用問題が確定する
死ぬほど問題文を修正する
テストプレイをしてもらったら虐殺セットであることが判明した
とりあえずコンテスト時間を 5 時間にすることにした

8/30

銀冠に 3 時間で全完される恐怖に打ち勝ち、セットの中で一番難しい問題を抜いて Next TTPC(この日に思いついた)を入れた
問題の順序がずれたので死ぬ気で修正する
なぜか麻雀をした

8/31

本番
胃が痛い
なんとかなってよかった

レッドコーダーなので就活で俺TUEEEEをしようと思ったがそうもいかなかった件(タイトル募集中です)

はじめに

このタイトルは若干盛っています。すぐに出てきますが、自分がレッドコーダーなのは Codeforces というサイト(いま世界で一番参加人数が多いコンテストサイトですかね?)においてで、日本で有名な AtCoder では一つ下のランクであるオレンジコーダーです。

また、これも後述されますが、自分には他の競技プログラマにないディスアドバンテージを持っていたりするので、決して一般的な話でなくあくまでも一個人の話であることを念頭においてください。
例えば、この記事のせいで「この人が落ちたんだから自分なんて受かるわけないし諦めよう」とかなって企業に不利益が出たとか言われても困るし。
また、就活模様は毎年大きく変化すると思うので、今後就活がある人は本当にあくまでも参考という程度にしてください。


お前は誰

競技プログラミング

rian, riantkb, rian_tkb などの名前でコンテストなどに参加しています。

AtCoder

atcoder.jp
f:id:riantkb:20190703152522p:plain
レートは日本人の中で 50 番目くらい、日本人の学生の中で 30 番目くらい、同学年の中で 5 番目くらいに高いと思います。

Topcoder

www.topcoder.com
f:id:riantkb:20190703153423p:plain
統計情報はよく知りませんがまぁまぁ高い方だと思います(ほんまか?)。

Codeforces

codeforces.com
f:id:riantkb:20190703171057p:plain
レートは日本人の中で 30 番目くらい、日本人の学生の中で 15 番目くらいに高いです。

その他

ICPC2018(年に 1 度の 3 人 1 組の学生チーム戦)の国内予選で 2 位を取ったり、SnackDown2017(2 年に 1 度くらいの 2 人 1 組のチーム戦)で決勝まで進んでインドに行ったりしました。
コンテストの中には本戦に進出したり上位に入賞したりすると T シャツがもらえたりするものもあるのですが、そんな T シャツが家に 20~30 着ほどあります。

学歴

東京にある国立中高一貫男子校(もしかしてこれって一意ですか)に 6 年間通い、東工大に進学しました。大学院も東工大に進み、情報工学を専攻しています。研究は学部 4 年から、バイオインフォマティクス(生命情報解析)と呼ばれる分野に関する研究をしています。


面接でアピールした事柄たち

以下に書いたことはもちろん全てを一度の面接で言ったわけではなくて、全ての面接の和集合を取った感じです。

研究

すごく簡単に研究でどんなことをやっているかの説明をしました(機械学習など、技術としてわかりやすいことをやっているわけではない(強いて言うならば最適化)ので、どちらかと言うと、こういう理由でこういう需要があるため、こんなような問題を解いている、みたいなストーリーの方をわかりやすく説明することが多かったです)。
具体的な内容が気になる方は研究会発表のときのスライドを乗っけておくのでこちらを参照してください(後で出てきますが、自己紹介用のスライドを持っていくタイプの面接ではこれを 5 ページ程度にまとめて説明しました)。
github.com

業績はほとんどないんですが、一応国際論文の 3rd author に入ったり、国内の研究会で発表して(上のスライドのやつ)優秀プレゼンテーション賞をいただいたりしました。

インターン

修士1年の夏に、④社(この表記は後でわかるので今は気にしないでください)で 6週間のインターンをしました。
内容はガチガチのフロントエンド開発業務で、開発業務経験がないどころか JavaScript なんて 1 文字も書いたことない、MVC モデルって何、という状態から、ひいひい言いながら Spring, React, Redux などを使った開発をしていました。
一応期間中にデプロイできて、簡単なリアクションをいただくところまでいけたはずです。

インターンにいく前は自分がガチガチの開発業務をする将来なんてものは全然考えていなかったのですが、インターンでやってみてこういうのも全然面白いし、何より保守を考えてわかりやすく簡潔なコードを書いていくというのはわりと得意で向いてるかも、と思った記憶があります。

アプリ開発

大学院の授業の一貫で、Android アプリの開発をしていました。
2 回あって片方が半月ほどの個人開発(実際には計画性が虚無なので半日で作った)、もう片方は 1 年間のチーム開発でした。

個人開発の方だけ簡単に説明をしておくと、写真を撮るとそこから顔検出をして映った人の顔を福山雅治に置き換える、というアプリを作りました。
github.com


ウェブ開発 (TokyoTech Online Judge)

学部2年生向け向けの C 言語の実習の授業の TA をしていて、その授業で使用するオンラインジャッジシステムの保守運用、bug fix、および一部機能の開発をしていました(実際に開発したのは 2 つ上の先輩なんですが、すでにご卒業されていて大学にいないため)。
Ruby on Rails, Docker, MySQL あたりをひいこら言いながら触っていて、ずっと原因不明だったバグを解決したり新たに順位表機能やスコア問題機能を実装したりしました。

開発? (TSP Visualizer)

上の TA の関連で、TSP のビジュアライザを作ったりしました。kimiyuki さんのフレームワークをお借りして(魔改造して)作りました。
TypeScript を触るのは初めてでしたが、型があるっていいなぁとなった(適当)。
github.com
riantkb.github.io


ディスアドバンテージについて

これは書くかどうかけっこう迷ったんですが、この記事の内容をより正確に、客観的に評価してもらうには書く方が正しいと思ったので書きます。

吃音症

自分はけっこう重めの吃音症を患っています(障害と見なされるようになったらしいので患う、という表現はもしかしたら適切でないかもしれません)。
吃音症についての説明は wikipedia とかを参照してください。
ja.wikipedia.org

どんな感じかという説明はなかなか難しいのですが、一つの例を挙げるとすると、自分の場合は語頭の無声音が苦手で、自分の名字を吃らずに言うことができない、というのがあったりします。
また、相手にわかりやすく伝えるために抑揚をつけて喋るときや、緊張しているときに吃りやすくなるため、端的に言うと面接に死ぬほど向いていないです(ちなみに、べつに緊張していなくても吃るので家族や友達などと話すときも普通に吃ります)。
同様に研究発表も死ぬほど向いていなくて、普通の人が半分くらいの時間で発表し終わるような分量まで削って持っていくことが多いです(かなしい)。

このような背景があったのですが、これが直接的にディスアドバンテージになった(この人は吃音持ちだから取るのをやめよう)とかがあったかどうかは知りません。というかさすがにそれはないんじゃないなぁと思います(これは楽観しすぎですか?)。
ただ、やはり必ず間接的にはディスアドバンテージになっていると思う(吃ってしまい十分に自己アピールができなかった、等)ので、就活の参考にする際にはその点も踏まえるべきかもしれないです。


就活概要

就活の結果としては、7 社を受けて、内定をいただくことができたのは 2 社でした。
これらをおおよそ最終結果が出たのが早い順に ①社〜⑦社 と呼ぶことにします。

①社

①社は ICPC のスポンサーもしていてなるほどなぁ〜、と思ったので 3 月末くらいにエントリーをしました。
通常コースとスペシャリストコース的なのがあったと思うんですが、普通の方に申し込みました。

4 月中旬くらいに web テストを受けて(競プロちっくな問題だった気がします)、5 月中旬くらいに 1 次面接を受けてそこで落ちました。

1 次面接では面接官がフロントエンドのエンジニアの方だったので、基本的にインターンの話を聞かれました。
ただ、如何せん1年近く前のことで、かつそのときすでに TOJ を触っていたこともあり薄い記憶の彼方な話をしていた記憶があります。

また、会社内で競技プログラミングがあまり盛んでないらしく(面接官の方々もやっておらず、また周りでやっている人も知らないとのこと)、なんで ICPC のスポンサーやっているんだろうと思った記憶があります(それを実際に聞いたかどうかが記憶がない…)。

②社

②社は AtCoder でコンテストも開いており、競プロer で行っている人が多く、また楽しそうな雰囲気もすごく伝わってきていたので 5 月初めくらいにエントリーしました。
ここまでエントリーが遅くなった理由としては、正確には②社の中のあるグループ会社?に入りたかったんですが、②社が全社一括採用をしていてどうすればいいのかわからなかったというのがあります。そして、どうすればよかったのかは結局最後までわかりませんでした。

その後、5 月中旬くらいに web テストを受けて(これは競プロちっくな問題とそうでない問題が両方あった気がします)、その結果が返ってきませんでした(え?)

終わりです(え?)

③社

③社はまず去年の夏にインターンにエントリーをしていました。インターンに関しては通過したんですが結局④社の方に行ったので参加はせず、という感じでした。

その後、登録したメールアドレスに新卒採用に関するメールが来るようになって、暇だし web テストだけ受けておくか…、って言って 1 月中旬くらいに受けました(競プロちっくな問題だった気がします)。

すると通過となり、1 次面接の日程を予約しろというメールがきました。しかしめんどくさいのでスルーします。
1 次面接の日程を予約しろというメールがきました。しかしめんどくさいのでスルーします。
1 次面接の日程を予約しろというメールがきました。しかしめんどくさいのでスルーします。
1 次面接の日程を予約しろというメールがきました。しかしめんどくさいのでスルーします。

……

そんなメールを 8 回くらいスルーしていたら、いきなり電話がかかってきて「お前来週のこの日空いてるか? 面接すっぞ」って言われました(もちろんこれは超意訳です)。
そうして 4 月初めくらいに 1 次面接を受けに行きました。

すると通過となり、2 次面接の日程を予約しろというメールがきました。しかしめんどくさいのでスルーします。

今度はすぐ電話がきました。2 次面接の日程が決まり、2 次面接をします。

そんなこんなで 4 月中に 3 回面接をしました。

ただ、その時点では他の企業の選考が本当に全く進んでいなかったので、5 月末にもう一回面接をすることになりました。
そこで 4 回目の面接をして、内定を頂きました。

④社

④社は実際にインターンに行ったところです。
人事さんと仲良くなったので、エントリーが始まったときに教えてもらい、3 月末くらいにエントリーをしました。

その後 web テスト(競プロ)と英語テスト(つらい)と適性検査(SPI と呼ばれるやつ?)を受けて、6 月初めくらいに 1 次面接を受けました。

面接の形式は 1 時間のコーディングインタビューで、自分の場合は日本語でした(人による?)。


朝一だったので頭が回っておらず任意のコーナーケースを踏みまくりましたが、まぁちゃんと最後まで行ったっぽいし大丈夫かな、と思っていたんですが落ちました(サイレントお祈りをされました)。かなしいね。

⑤社

⑤社も AtCoder でコンテストも開いている会社です。最近強い競プロer がモリモリ入っている印象で、また研究室の先輩で行っている人が多いという印象もありました。
競技プログラミングのレートが高いとあるコースに申し込めて、そのコースの人は初年度の年収が高くなる、という話があったので 4 月中旬くらいにそのコースでエントリーしました(AtCoder のレートはギリギリ足らなかったんですが、Codeforces のレートが足りていたため)。

その後、5 月初めくらいに 1 次面接を受けました(そのときに実は本来 1 次面接より前にある web テストが免除されていた、という話を聞いた気がします)。

1 次面接は通過となり、6 月中旬くらいに 2 次面接を受けました。
2 次面接は自分のやってきた技術分野とかの紹介スライドを持って行って 5 分程度プレゼンするという形式で、まぁ上に書いたことの一部を適当に持って行きました。わりと研究の話がウケていたような気がします。

その後 6 月末にもう一度面接があり、そこで内定を頂きました。
ただ、初年度の年収に関しては一般の修士卒の金額で、という話でした。理由としては、アルゴリズムなどの知識・経験などは十分だが web 系の経験はまだ十分とは言えないので、という説明をされました。

⑥社

⑥社は 3 月末くらいに ICPC に参加した学生向けのイベントがあり、そこでエントリーをしました。

その後 4 月中旬くらいに web テストがあり、5 月中旬くらいにオンライン面接(日本語)がありました。
このオンライン面接もコーディングインタビュー的な感じでした。問題が興味深かったんですが誰にも共有できないかなしみ。

その後、6 月中旬くらいに面接がありました。
その面接は 45 分のコーディングインタビュー が 4 セットで、自分の場合はそのうち 2 回が日本語でした。

英語自体はとても苦手なのですが、英語のコーディングインタビュー自体はインターンの面接のときにも経験していたのでそこまでめっちゃ不安というわけでもなかったのですが、なんか手応えはそこまで良くなく、実際落ちました。

⑦社

⑦社は AtCoder でコンテストを開いており、そのコンテストの本選に進出したことで最終面接より前の面接をスキップできる権利を持っていたので、5 月初めくらいにエントリーしました。

その後、6 月末くらいに最終面接があり、落ちました。


就活をして思ったこととか、スタンスとか

どういう基準でエントリーする企業を選んだか

基本的には、AtCoder でコンテストを開いたことがある企業からエントリーする企業を選んでいました。
理由としては、探すのがめんどくさかったというのもあるんですが、コンテストを開くくらいだから競プロer の良い点悪い点を理解して、その上で競プロer に来てほしいと思っているのではないか、と思ったのが大きかったと思います。

何をして働きたいか

これが難しくて。だって、本音を言うと「働かずに金が欲しい」で、百歩譲って「競プロみたいな問題を解いてたら金が降ってきてほしい」。
じゃあ 200 歩譲るとどうなるかと言うと「やりたいことは特にない(コードが書ければなんでもいい)」になるんですが、実はこれは就活ではダメらしいです。えー、なんでさ。



でもエントリーの段階でフロントエンドエンジニア、バックエンドエンジニア、アプリ開発エンジニアとか分かれている会社もあるし、やりたいことが決まっている人は決まっているんだなぁ、となりました。

あとこれはわりとびっくりしたんですが、例えばアプリ開発をやりたいけどフロントエンドは死んでもやりたくない、みたいな人が存在したりするらしいです。
個人的にはそこらへんって本質というか根幹は同じだと思っているので、単純になんでそういうことになるんだろうなぁと思いました(これは普通に興味があるので、そういう方がいたら教えていただきたいです)。

結局面接では、まぁ競技プログラミング的なアルゴリズムとかが活かせる問題があれば嬉しいけど、べつにそういうのじゃなくても良いし、開発もインターンでやって面白かったし向いていると思ったのでそっちでも問題ない、みたいなことを言っていました。

企業を選ぶ基準、企業の順位

これも聞かれて困る質問でした。上で書いたように、やりたいことが明確でない/どんなことでもわりと楽しめてしまう ので、どうしても業務内容よりも環境(給料、周りの社員の優秀さ、等)を挙げることが多かったです。
でもこの回答は、おそらく面接官からの印象はそこまでよくなさそうな気がします。

就活のタイミングについて

これについてですが、まず自分の始めた時期は比較的遅めだったと思います。
自分が本格的に色々な企業にエントリーをし始めたのは 3 月中旬くらいからで、その頃にはすでに就活を終えてる同期もいました。

基本的にはいつ就活をしてもいいとは思うんですが、いくつか難しい点があって、

  • エントリー〆切(3 月末ごろにはもう締め切っているところが多い)
  • (今年の場合、)一部 6 月になってからじゃないと面接をしない企業があり、そうでない企業の選考が早く終わってしまうと長く待ってもらうことになる
  • 通年採用のところは、早いうちに選考を進めないと枠が絞られてしまう/埋まってしまうという噂がある(ほんまか???)

あたりを気をつけるべきかもしれません。

面接について

率直な感想としては、良い雰囲気で進んでいても落ちるときは落ちるなぁというやつでした。
終始和気藹々として 1 時間を過ごしたのに落とされると、普通に人間不信になります。
例えばコンテストとかだと明確な判定基準があってこれが解けなかったからこの順位、とかがあると思うんですが、面接で落ちてメールでいつもの定型文を受け取っても、どこが悪かったか、どうしたらよかったか、今後どうすればいいかなんてわかりません。

あとは、やはり短い時間で自分の優秀さをアピールしなければならないので、練習とまではいかなくても話す内容の準備くらいはしていくべきだと思います。
個人的には、たった 1 時間の面接による印象よりも競技プログラミングのレーティングの方がどちらかと言うと頭の良さとか優秀さとかに対する相関があると思っているのですが、さすがにそんなものはただの持論で、実際には競技プログラミングのレーティングにはそんな影響力はないので、やはり口の上手さは重要になると思います。

あとはまぁこれですね。

あとこれも。

結局競技プログラミングだけで就活はできるのか

端的に言うと、受ける会社・受ける職種に依ると思います(それはそうすぎる)。

例えば、面接が全てコーディングインタビューのみの会社だったら、基本的には行けると思います(え、落ちましたが……)。

そうではない場合、例えば機械学習エンジニアを受けるのだとしたら研究分野が機械学習であったり、そうでなくともしっかり触ったことがあることが望ましいだろうし(最近は機械学習をやっている学生も多いため)、フロントエンドエンジニアを受けるのだとしたら少しくらい触ったことがあることが望ましそうです。

それ以外の、特に細かい分かれ方をしていない職種については扱いが少し難しいですが、それに関しては会話が合計で 1 時間持つようなネタがあればまぁ大丈夫だと思います。
これは知見なんですが、競技プログラミングでの成果ってそこまで話を広げられるものでもないという話があります(これはトークスキルに依存するかもしれません)。
なので、みんな研究はやっているだろうから基本はその話で、もしあまり研究で成果がないなら何か他に話せるネタ、アピールできる何かが必要なのかな、と感じました。


就職先について

結局 ③社 と ⑤社 の 2 社から内定をいただき、③社の方に入ることにしました。以下に理由を挙げていきます。

職種について

まずこの 2 社ではそもそも職種が違います。⑤社は web 系企業ですが、③社はいわゆる ITコンサルと呼ばれるところになります。
感覚としてどう違うかというと、前者は何万何億というユーザーに対してサービスを提供、およびそのサービスを改善をしていくのに対し、後者は一人一人(一団体一団体)の抱えている課題を一つずつ整理し解決する、というイメージです(これは個人的なもので、間違っていても責任を負いません(でも間違っていたらこっそり教えてください))。

このどちらが好きか、というのは本当に人それぞれだと思うのですが、個人的には後者の方が好きだと感じました。
あまり関係ないですが、TL にバグった AtCoder の提出が流れてくるとつい見に行って解決したくなっちゃうのと似ているかもしれません。いや、似てないかもな。

業務内容について

最適化をお仕事にできる、というのもやはり魅力の一つではあります。最適化いいよね。

もちろんそれだけではなくて、やはり顧客の抱えている課題を紐解いてちゃんとクリティカルな問題に切り分けていく、というような作業がわりと好きだし向いているなぁと思ったところも大きいです。

まとめ

短くも険しい就活が終わり、つらいことも多々あったけどでも、結局自分で納得のできる結果を得られたかなという気持ちがあります(いま、落ちた 5 社全てからやっぱり内定出すよ、って言われても、やっぱり③社を選ぶような気がします)。

まぁでも苦労したのは事実で、このレートでこの前例を作ってしまったことが少し申し訳ない気持ちもあります。


しうかつが終わったので各位と飲みたい気持ちがあります。連絡をください。雛鶴あいにはならないけど。


今度は、「レッドコーダーなので就活で俺TUEEEEした件」という記事が投稿されるのを楽しみに待っています。