AtCoder 初挑戦するので自分なりのテンプレをまとめておく

本日 21 時から AtCoder Beginner Contest 171 が開催されます。 というわけなので私も AtCoder に初挑戦したいと思います。

AtCoder 処女膜は決して復活しないので, せっかくなので記念としてここに今回の参加に持っていくテンプレを置いていくことにします。

実を言うと, 厳密には AtCoder 初参加ではありません。 が, アレは俺のなかではノーカンです。 “どなたでも参加できます” みたいな謳い文句が “無差別級” の意味だなんて気付けるかよ。 いまは “上級者向けのコンテンツです。 初級者・中級者の方には難しい問題が多く出題されますのでご注意ください。” っていう注意書きついてさらに難易度上がったらしいですね。 最近やっと 1200 以上のみが Rated になりました。 俺みたいな被害者がこれ以上生まれないことを願う。

競プロ自体処女なの?と聞かれるとそういうわけではないです。 高専時代に部活でパソコン甲子園とかに参加させられました。 当時は (というか今でも) アルゴリズムの知識とかほとんどなかったです。 使っていた言語も C でした。 厳密に言えば better C としての C++ だったかもしれません。 覚えてないです。 それと先日 yukicoder のコンテストに 1 度だけ挑戦しました。 とはいえこれら合わせても 5 回やったかやってないかって感じなので初心者であることには違いないと思います。

競プロも初心者, C++ も初心者 (こちらの記事によると明らかにそれ未満ですね。 入門者くらい?) ですのでマサカリいっぱい待ってます。

テンプレ

こんな感じのを持っていくつもりです。

# include <bits/stdc++.h>
# include <boost/range/irange.hpp>
# define RANGE_1(e) (boost::irange(0,(e)))
# define RANGE_2(s,e) (boost::irange((s),(e)))
# define RANGE_3(s,e,step) (boost::irange((s),(e),(step)))
# define RANGE_SELECTER(_1,_2,_3,SELECT,...) SELECT
# define range(...) RANGE_SELECTER(__VA_ARGS__, RANGE_3, RANGE_2, RANGE_1) (__VA_ARGS__)
# define guard(x) if(x);
# define CINS(x) for(auto&& __E__:(x))cin>>__E__
# define ALL(x) (x).begin(),(x).end()
# define RALL(x) (x).rbegin(),(x).rend()
# define CALL(x) (x).cbegin(),(x).cend()
# define MAX(x) *max_element(ALL(x))
# define MIN(x) *min_element(ALL(x))
# define BIT(n) (1LL<<(n))
# define MOD 1000000007

using namespace std;
using lint = long long;

// template<class T>class irange{private:struct I{T x;T operator*(){return x;}bool operator!=(I&lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;public:irange(T i,T n):i({i}),n({n}){}I&begin(){return i;}I&end(){return n;}};
// template<class T>class srange{private:struct I{T x,s;T operator*(){return x;}bool operator!=(I&lhs){if(s<(T)0)return x>lhs.x;return x<lhs.x;}void operator++(){x=x+s;}};I i,n;public:srange(T i,T n,T s):i({i,s}),n({n,s}){}I&begin(){return i;}I&end(){return n;}};
// template<class T>irange<T>range(T n){return irange(0,n);}template<class T>irange<T>range(T i,T n){return irange(i,n);}template<class T>srange<T>range(T i,T n,T s){return srange(i,n,s);}
template<class T>bool amax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool amin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

struct initialize{initialize(){cin.tie(nullptr);ios::sync_with_stdio(false);};}__ini__;

int main(){
    /* Code Area */
}

bits/stdc++.h

なんかもう定番ですね。 つよつよ標準ライブラリ群をひとまとめにしたという GCC が誇るやべーファイルです。

range

C++ の for 文はモダンな言語群からすると幾分か無骨でした。 多くのテンプレにはいわゆる rep マクロが採用されていたと思います。

それはそれでよいのですが, C++ にも範囲 for 文というモダンなやつが搭載されたということで, せっかくなのでそれを使えばいいじゃん, と思ってテンプレに乗せました。 Python のrangeいいですよね。 Q. あのー, 人質にされたタイプ数は? A. 知らんな。

boost というライブラリから利用しています。 AtCoder では boost が使えるようですが, 使えない競プロサイトの事も考え自前版も作ってあります (コメントアウトされてるやつです)。 実際, 先日参加したっていう yukicoder では利用できませんでした。 C++ 初心者がこんな複雑なもの書ける訳ありませんよね。 はい, こちらで紹介されているものをパクりました。

おおむね使えているのですがたまに型合ってねえぞ的なエラーが出て枕を濡らすことがあります。

guard

定義だけ見ると意味分からんですが, else 文と組み合わせて使うのが前提で, アーリーリターンの明示化が目的です。 こちらは Swift の guard 文から借用しました。

むこうと違ってアーリーリターンしなくてもエラーも何も起こりませんし, 競プロというメンテナンス性や再利用性が重要視されない環境でアーリーリターンを明示化することに大きな意味はなさそうですので, おおむね自己満足です。

CINS

コレクションのサイズ分だけ標準入力から引っ張ってきます。

N
A1 A2 ... AN

系の問題で効果を発揮します。

ALL 系

これも定番ですね。 sortとかのやつで開始地点と終了地点を引数に渡すときに, “いやどうせ全部だし” ってことが多いのでいちいち書かなくて済みます。 配列はこのメソッド持ってないので, 自由関数のbeginのほうを推奨されることもあるのですが, どうせ次のRALLは配列で使えないので配列自体使うのを控えることにしました。

RALLをsortに引き渡すと降順でソートしてくれます。 つよいです。 第 3 引数に比較ルールを渡すよりも直感的です。 つよいです。

CALLはstringに対して使うとcharのイテレータのように振る舞ってくれるみたいです。 こちらの問題で使いました。 当時はまだテンプレ入りしていないので直書きですが。 というかここで使ったのでテンプレに入れちゃいました。

MAX, MIN

コレクションの中の最大値, 最小値を返してくれます。 長すぎて覚えてらんないのでマクロにしているわけですな。

BIT

n番目のビットが立っている倍長整数をもらえます。 ビット演算ってワクワクしますよね。

MOD

ただし、答えがとても大きくなる可能性があるので、その量を 1000000007 で割ったあまりを求めよ。

こいついつも 1000000007 で割ったあまり求めてんな。 ということで定数マクロにしてあります。

modint という剰余類環の構造体を使うと演算を抽象化できてめちゃ便利そうなのですが, なんとなく今回は見送りました。 次はテンプレ入りさせるぞ。

std

名前空間毎回書いてられっかよ, ということで using 宣言します。 名前かぶると爆発します。

lint

倍長整数がロンリーロンリーみたいなクソ長い名前で嫌になってくるので型エイリアスです。 ll派も多いと思いますが, 発音するとこっちのほうが短いのでlint派です(?)。 そして今日も地下鉄に乗り, 無口な他人と街に置き去りね。 だからlong long切なくて壊れそうな夜にさえlong long君だけはオリジナルラブを貫いて。

amax, amin

現時点での最大値, 最小値を次々に更新していく処理を短く書けます。 さらに更新したかどうかを戻り値で示すことで一部アルゴリズムで有利になるらしいです。 これもこちらからパクりました。

initialize

構造体のコンストラクタとして記述し, グローバル変数として持たせることで main より前に実行してくれることを利用しています。 内容は標準入力の同期を切ったりして高速化させるやつ。 これも定番らしいです。

過去問を解いてみた

そういうわけなので, 早速こちらを使って ABC 170 の A, B, C 問 (激ウマギャグ) を解いてみました。 当然ネタバレなので注意。

A - Five Variables

題意要約: 1 から 5 までの整数のひとつだけが 0 に置き換えられている。 置き換えられた元の整数を答えよ。

int main() {
    int x; // 各々チェックするだけでいいので vector に入れるまでもない
    
    for (auto&& i : range(4)) {
        cin >> x;
        guard (x != 0) else {
            cout << i + 1 << endl; // 0 が見つかったならその時点で終了できる
            return 0;
        }
    }
    
    cout << 5 << endl; // 必ずひとつは置き換えられているので最初の 4 個になければ最後で確定できる
}

B - Crane and Turtle

題意要約: 鶴亀算を行う。 与えられた頭の数と足の数を満たす組み合わせが存在できるか答えよ。

int main() {
    int x, y; // 頭, 足
    cin >> x >> y;
    
    guard (!(y & 1)) else {
        cout << "No" << endl; // 足が奇数ならその時点で破綻している
        return 0;
    }
    
    int t = 2 * x - y / 2; // tsuru. 2t + 4(X - t) = Y の解
    
    string judge = t >= 0 && t <= x ? "Yes" : "No"; // 数学的解と現実(負の鶴や亀はいない)が剥離していなければ組み合わせが存在する
    cout << judge << endl;
}

C - Forbidden List

題意要約: 与えられた “禁止リスト” に含まれない整数のうちで, 与えられた整数に最も近い整数を答えよ。

int main() {
    int x, n; // 与えられる整数, 禁止リストの長さ
    cin >> x >> n;
    vector<int> p(n); // 禁止リスト
    CINS(p);
    
    for (auto&& i : range(n + 1)) { // ループの回数が多すぎる気もするが, 見つかった時点で終了するので多すぎる分には問題ないと判断 考える時間のほうが惜しい
        if (!count(ALL(p), x - i)) { // 要約では省いたが, 小さい方を優先する
            cout << x - i << endl;
            return 0;
        } else if (!count(ALL(p), x + i)) { // どうでもいいが count と cout 紛らわしいな
            cout << x + i << endl;
            return 0;
        }
    }
}

ごちそうさまでした。 それでは頑張ってきます。