ABC-only 回です。

競プロ参戦記

この連載記事では、着手した問題の考察を自分なりに書いていきます。

問題の詳細はリンク先を参照してください。
前回: 競プロ参戦記 #39 Minimum Triangulation | エデュフォ 62 Div.2

AtCoder Beginner Contest 123

問題一覧: https://atcoder.jp/contests/abc123/tasks

A - Five Antennas

問題概要: 5本のアンテナが左から順に位置 A, B, C, D, E に配置されている。2本のアンテナは、間隔が K 以下なら直接通信できて、そうでなければできない。直接通信できないアンテナのペアがあるか判定せよ。

考察:

アンテナのペアは10通りなので、そのすべてについて調べてもいいですが、もっと簡単にできます。

例えば A と C の間の距離が K 以下なら、A と B の間も K 以下です。このことから、A と E の間の距離が K 以下なら A-B, A-C, .. すべてのペアについて距離が K 以下であることが分かります。

したがって、A-E 間の距離が K 以下か否かだけ判定すれば十分です。

    println!("{}", if E - A <= K { "Yay!" } else { ":(" });

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4850431

B - Five Dishes

問題概要: 5種類の料理があり、それぞれ提供時間が A, B, C, D, E である。注文ができるのは、時刻が10の倍数のときに限る。これらの料理を好きな順番で1つずつ注文するとき、最後の料理が提供される時刻を求めよ。

考察:

料理をどの順番で頼むかは 5! = 120 通りしかないので、全列挙すればよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4849640

C - Five Transportations

問題概要: 都市が6つあり、前から 1, 2, 3, 4, 5, 6 とする。隣接する2つの都市の間にはそれぞれ1つだけ交通機関があり、1分につき A, B, C, D, E 人を輸送する。はじめ、N 人が都市 1 にいる。全員が都市 6 に行くまで最短で何分かかるか求めよ。

考察:

都市 6 に最後に到着する1人 X 氏に注目します。この人は他の人に必ず席を譲るので、可能な限り遅い便に乗るとします。

はじめ都市 1 から 2 に行くには ceil(N / A) 分かかり、最後の便は ceil(N / A) 本目です。

次に、都市 2→3 の輸送を考えます。A ≤ B なら、1→2 に移動した人はみな次の1分で 2→3 と移動できます。

A > B なら、都市 1→2 に移動した人の一部だけが次の1分で 2→3 に移動できます。人々は次々に都市 2 に送られてくるため、「はじめから N 人全員が都市 2 にいる」と考えても同様です。

輸送は時刻 1 から始まるので、最後の便は時刻 1 + ceil(N / B) です。

都市 1→2 に最後に輸送された X 氏は、時刻 ceil(N / A) に都市 2 について、次に乗る便の出発時刻が 1 + ceil(N / B) なので、その差だけ待つことになります。

このように X 氏が乗る便がどの時刻に出発するかを計算して、待ち時間を加算していくことで解けます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4847281

    // 最後の便
    let mut s = 0;

    // 現在時刻
    let mut t = 0;

    for x in X {
        // 次の交通機関の最後の便が何本目か
        let y = (N + x - 1) / x;

        // 待ち時間を加算
        if y > s {
            t += y - s;
            s = y;
        }
        // 1分ずつずれていく
        t += 1;
    }
    t -= 1; // 最後の t += 1 をキャンセル

D - Cake 123

問題概要: 3種類のキャンドルがあり、キャンドル 1, 2, 3 のついたケーキがそれぞれ X, Y, Z 種類ある。キャンドル 1 のついた x 番目のケーキの美味しさを A[x] とする。同様にキャンドル 2 の y 番目が B[y]、キャンドル 3 の z 番目が C[z] の美味しさを持つ。キャンドル 1, 2, 3 のそれぞれからケーキの種類を1つ選ぶ組み合わせを、美味しさの和が高い順に並べたとき、上位 K 個の美味しさの和を列挙せよ。

考察:

ケーキの種類の組み合わせを決めたとき、キャンドル 1, 2, 3 がついたものの美味しさをそれぞれ a, b, c という変数で表すことにします。

組み合わせの総数 X * Y * Z が十分に小さければ、美味しさの和を実際に列挙してソートすることで解けます。実際には X * Y * Z は 10^9 のオーダーなので、すべて列挙するには時間もメモリも足りません。

組み合わせの数を減らすため、(b, c) だけ列挙することを考えます。つまり b + c の値からなる配列 W を作ってソートしておきます。a の値を決めたとき、a + b + c の値は降順に a + W[0], a + W[1], .. です。

はじめ、美味しさの最大値の候補は A[0] + W[0], A[1] + W[0], .. です。この中から最大値を探して出力します。仮に A[i] + W[0] が最大だったとしましょう。

A[i] + W[0] はもう列挙できませんが、A[i] のケーキを使う組み合わせの中で次に大きい美味しさの和は A[i] + W[1] です。また、A[i] のケーキを使わない組み合わせの美味しさの和の最大は A[x] + W[0] のままです。

したがって、2番目に大きい美味しさの和の候補は A[0] + W[0], A[1] + W[0], .., A[i] + W[1], .., A[i + 1] + W[0], .. です。以降も同様に W の添字を1つずつ増やしながら列挙していけば、常に「美味しさの和の最大値の候補」を X 個以下に保ったまま列挙を進めることができて、十分に高速です。

計算量は事前計算が O((Y + Z) log (Y + Z))、列挙部分が O(KX) 時間で、全体としては大きく見積もって O(KN log N) (N = X + Y + Z) です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc123/submissions/4858437

反省:

考察では省略しましたが、かなり迷走しつつなんとか辿り着いたという感じでした。

今回の教訓

A: 三角不等式
B: 全列挙で解ける問題は全列挙で解いていい
C: 複数のものを動かすとき、1つの動きに注目すると何か分かるかも