ABC に参加して、E完でした。

AtCoder Beginner Contest 143

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #65 Pure | ABC 142
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/abc143/tasks

A - Curtain

問題概要: 幅 A の窓に、幅 B のカーテンが2つ取り付けられている。窓のカーテンに覆われていない部分の幅を求めよ。

A: 考察

次のような状況です。

      A (窓)
    <------------------>
    <----><----><------>
      B     B    覆われていない部分

明らかに A - 2 B ですが、答えは 0 未満にならないので注意。

ここでの「答え x は 0 未満にならない」は「x が 0 より小さいなら 0 にする」や「x と 0 の大きい方」と言い換えられます。

   let mut x = A - 2 * B;
   if x < 0 { x = 0; }

    std::cmp::max(0, A - 2 * B)

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

B - TAKOYAKI FESTIVAL 2019

問題概要: N 個のたこ焼きがある。異なるたこ焼きを2つ選ぶすべての組み合わせについて、選ばれたたこ焼きのおいしさを x, y として積 x×y を計算し、それらの総和を求めよ。

B: 考察

異なる2個を選ぶ組み合わせを列挙するコードを書く問題のようです。

例えば 1~3 の3つの整数から異なる2つを選ぶ組み合わせは以下の3通りです。

1, 2
1, 3
2, 3

ここで 2, 2 は異なる2つを選んではいないのでダメですし、3, 1 を列挙すると 1, 3 と被ります。

ポイントはペア (x, y) を x < y に限って列挙することです。

    for x in 0..N {
        for y in x + 1..N { // y > x だけ列挙
            sum += D[x] * D[y];
        }
    }

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

C - Slimes

問題概要: 長さ N の文字列が与えられる。同じ文字が連続する区間を数えよ。

C: 考察

次のような文字列が与えられたとき、同じ文字が連続する区間の境界、すなわち異なる文字が隣接している部分に区切りを入れることを考えます。

    a a b b b b a a c a

    a a|b b b b|a a|c|a

この区切りの数 + 1 が答えになります。

実装では、区間の先頭の位置 l (< N) を変数に持つと分かりやすいと思います。r = l + 1 から始めて、S(l) = S(r) である限り r を増やしていくことで境界を発見できます。次に l = r として繰り返し、l = N になれば終わりです。

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

D - Triangles

問題概要: 互いに区別できる棒が N 本あり、i 番目の棒は長さ L(i) である。3本の棒を選んで三角形を作るとき、選べる棒の組み合わせの総数を求めよ。

制約: N≤2×10^3

三角形の成立条件:

辺の長さが a, b, c である三角形が存在するための条件は以下の3つがすべて成り立つこと:
- a < b + c
- b < c + a
- c < a + b

D: 考察

3重ループを回して条件を検査する方法では 10^9 ステップ程度の時間がかかり、間に合わなさそうです。(実は間に合うという噂も……)

2重ループなら間に合うので、三角形の短い辺2つ a, b を全列挙し、最長の辺 c として使える棒を高速に数える方針を考えます。

いま辺の長さ a ≤ b ≤ c を仮定しているので、あとは c < a + b だけ満たせば十分です。実際、以下のように残りの2条件がいえます。

a ≤ c + (c - a) < (a + b) + (c - a) = b + c
b ≤ c + (c - b) < (a + b) + (c - b) = c + a

b ≤ c < a + b となる c を数えればよいですが、棒をソートしておくと二分探索が使えて、十分高速に求まります。

    a=3, b=5 のケース

           a   b    a+b
           v   v     v
    L: 1 2 3 4 5 6 7 8 9
                 ^ ^
                 c c (2通り)

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

E - Travel by Car

問題概要: N 個の街があり、街同士を結ぶ道が M 本ある。これらの道を通って、燃料が最大 L まで入る車で、街から街へ移動することを考える。i 番目の道を通ると燃料が C(i) だけ減る。どの街でも「補給」を行い、車の燃料を L に戻すことができる。街のペア (s, t) が Q 個与えられる。燃料が満タンの状態で街 s を出発し、街 t まで移動するとき、補給回数の最小値を求めよ。

制約: N≤300, Q≤N(N-1)

備考: 燃料が 0 未満になるような移動はできない。燃料 0 で街に到着する移動は可。

E: 考察

余談ですが、グラフを表示するページを用意したので使ってみてください: AtGraph

制約を見ると O(N^3) が間に合うので、Floyd-Warshall 法の拡張で解けそうです。

パット見、以下のような手順でできそうに思えましたが、先に結論をいうとダメでした。メモ書き程度に書いておくと、まず dist(u, v) = (n, c) という表を定義します。これは燃料満タンで街 u を出発したら最小 n 回の補給で街 v に到着できて、残る燃料の最大値が c である、という状況を表しています。Floyd-Warshall 法では、街 w を経由する移動 (すなわち u → w → v) において dist(u, w) と dist(w, v) から dist(u, v) を構築できないといけませんが、この表からはできません。w に移動した状態で燃料が満タンではなくなり、dist(w, ?) が使えないからです。 (ここまでメモ)

解が満たす性質を考えることにしました。仮に解「街 s から t への補給回数が最小となる移動経路」が分かったとします。この経路上で補給を行った街とそうでない街に注目すると、補給を行った街同士は燃料 L 以下で行き来できる ことに気づきました。

そこで、問題により与えられるグラフ G (街を頂点、道を辺とするグラフ) とは別のグラフ H を考えます。これは街を頂点とし、燃料 L 以下で行き来できる街の間に辺があるようなグラフです。

このグラフ H 上の街 s から t へ最短経路は、補給回数が最小であるような移動に対応します。(仮に補給回数がもっと少ない経路があるなら、その道中で補給を行った街同士をつないだ経路が H 上における最短より短い経路になってしまい矛盾します。)

そういうわけで方針としては、上述のグラフ H を構築して、街のペアごとにグラフ H 上での最短経路問題を解けばOKです。

なお車の初期燃料は 0 で出発時に1回補給する、と考える方が分かりやすかったので、以下ではそうしています。

    例 (燃料容量 L=2, 道のコストはすべて 1)

    グラフG:
    経路   a ----> b ----> c ---> d ---> e ---> f
    燃料   2       1       2      1      2      1
    補給   ^               ^             ^        (街 a, c, e で補給)

    グラフH:
    経路   a ------------> c ----------> e ---> f

実装は、まずグラフ G (道を辺とするグラフ) における全点対の最短経路問題を Floyd-Warshall 法により解きます。街 u → v 間を補給なしで移動するときにかかる燃料量 dist(u, v) が分かります。

次にグラフ H を構築します。dist(u, v) ≤ L である頂点対 (u, v) の間に辺を引きます。

最後にグラフ H において街 s → t へ移動する最短経路の長さを調べます。グラフ H の各辺に重み 1 をつけて Floyd-Warshall 法を使っておくと、O(1) で最短経路長が求められます。(確かめてはいませんが、街のペアごとに幅優先探索を行う実装でも間に合うはずです。)

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