競技プログラミングで意識していること【AtCoder】【入青】

Posted at 2024-11-15

はじめに

先日、競技プログラミング3年目、AtCoder Beginner Contest 90回目の参加にして初めて全問正解、そしてパフォーマンス2400を叩き出し、再再再再入青を果たしました。

それを記念しまして、競技プログラミングにおいて、特に最近意識していること(に限らず、書きたいこと)を書いてみました。

マクロは使わず、スニペットで

競技プログラミングにおけるC++のコーディングでは、しばしばタイプ数を減らすためにマクロが使われます。

筆者自身も、大量のマクロを使い、テンプレートが100行以上になっていた時期がありましたが、現在は代わりにVScodeのスニペットを用いています。

例えば、代表的なマクロで、AtCoderのC++入門教材でも「ループの裏技」として紹介されているrepマクロですが……

#define rep(i, x, y) for (auto i = (x); i < (y); i++)
int main(){
  rep(i, 0, 10){
    cout << i << '\n';
  }
}

次のようなスニペットを作り、これを用いています。

"repeat":{
  "prefix": "rep",
  "body": "for (int ${1:i} = ${2:0}; ${1:i} < ${3:10}; ${1:i}++) "
}

他のマクロも全てスニペットに置き換えれば、基本的にほとんど同じタイプ数削減の効果があると思います。

ただし、(自分自身の)可読性の面や、突き詰めていった時のコーディング速度は(慣れれば)マクロに分があります。

実際にマクロを使うコーディングから使わないコーディングに移行してみて、1問当たり数秒から十数秒程度実装が遅くなったかな、という程度なので、First ACを狙うのでもなければマクロに凝る必要はないでしょう。

複数種類のクエリを処理する問題はswitch文で

基礎的な文法であるにもかかわらず、いまいち影が薄く、Pythonなどの言語では「if文で十分だ」と、存在すらしていないswitch文ですが……

複数種類のクエリを処理する問題は、Switch文を使うと気持ちよく書ける気がしてきませんか？

for(int i = 0; i < Q; i++){
  int q;
  cin >> q;
  switch(int x, y, z; q){
    case 1:
      cin >> x >> y;
      /* code */
      break;
    case 2:
      cin >> z;
      /* code */
      break;
  }
}

使う変数はswitch (初期化式; 条件式)という形で宣言できます。

infの値は1070000000

競技プログラミングで頻繁に必要となる「十分大きな値」 INF ですが、32bit整数¹の範囲では $107 \times 10^7$ を、64bit整数の範囲では $461 \times 10^{16}$ を用いています。

$10^9$ や $10^{18}$ だと、出力すべき答えが$10^9$ぴったりの場合、 INF と区別できないので不便ですし、 $2^{31}-1$ や $2^{63}-1$ のような、型の最大値を使うとオーバーフローが怖いです。

$107 \times 10^7$ は、$2$ 倍してもint型に収まり、下の桁に0が並ぶので、デバッグの際に有用です。

例えば、複数の INF を区別して調べるために INF $+$ i を出力したとき、i がいくつなのかが一目で分かります。

array型を積極的に使う

たとえば、2つの値がセットになっている要素をソートする時、よくpairクラスが用いられます。

vector<pair<int, int>> AB(N);
for(int i = 0; i < N; i++){
  cin >> AB[i].first;
}
for(int i = 0; i < N; i++){
  cin >> AB[i].second;
}
sort(AB.first(), AB.end());

ですが、「first」と「second」が長くて嬉しくないです。

それに、firstとsecondで同じ処理をするとき2回同じ事を書かないといけない²し、firstは5文字、secondは6文字と文字数が違うせいでコードがガタガタになりがち³なのも気に入りません。

こういう場合、array型を使います。固定長で宣言時に長さを指定すること以外、使い方はvectorとほとんど同じです。
(ただし、初期化の挙動が生配列に近く、未初期化での参照が安全ではないので、注意が必要です。)

vector<array<int, 2>> CD(N); // 感覚的には vector<vector<int>> CD(N, vector<int>(2)) と同じ
for(int i = 0; i < N; i++){
  cin >> CD[i][0];
}
for(int i = 0; i < N; i++){
  cin >> CD[i][1];
}
sort(CD.first(), CD.end()); // sortもデフォルトで辞書順に行われる

当然同じ処理を行いたい時はfor文を使えばいいし、コードの見通しも良くなりやすいです。

vector<pair<int, int>> AB(N);
vector<array<int, 2>> CD(N, {0, 0});
for(int i = 0; i < N; i++){
  AB[i].first /= hoge;
  AB[i].first += fuga;
  AB[i].first *= piyo;
  // pairだと同じ処理を2回書かないといけない
  AB[i].second /= hoge;
  AB[i].second += fuga;
  AB[i].second *= piyo;
  for(int j = 0; j < 2; j++){
    // for文でシンプルに
    CD[i][j] /= hoge;
    CD[i][j] += fuga;
    CD[i][j] *= piyo;
  }
}

要素数を3や4へ変更することになってもコードの修正が楽ですし、応用性も高いと思います。⁴

汎用的で便利な自作関数を使う

便利な自作関数その1 chmin, chmax

template<class T>
bool chmin(T &a, const T b){
  if(b < a){
    a = b;
    return true;
  }
  return false;
}

有名な関数ですね。比較をして、より小さい(大きい)場合に代入します。

if(chmin(A, B)){
 cout << A << "\n";
}

if(A < B){
  A = B;
  cout << A << "\n"; // こっちの方がわかりやすくないですか？
}

更新する場合にtrueを返すので、上のようにif文の条件式の部分に入れるような使い方もできます。

しかし、こういうことがしたい場合は普通に比較してif文のブロック内で更新する方がより分かりやすくなりがちなので、実際にこういう書き方をすることは稀かもしれません。

便利な自作関数その2 inrange

template<class T>
bool inr(const T &l, const T &x, const T &r){
  return (l <= x && x < r);
}

$x$ が半開区間 $[l,r)$ にあるかどうかを返す関数です。⁵
配列外参照を防ぐ時、特に上下左右に動いてグリッドを探索する問題などでよく使います。

引数の順番は不等号の向きが揃うようにしていますが、C++の標準ライブラリで似た機能を持つ clamp 関数は clamp(x, l, r)の順番なので注意が必要かもしれません。

便利な自作関数その3 safe_mod

long long safe_mod(long long x, long long m) {
  x %= m;
  if (x < 0) x += m;
  return x;
}

$x\bmod m$ を返すだけの関数です。AtCoder Library の math にも入っています。

"%"演算子でいいと思うかもしれませんが、Pythonなどと異なり、C++では負の数の剰余の計算結果が負(もしくは$0$)になるという仕様⁶なので、注意が必要です。

AtCoder Library の Modint をよく使うという人は必要ないかもしれません。

素晴らしい C++ 用の順序付き集合ライブラリを使う

NokonoKotlin(おこていゆ)さんの素晴らしい順序付き集合ライブラリです。

詳しい実用例は上の記事を参照してください。

何が素晴らしいかというと、setの要素アクセスや、範囲を指定してその総和を取得することが$O(\log N)$で出来ます。順序付き集合なので、挿入されたものは昇順に並びます。

特にABCの一部の問題では、このライブラリを使うことでかなり解きやすくなることがあります。上の記事で紹介されていない問題を2問紹介します。

ABC376-E (Difficulty 1063)

ABC306-E (Difficulty 1268)

こちらは水色Difficultyの問題ですが、特に有用です。

もし標準ライブラリやACLにこのライブラリと同じ機能が入っていたら、それだけでこれらの問題のDifficultyはかなり下がるんじゃないかな、と思うくらい効果的です。

これ以上難しい問題にも応用できることもあります。このデータ構造だけで解けるということは中々ないですが、思考と実装を節約できます。

おわりに

内容にミスや勘違い、その他改善案や感想があれば、よければご教示いただけると嬉しいです。

long longしか使わない、あるいは #define int long long してしまう人もいて、それはそれで合理的だと思いますが、使い分けることで可読性を上げたり、(稀ですが)short型を使うことで定数倍高速化したり、整数の型を意識するといいこともありそうです。 ↩
コピペして置き換えればよいのですが、後々の追加、変更、削除の手間が全て倍になり、バグの原因になりがちです。 ↩
単純に長いというのもありますが、個人的にはそれ以上に文字数の差がストレスになりがちです。マクロで first, second を F, S とか fi, se とかに置き換えているのをよく見ます。競プロマクロよく見るランキング、体感1位rep、2位all、3位入力関連、4位がpair関連でしょうか。 ↩
そこまでになると流石に構造体を定義した方が良いとは思いますが、ついtupleやarrayに頼ってしまいます。 ↩
Pythonでは演算子の結合を使って l <= x < r と書けます。羨ましい。 ↩
より厳密には A と (A / B) + (A % B) が等しくなる仕様らしいです。競プロ的には嬉しくないことの方が多そう ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up