ARC 064に参加しました

arc064.contest.atcoder.jp

2,3分遅れてスタート→C問題で3回WA、その後AC→D考えてるうちに寝落ち→Eを提出するもWA
って感じでした。これはひどい。

C問題: 左側から順に求めていくのと右側から順に求めていくの2通りやりましたがその必要はなかったっぽい。非負整数分だけ減らせるのを見落としていました。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    int main()
    {
        long long int n, x;
        cin >> n >> x;
        long long int a[100001], b[100001];
        for(int i = 0; i < n; i++){
            cin >> a[i];
            b[i] = a[i];
        }
        long long int ans1 = 0, ans2 = 0;
        for(int i = 1; i < n; i++){
            if(a[i - 1] + a[i] > x){
                long long int tmp = a[i - 1] + a[i] - x;
                ans1 += tmp;
                if(a[i] < tmp){
                    a[i - 1] -= tmp - a[i];
                    a[i] = 0;
                } else {
                    a[i] -= tmp;
                }
            }
        }
        for(int i = n - 1; i > 0; i--){
            if(b[i] + b[i - 1] > x){
                long long int tmp = b[i - 1] + b[i] - x;
                ans2 += tmp;
                if(b[i - 1] < tmp){
                    b[i] -= tmp - b[i - 1];
                    b[i - 1] = 0;
                } else {
                    b[i - 1] -= tmp;
                }
            }
        }
        cout << min(ans1, ans2) << endl;
        return 0;
    }

E問題: ダイクストラやんけ！と思いつけたのはいいもののスタート地点からゴール地点まで直接行く道のことを考えていませんでした。解説読んで気づきました。かなしい。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <sstream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define mod 1000000007
     
    double kyori(double x1, double y1, double x2, double y2)
    {
        return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
    }
     
    int main()
    {
        double xs, ys, xt, yt;
        int n;
        cin >> xs >> ys >> xt >> yt >> n;
        double x[1001], y[1001], r[1001];
        for(int i = 0; i < n; i++){
            cin >> x[i] >> y[i] >> r[i];
        }
        double minkyori[1001];
        for(int i = 0; i < n; i++){
            minkyori[i] = -1.0;
        }
        priority_queue<pair<double, int> > qu;
        for(int i = 0; i < n; i++){
            qu.push(make_pair(-(max(0.0, kyori(xs, ys, x[i], y[i]) - r[i])), i));
        }
        while(!qu.empty()){
            int nowbaria = (qu.top()).second;
            double nowkyori = -(qu.top()).first;
            qu.pop();
            if(minkyori[nowbaria] != -1.0 && minkyori[nowbaria] < nowkyori) continue;
            minkyori[nowbaria] = nowkyori;
            for(int i = 0; i < n; i++){
                double tmp = max(0.0, kyori(x[nowbaria], y[nowbaria], x[i], y[i]) - (r[nowbaria] + r[i]));
                if(minkyori[i] == -1.0 || minkyori[i] > nowkyori + tmp){
                    minkyori[i] = nowkyori + tmp;
                    qu.push(make_pair(-nowkyori - tmp, i));
                }
            }
        }
        double ans = kyori(xs, ys, xt, yt);
        for(int i = 0; i < n; i++){
            ans = min(ans, minkyori[i] + max(0.0, kyori(xt, yt, x[i], y[i]) - r[i]));
        }
        printf("%.10f\n", ans);
        return 0;
    }