AtCoder ARC044 C

 問題リンク

 https://atcoder.jp/contests/arc044/tasks/arc044_c

 解説

 縦のビームが飛んでくるとき、高橋君は横に逃げます。このとき、縦に逃げる必要はないため、縦方向の座標は考えなくてよいです。横のビームも同様です。したがって、縦に逃げる回数と横に逃げる回数を独立に計算して足し合わせれば答えが求まります。

 縦のビームを考えましょう。各時刻にそれぞれの座標にいるときの移動回数の最小値を、配列\(move\)で管理します。最初、すべての座標について移動回数は\(0\)です。

\[\begin{array}{c|c|c|c|c|c|c|c} \text{座標} & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline \text{移動回数} & 0 & 0 & 0 & 0 & 0 & 0 & \ldots \end{array}\]

 ここで、ある時刻に座標\(2, 3, 4, 5\)にビームが通過したとします。次のようにして移動回数を更新してみましょう。

1. ビームが通過した直後に座標\(2, 3, 4, 5\)にいることはないため、これらの座標の移動回数を無限大とする
2. ビームが通過した座標に、その左右の位置から移動してくる。ビームが通過した座標を\(p\)として、\(move(p) = 1 + min(move(p - 1), move(p + 1))\)で更新する

 手順2を座標\(2, 3, 4, 5\)の順に左から行うと、更新後の移動回数は次のようになります。

\[\begin{array}{c|c|c|c|c|c|c|c} \text{座標} & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ \hline \text{移動回数} & 0 & 1 & 2 & 3 & 1 & 0 & \ldots \end{array}\]

 これは最適ではありません。座標\(4\)に移動するためには、座標\(6\)から左に2回移動するのが最適です。このように、ある座標の移動回数を右側の値を使って更新したいときは、右側の値が更新されてから行う必要があることがわかります。したがって手順2に代えて、次の方法で更新すればよいです。

• ビームが通過した座標を左から順番に見て、\(move(p) = min(move(p), move(p - 1) + 1)\)で更新する
• ビームが通過した座標を右から順番に見て、\(move(p) = min(move(p), move(p + 1) + 1)\)で更新する

 計算量は、更新がビームの本数のソートがボトルネックで\(O(Q \log Q)\)、最小値の取得が縦横それぞれ\(O(W)\)と\(O(H)\)であるため、全体で\(O(W + H + Q \log Q)\)となります。

 C#のソースコード

using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        string[] input = Next();

        var w = int.Parse(input[0]);

        var h = int.Parse(input[1]);

        var q = int.Parse(input[2]);

        var sizes = new[] { w, h };

        var tmax = 100000;

        var beams = new List<int>[2, tmax]; // beams[縦 or 横, 時間] = ビームが飛んでくる座標たち

        for (var i = 0; i < 2; i++) for (var j = 0; j < tmax; j++) beams[i, j] = new List<int>();

        for (var i = 0; i < q; i++)

        {

            input = Next();

            var t = int.Parse(input[0]) - 1;

            var d = int.Parse(input[1]);

            var x = int.Parse(input[2]) - 1;

            beams[d, t].Add(x);

        }

        var ans = 0;

        var infinity = int.MaxValue / 2;

        for (var direction = 0; direction < 2; direction++)

        {

            var size = sizes[direction]; // w or h

            var move = new int[size];

            for (var t = 0; t < tmax; t++) if (beams[direction, t].Count > 0)

            {

                var l = beams[direction, t];

                foreach (var p in l) move[p] = infinity;

                l.Sort();

                foreach (var p in l) if (p > 0) move[p] = Math.Min(move[p], move[p - 1] + 1);

                l.Reverse();

                foreach (var p in l) if (p + 1 < size) move[p] = Math.Min(move[p], move[p + 1] + 1);

            }

            ans += move.Min();

        }

        Console.WriteLine(ans >= infinity ? -1 : ans);

    }

    static string[] Next(char separator = ' ') => Console.ReadLine().Split(separator);

}