yukicoder No.322 Geometry Dash

問題

No.322 Geometry Dash - yukicoder

解法

見た目が貪欲法で解けそうなので, 貪欲法で考えてみます。
貪欲法のアルゴリズムを考える際, よく p 番目に (Tp, Dp), q 番目に (Tq, Dq) を配置した際どのようにするとスコアが大きくなるか, ということを考えますが, このスコアを大きくする時の関係がよくあるような大小関係で書ける場合は, 特に q = p+1 を満たすものについてどのような関係が成り立つかのみ考えれば良いです(ソートする感じになるからですね)。

結論を言うと今回の関係は大小関係っぽく書けるので, q = p+1 を満たす p, q について比較すれば良いです。
ということで早速比較していきましょう。前提として, p より前の難所は, (繰り返ししない場合は) 合計で t だけ時間がかかるとします。
まず p 番目を (Tp, Dp) にして, q 番目を (Tq, Dq) にした場合にかかる時間は
(const1) + (t+Tp/2) * Dp + (t+Tp+Tq/2) * Dq + (const2) …(A)
次に p 番目を (Tq, Dq) にして, q 番目を (Tp, Dp) にした場合にかかる時間は
(const1) + (t+Tq/2) * Dq + (t+Tq+Tp/2) * Dp + (const2) …(B)
よって, 時間差は
(B) - (A) = (Dp*Tq - Dq*Tp)
となります。つまり, Dp/Tp > Dq/Tq のとき, p 番目は (Tp, Dp) にすべきということです。
これを適当にソートして答えを求めましょう。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<pair<pii, int> > P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i].first.first;
    }
    for (int i = 0; i < N; i++) {
        cin >> P[i].first.second;
    }
    for (int i = 0; i < N; i++) P[i].second = i;
    sort(P.begin(), P.end(), [](const pair<pii, int>& lhs, const pair<pii, int>& rhs) {return lhs.first.first*rhs.first.second > lhs.first.second*rhs.first.first;});
    for (int i = 0; i < N; i++) {
        cout << P[i].second+1 ;
        if (i < N-1) cout << " ";
    }
    cout << endl;
    return 0;
}