TopCoder SRM610: AlbertoTheAviator

本番では、嘘解法っぽい後ろからの貪欲の全探索で通したけど、合っている証明ができなかった。

想定解法は、ミッションをRefuelの大きい順に順番を固定してから、動的計画法が適用する、というものだった。

ミッションをRefuel の大きい順に並び替れば上手くいくというのはあまり直感的ではないため、簡単に思いつくのは大変そう。

こういうある特定の順番に並び替えれば簡単になる系の問題は、A と B を比べて、どちらが手前に来てほしいかを定義する比較関数を定義してから、ソートするだけであまり深いことは考えずに実装できるので楽できると思う。

今回の場合は、

• A → B の順でミッション遂行した場合の燃料の最小値
• B → A の順でミッション遂行した場合の燃料の最小値

を求めて、最小値が大きいほうになるように前後関係を決めれば良い。

この方法の欠点は、全順序関係が成立するかどうかが分からない点で結局これで解法が合っているかどうかの確信が得られないという点。逆にいうと全順序関係が成立するか分からなくても解法が書けるので、いざというときの手段には使えそうである。

public class AlbertoTheAviator {
    struct Mission {
        public int Duration, Refuel;
    }

    static public void UpdateMax<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) < 0) x = newValue; }

    public int MaximumFlights(int F, int[] duration, int[] refuel) {
        var missions = duration.Zip(refuel, (d, r) => new Mission() {
            Duration = d,
            Refuel = r
        }).ToArray();

        Array.Sort(missions, (m1, m2) => {
            // m1 -> m2 の順番でミッションを遂行したときに、燃料が一時的に取る最小値
            var min1 = Math.Min(-m1.Duration, -m1.Duration + m1.Refuel - m2.Duration);
            // m2 -> m1 の順番でミッションを遂行したときに、燃料が一時的に取る最小値
            var min2 = Math.Min(-m2.Duration, -m2.Duration + m2.Refuel - m1.Duration);
            // 最小値が大きい方を手前にする
            return min2.CompareTo(min1);
        });

        var dp = E.Repeat(-1 << 28, F + 1).ToArray();
        dp[F] = 0;

        foreach (var m in missions) {
            for (int i = 0; i <= F; i++) {
                if (i - m.Duration >= 0) {
                    UpdateMax(ref dp[i - m.Duration + m.Refuel], dp[i] + 1);
                }
            }
        }

        return dp.Cast<int>().Max();
    }
}

本番で通った謎解法

public int MaximumFlightsYour(int initF, int[] duration, int[] refuel) {
    int ans = 0;
    int n = duration.Length;
    for (int remainFuel = 0; remainFuel <= initF; remainFuel++) {
        int currentFuel = remainFuel;
        var used = new bool[n];
        bool yet = true;
        int sub = 0;
        while (yet) {
            yet = false;
            int minUp = 1 << 29, target = -1;
            for (int i = 0; i < n; i++) {
                if (used[i]) continue;
                if (currentFuel >= refuel[i]) {
                    if (minUp > duration[i] - refuel[i]) {
                        minUp = duration[i] - refuel[i];
                        target = i;
                    }
                }
            }
            if (target == -1) break;
            currentFuel += duration[target] - refuel[target];
            if (currentFuel > initF) break;
            used[target] = true;
            sub++;
            yet = true;
        }
        ans = Math.Max(ans, sub);
    }

    return ans;
}