NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ，自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので，過去にブックマークされた記事は URL が変わってしまっている可能性があります……．

競技プログラミングを始めて 4 年経った

Noise 競技プログラミング (雑記)

競プロを始めて今日でちょうど 4 年です。

4年というと中途半端ではありますが，大学編入学という環境が変わる直前に始めた趣味なので，同様に就職で環境が変わる直前である今，なんとなく感慨深いものがあります。そういうわけで，ブログに思い出を残しておこうと思いました。

念のため最初に書いておくと，他の方の色変記事のような，青コーダーになりたい方が参考にできるような内容はないです……。

４年間の Unique AC 数

コンテストサイト・コンテスト AC 数
AtCoder 1024AC
Codeforces 288AC
TopCoder SRM 60AC (コンテスト中 AC は 22)
yukicoder 64AC
Aizu Online Judge 106AC
Google Code Jam 6AC
PG BATTLE 4AC

合計 1552AC

4年間のレート変化

f:id:noimin:20200315231449p:plain
AtCoder
f:id:noimin:20200315231523p:plain
Codeforces
f:id:noimin:20200315231504p:plain
TopCoder SRM

思い出話

競プロを始める前 (高専時代)

高専時代，今は亡き CodeIQ でコードゴルフをして遊んでいた。アルゴリズム系の問題は全然解けなくて，コードゴルフも上位に入れるわけではなかったけど，それでも Prolog とか awk とか提出者数が少なそうな言語で shortest をとったりしてキャッキャしていた記憶がある。

この頃から競技プログラミングのことは知っていた。競技プログラミングをしている愛好会が高専にあったからなのだが，完全に他人事だと思っていた。高専時代の私にとっては，競技プログラミングは (ポジティブな意味で) "やべー奴がやるもん" だった。ただ，アルゴリズムやプログラミングへの理解が浅すぎることに対する焦りはうっすらとあった。

無色〜水色突入時代 (高専卒業〜B3)

高専卒業後，無事希望していた大学 (隠す意味がまるでないけど……) に3年次編入学をすることになった。ごくたまにゲームや作曲をするぐらいであまり趣味と言えるようなものがなかったので，何か新しい趣味が欲しいと思っていたところ，コードゴルフ関連で FF になっていた人たちが何やら AtCoder というサイトで競技プログラミングをしているらしい，ということを知った。まだ競技プログラミングに対して謎の恐怖感はあったが，思い切って AtCoder に登録してみた。

初めての AC はこれ。ABC 033 A - 暗証番号の Python 解のようだ。DIFFERENCE と DIFFERENT を間違えて WA している。しかもなぜか Python2。

ただ，競プロは思ったより怖くなさそうだということがわかった。初心者向けのコンテストであれば私にもわかる問題が用意されていたし，春休みはそれなりに楽しんで競プロをやった。ちなみにこの頃は ABC の B 問題も怪しいレベルで，主に ABC の A, B を埋めていた。言語は最初は Python だったが，割とすぐに C++ に乗り換えた記憶がある。

ちなみに，このころの AtCoder (2016年春ごろ) はまだレーティングというものが実装されていなかった。私の初期のレートがぐんぐん伸びているように見えるのは多分そのせい。

大学が始まると，思っていたよりも忙しく，競プロは少しおろそかになった。気が向いたときだけコンテストに出て，気が向いたときだけ復習した。「気が向いたとき」というのは週に1-2回くらいだった気がする。こんな感じでギリギリ水色になるところまでは行ったが，明らかにレーティングの傾斜がなだらかになってきていた。

本格的に競プロを趣味にし出したのは，DDCC 2016 の予選を突破したあたりからだったように思う。枠に対して競プロerが少なかったことや18卒枠だったこともあり，なんと100点問題と200点問題を解いただけで予選を突破してしまった。

このままでは本戦が座るだけになるのは明らかだったので，蟻本を読み始めた。初級編を読んだが，正直よく理解できなかった。写経したダイクストラ法を使って問題を解いてみたりしているうちにちょっとわかった気にはなった。気になっただけ。

このときに勉強していたアルゴリズムで名前のついているものは，二分累乗法，ユークリッドの互除法，最短路アルゴリズム，最小全域木アルゴリズムとかその辺りだったと思う。

精進の甲斐あってか (?) ，本選は0完太陽にはならずに済んだ。このときに初めて会った競プロerの中には，今でも FF だったりその後も関わりがあったりする人も結構いる。コンテストの帰りなどに一緒に遊びに行った人もいる。競プロer と精進について話したりする中で，かなりモチベーションが上がった。とうとう競プロをメイン趣味にし始めた私は，Codeforces と TopCoder にも参加し始めた。

水色停滞時代 (B3終盤〜B4)

モチベーションが上がったすぐ後ぐらいに，レーティングが停滞し始めた。のちにレーティング大暴落を経験したので今でこそ「それぐらいレーティングが低下することもたまにはあるよな〜」という感じだが，当時は慣れていなかったので結構しんどかった。

さらに，研究室に配属され，スランプを抜け出せないまま競プロに割ける時間が減ってしまったのも大打撃だった。しかし，研究室で足を引っ張ってばかりいる自分が唯一研究室の他の人にも勝てるものが競プロだったため，競プロへの逃避はやめられなかった。しばらくそうしていると，徐々に「人より研究をしっかりやることを諦め，研究室のタスクはほどほどにして競プロをやる」を覚えてしまい，それに伴ってレーティングも回復し始めた。

CODE THANKS FESTIVAL 2017 に出場することができたのもかなり救いだった。このときの行きの電車の中で，同期の sidebook37 と ICPC のチーム組みたいねみたいな話をした。詳しくは ICPC の参加記 に書いたので割愛。

コンテストとは関係ないが，CODE FESTIVAL 2017 の T シャツのデザインは今までもらったプログラミング系イベントの T シャツの中でいちばんのお気に入り。でかでかと書いてあるグラフが可愛いし部屋着のズボンとよく合うので……。

f:id:noimin:20200316001552j:plain

青色突入時代 (M1〜今)

このあたりから，Twitter やこのブログでもよく書いているような時代になる。

M1 の前期は「ICPC があるから……」と，研究室関連のタスクを犠牲にして競プロをやっていた。その甲斐あって，やっとこさ青コーダーになることができた。

しかし ICPC の参加記 に書いた通り，学内2位国内予選敗退。模擬国内予選の結果が良かっただけに人生の3本指に入りそうなくらい悔しかった。ちなみに学内1位だったのはこの年に結成された (間違ってたらごめんなさい) Aobayama_dropout。

ICPC という大学院生活の支えを失い，毎日に張り合いがなくなってしまったものの，レーティング的にはしばらく青をキープ。AtCoder Jobs を通して夏の短期インターンにも参加した。短期インターンで参加した企業は雰囲気が自分にマッチしている上に業務にも割と関心が持てる感じで，結構良かった。この企業はのちに私の内定先となり，writer デビューのきっかけともなる。

しかし年が明けた頃に落水。その後しばらく不安定なレーティングが続く。色々あって M2 になる頃には研究室にはほぼ行かなくなり (教員と相談の上だし，研究は多少の休止期間を経て最低限続けてました，一応……) ，競プロに使える時間が増えても下がる下がる。最低で Highest-272 まで下がった。落ち込みはしたがレーティングの下がり幅の割には楽観的な気持ちで，そのうち回復するだろうと思いながらマイペースに問題を解いていた。実際にレーティングが回復してきたのは秋頃の話なので，半年間ぐらいスランプだったことになる。

気づけば AtCoder の Rated 参加回数が 100 回を突破。Rated 参加回数が多いのは Rated が多いレーティング帯から抜け出せていないということなので誇らしいことではないが，なんだか達成感があった。

そして先月はついに初めて writer をやった。これもブログに記事を書いたばかりなので詳しくは割愛するが，自分の作った問題を面白いと言ってもらえるのは想像以上の喜びだった。夏の終わり〜秋頃にまた writer をやるつもりなので，今から問題のストックを貯めようと試みている。

オチというほどではないが，来月からフォルシア株式会社で web エンジニアとして働くことになっている。御社は競プロをやっていなかったら出会えなかったであろう企業なので，競プロがだいぶ人生に影響を及ぼしてきたなという感じだ。これから競プロとどういう付き合いになるのかも，自分がどこまで強くなれるのかもまったくわからないが，競プロは長く付き合っていきたい趣味だと思う。御社には競プロerがそれなりにいるし，社会人になって競プロからフェードアウト……みたいな感じにはならずに済むはず。

追記: この記事が本ブログ 100 記事めだったみたい。感慨深い。

パナソニックプログラミングコンテスト E - Three Substrings

競技プログラミング (問題解説)

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f

公式解説: 解説 pdf

問題概要

次の同じ方法で得られた長さ $2000$ 文字以内の文字列 $ a, b, c$ が与えられる。元の文字列 $s$ の長さとしてありえる最小値を求めよ。

  • 文字列 $s$ の空でない部分文字列を選ぶ。そのうちいくつかの文字を '?' に置き換える (0個，全部も可) 。

解法概要

与えられる文字列の長さは高々 2000 (これを $n_\mathit{max}$ とおく) 文字なので，1つの文字列 (たとえば $a$) の長さを固定してしまい，残りの2つについては固定した文字列から見た相対位置を $[-4000, 4000]$ の範囲で試すことができる ($[-2000, 2000]$ では足りていないことに注意)。

ただし，ある文字列 $a_1$ を他の文字列 $a_0$ に対して相対位置 $i$ で配置できるか？ の判定は時間計算量 $\mathcal{O}(min(|a_0|, |a_1|))$ なので，何にも考えずに実装しようとすると $\mathcal{O}(n_\mathit{max}^3)$ とかになってしまう。しかしこれは「ある文字列 $a_1$ を他の文字列 $a_0$ に対して相対位置 $i$ で配置できるか？ の判定」の結果を前計算しておくことで回避できる。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int INF = 1 << 30;
constexpr int BASE = 4000;

inline bool match(char c1, char c2) {
    return (c1 == c2 || c1 == '?' || c2 == '?');
}

// t を s から見て相対位置 i-BASE に置くことができるか
inline bool can_place(string &s, string &t, int ns, int nt, int i) {
    for(int j=0;j<nt;++j) {
        if(i+j-BASE < 0 || ns <= i+j-BASE) continue;
        if(!match(s[i+j-BASE], t[j])) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string a[3];
    cin >> a[0] >> a[1] >> a[2];
    int n[3] = {int(a[0].length()), int(a[1].length()), int(a[2].length())};

    // a (位置: BASE) に対する c の位置を i にしてよいか
    vector<bool> ac(2*BASE+1, true);
    for(int i=0;i<=2*BASE;++i) {
        ac[i] = can_place(a[0], a[2], n[0], n[2], i);
    }

    // b (位置: BASE) に対する c の位置を i にしてよいか
    vector<bool> bc(2*BASE+1, true);
    for(int i=0;i<=2*BASE;++i) {
        bc[i] = can_place(a[1], a[2], n[1], n[2], i);
    }

    int ans = INF;
    // a の位置は BASE に固定
    for(int bi=0;bi<=2*BASE;++bi) { // b の位置
        if(!can_place(a[0], a[1], n[0], n[1], bi)) continue;
        for(int ci=0;ci<=2*BASE;++ci) { // c の位置
            if(0 <= BASE+(ci-bi) && BASE+(ci-bi) <= 2*BASE && !bc[BASE+(ci-bi)]) continue;
            if(!ac[ci]) continue;
            ans = min(ans, max({BASE+n[0], bi+n[1], ci+n[2]}) - min({BASE, bi, ci}));
        }
    }

    cout << ans << endl;
}

所感

3つの要素があるときはそのうち1つの位置なり値なりを固定してしまうとうまくいくパターンが多い気がする。

それから，今回はwriter さんの思想がバチバチに表れたコンテストだったと思います (最近界隈に影響されて「バチバチに」という副詞をつい使ってしまいます) 。

AtCoder Beginner Contest 158 F - Removing Robots

競技プログラミング (問題解説)

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f

公式解説: 解説 pdf

問題概要

数直線上に $N$ 台のロボットが置かれている。$i$ 番目のロボットの初期位置は $X_i$ で，このロボットは起動させると $X_i+D_i$ まで移動する。移動中，$i$ 番目のロボットが $X_i \le X \lt X_i+D_i$ を満たす $X$ にいるとき，$ X_j = X$ を満たす他のロボット (このロボットを $j$ 番目のロボットとする) が存在すれば，$i$ 番目のロボットと $j$ 番目のロボットは接触したと考える。このとき，接触された $j$ 番目のロボットは起動し移動し始める。

高橋くんは次の操作を何回でも行うことができる。

  • 数直線上のロボットから1台のロボットを選び，起動させる。

移動中のロボットがいるときは高橋くんはロボットを起動させることはできず，移動を終えたロボットは数直線上から取り除かれるとする。

高橋くんが操作を終えた後に数直線上に残っているロボットの組み合わせとして考えられるものの通り数を $998244353$ で割った余りを答えよ。

解法概要

数直線上に残っているロボットの組み合わせを数えるのは取り除かれるロボットの組み合わせを数えるのと等しいので，以下，取り除かれるロボットの組み合わせを考える。

また，ロボットは $X_i$の値によってソート済みとする。

仮に，$0 \leq i \lt N$ のすべての $i$ について，$i$ 番目のロボットを起動させたときにロボット同士の接触で起動されるロボットが $j (\geq i)$ 番目までのロボットであるとわかっているとすると，次のような DP で求めるべき通り数を計算することができる。 ($i$ 番目のロボットとの接触とは限らない点に注意。$i$ 番目のロボットと接触して動き出した $j$ 番目のロボットが，$i$ 番目のロボットとは接触しない別の $k$ 番目のロボットと接触して $k$ 番目のロボットが起動する，といったことがありえる)

$\mathit{dp}_i := i$ 番目以降のロボットの残りかたの通り数

$\mathit{dp}_{n+1} = 1$ (いずれのロボットも起動させない場合に対応する)

$\mathit{dp}_i = \mathit{dp}_{i+1} + \sum_{j'=j}^{n+1} \mathit{dp}_{j'}$ (第 1 項は $i$ 番目のロボットを残す場合の $i+1$ 番目以降のロボットの残りかたの通り数，第 2 項は $i$ 番目のロボットを起動させる場合の通り数)

上式の第2項について，$i+1$ 番目のロボットから $j-1$ 番目のロボットについては，$i$ 番目のロボットを起動させると衝突によって強制的に起動されてしまうので足しこむ必要はない。

さて，肝心の「$i$ 番目のロボットを起動させたときにロボット同士の接触で起動されるロボットが $j (\geq i)$ 番目までのロボットである」の $j$ を求めるにはどのようにすればよいだろうか。

すぐに思いつくのが，「$X_j \geq X_i + D_i$ となる最初の index $j$ を二分探索で求め，そこから 1 を引いたもの」であるがこれは実は間違っている。例えば，

3
1 3
2 3
4 3

のような場合，1 番目のロボットに影響を受けるのは 2 番目のロボットと 3 番目のロボットの両方であるが，上のやり方だと 2 番目のみということになってしまう。

ではどうすればよいのかというと，これも DP っぽく計算できる。ソースコードに合わせて， $j$ ではなく $j+1$ にあたるもの (= $i$ 番目のロボットが起動されても影響を受けないロボットのうち座標が最も小さいものの index) を $\mathit{ti}_i$ に格納することを考える。

$ k = X_j \geq X_i + D_i$ となる最初の index とすると，

$\mathit{ti}_{n+1} = n+1$

$\mathit{ti}_i = \max_{i \lt i' \le tmp_k} \mathit{ti}_{i'}$

となる。第2式は，$i \lt i'$ となる$i'$ について $\mathit{ti}_{i'}$ が正しく求められているとすると，$i$ 番目のロボットと直接衝突するロボットについて，どこまで影響が及ぶのかの最大範囲を見ればよいということに対応する。最大値をとるときに毎回愚直にループを回していると処理全体で時間計算量が $O(N^2)$ に及んでしまうので，セグ木などを使って $O(n\log n)$ に抑えよう。

あとは求めた $\mathit{ti}_i$ を使って最初の DP を計算すればよい。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;

constexpr ll MOD = 998244353;

template<class T> class SegmentTree {
    public:
    typedef function<T(T, T)> F;
    size_t n;
    vector<T> data;
    T def;  // 単位元
    T initial_value;    // 初期値
    F update_func;  // 更新用関数
    F find_func;  //クエリ用関数

    SegmentTree(size_t _n, T def, T initial_value, F update_func, F find_func)
        : def(def), initial_value(initial_value), update_func(update_func), find_func(find_func) {
        n = 1;
        while(n < _n) n <<= 1;
        data = vector<T>(2*n-1, initial_value);
    }

    void update(size_t i, T x) {
        i += n-1;
        data[i] = update_func(data[i], x);
        while(i) {
            i = (i-1) / 2;
            data[i] = find_func(data[2*i+1], data[2*i+2]);
        }
    }

    T find(size_t s, size_t t, size_t k, size_t kl, size_t kr) {
        if(kr <= s || t <= kl) return initial_value;
        if(s <= kl && kr <= t) return data[k];
        size_t kc = (kl+kr) / 2;
        T vl = find(s, t, 2*k+1, kl, kc);
        T vr = find(s, t, 2*k+2, kc, kr);
        return find_func(vl, vr);
    }

    T find(size_t s, size_t t) {
        return find(s, t, 0, 0, n);
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Pll> robots(n);
    for(int i=0;i<n;++i) cin >> robots[i].first >> robots[i].second;
    sort(robots.begin(), robots.end());

    // 初めて影響が及ばなくなる idx
    SegmentTree<int> ti(
        n+1, 0, 0, 
        [](ll a, ll b) { return b; },
        [](ll a, ll b) { return max(a, b); }
    );
    ti.find(n, n);
    for(int si=n-1;si>=0;--si) {
        int tmp_ti = int(lower_bound(robots.begin()+si, robots.end(), Pll(robots[si].first + robots[si].second, -1LL)) - robots.begin());
        if(tmp_ti - 1 > si) tmp_ti = ti.find(si+1, tmp_ti);
        ti.update(si, tmp_ti);
    }

    // si 以降を見たとした場合の通り数
    vector<ll> dp(n+1, 0);
    dp[n] = 1;
    for(int si=n-1;si>=0;--si) {
        dp[si] = (dp[ti.find(si, si+1)] + dp[si+1]) % MOD;
    }

    cout << dp[0] << endl;
}

所感

セグ木使った DP の高速化すき

好きなタイプ以外の問題の解説もちゃんと書いた方が勉強になるんだけど，ついこういう問題の解説を優先してしまうね