2021-02-22

AtCoder ABC074 D - Restoring Road Network

問題

解法

判定すべき問いは「表が本当に最短距離を示しているか？」です。
これは「ワーシャルフロイド法」を用いると、判定できます。
また、問いがYesの場合には、必要な道路の総距離（の最小値）を求めます。

ワーシャルフロイド法って？

ワーシャルフロイド法は、点i - j 間の最短距離を求めるアルゴリズムです。
実際には、「点i → j と行くよりも、点i → k → j と行くほうが早くないか？」という問いを、
kに全ての点を代入し判定します（早い場合は早い方の距離に更新します）。
今回の問題では、入力の表に対してワーシャルフロイド法を行い、
元の表と変化がない場合はYes（ちゃんと最短距離を示していた）、ある場合はNoとなります。

必要な道路の総距離は？

全ての点同士に道路を設ければ、表の通りになりますが、求める最小値にはなりません。
なくても構わない道路とはどんなものでしょうか？
不要な道路とは、点i - j 直通の道路がなくても表の距離で行ける道路です。
（逆に、必要な道路とは、その道路がないと最短距離が変わってしまう道路です。）

（「入力例 3」の点1 - 2間の道路は、点1 → 4 → 2 の道路で同じ距離で行けるので不要です。）
（「入力例 3」の点1 - 3間の道路は、どう迂回しようが直接1 → 3 に行くより遅くなるので必要です。）

これを全ての2点間の道路に対して判定して、必要な道路の距離の和を求めます。

実装

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define print(x) cout << x << endl

bool f(vvi v) {
    vvi tmp = v;
    int n = v[0].size();
    
    rep(k, n)rep(i, n)rep(j, n) {  // 経由点kは必ず一番外側のループ
        v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
    }
    
    bool ok = true;
    rep(i, n)rep(j, n) {
        if (v[i][j] != tmp[i][j]) ok = false;
    }
    return ok;
}

ll f2(vvi v) {
    ll res = 0;
    int n = v[0].size();
    rep(i, n)rep(j, n) {
        bool nokosu = true;
        rep(k, n) {
            if (k == i || k == j) continue;
            if (v[i][j] >= v[i][k] + v[k][j]) nokosu = false;
        }
        if (nokosu) res += v[i][j];
    }
    
    return res;
}

int main(void){
    int n; cin >> n;
    vvi v(n, vi(n));
    rep(i, n)rep(j, n) cin >> v[i][j];
    
    bool ok = f(v);
    if (ok) {
        // 点i-jと点j-iを二重に判定してるので割る2
        ll res = f2(v) / 2;
        print(res);
    } else {
        print(-1);
    }
}

2020-11-16

AtCoder ABC183 D - Water Heater

問題

atcoder.jp

解法

答えは「どの時刻においても、「使用量≦上限」であるか？」です。
各時刻の使用量は「imos法」を用いると、高速に求められます。

imos法って？

imos法は、例えば「時刻iにおけるバスの乗客数」を求めるのに使われます。
「時刻A～Bの間、C人組がバスに乗る」というデータがいくつも与えられる場合、
「時刻AでC人増える(array[A] += C)」「時刻B+1でC人減る(array[B+1] -= C)」という形で配列に記録します。
全て記録した後に配列の累積和を取ると、array[i]には時刻iの乗客数が格納されています。
（時刻1, 2, 3, ... と累積和を求めていくことは、「ある時刻でx人乗り/ある時刻でy人降り…」を実際にシミュレーションしているのと同じことをしています。）

実装

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        
        int[] start = new int[n];
        int[] end = new int[n];
        long[] p = new long[n];
        for(int i = 0; i < n; i++) {
            start[i] = sc.nextInt();
            end[i] = sc.nextInt();
            p[i] = sc.nextLong();
        }
        
        // sum[i]: 時刻iの使用量
        long[] sum = new long[200005];
        for (int i = 0; i < n; i++) {
            // 時刻start[i]で使用量がp[i]増える
            // 時刻end[i]で使用量がp[i]減る
            sum[start[i]] += p[i];
            sum[end[i]] -= p[i];
        }
        for (int i = 0; i < 200005 - 1; i++) {
            sum[i + 1] += sum[i];
        }
        
        boolean ok = true;
        for (int i = 0; i < 200005; i++) {
            if (sum[i] > w) ok = false;
        }
        
        if (ok) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}