ABC005 C:おいしいたこ焼きの売り方

競技プログラミング

人生ではじめてgoto文を使ってしまった。

https://atcoder.jp/contests/abc005/tasks/abc005_3

先に来店した客から順に、Ai <= Bj <= Ai + T の範囲内にあるたこ焼きを素直にさばいていく。これを貪欲法と言ってしまっていいのかはわからないが。

signed main() {
    int t, n;
    cin >> t >> n;
    vector<int> as(n);
    rep(i, n) {
        cin >> as[i];
    }
    int m;
    cin >> m;
    vector<int> bs(m);
    rep(i, m) {
        cin >> bs[i];
    }
 
    int ai = 0, bi = 0;
    for (; bi < m; ai++, bi++) {
        if (ai >= n) goto NO;
        while (!(as[ai] <= bs[bi] && as[ai] + t >= bs[bi])) {
            ai++;
            if (ai >= n) goto NO;
        }
    }
    puts("yes");
    return 0;
 
NO:
    puts("no");
    return 0;
 
}

公式解説を見ると「二部グラフ」なるこれまたいかついアルゴリズムでも解ける模様。
おれにはまだまだ時期早々なテクニックだと思うので、頭の片隅に入れておこう。