AtCoder Regular Contest #025

放置してましたが久しぶりに書きます http://arc025.contest.atcoder.jp/

結果はoox-でしたがシステムのミスでノーゲームになったのでレーティングの変動はありません。悲しい。

A

大きい方を貪欲にとっていく。#include <algorithm>し忘れて一回CEする。(VisualStudioではコンパイルが通ってしまう)

int main(){
    vi a(7), b(7);
    rep(i, 7) cin >> a[i];
    rep(i, 7) cin >> b[i];
    int ans = 0;
    rep(i, 7) ans += max(a[i], b[i]);
    cout << ans << endl;
}

B

グリッドのマスに値があって累積和をとるやつ。典型問題らしい。白黒の市松模様になっていて、部分長方形の黒い部分の和と白い部分の和が等しくない場合は無視する。白黒別々に配列に持ってDPした。いつかのABCで書いた気がしたのでそれを探してきてコピペする。

公式解説の、白いところに-1を掛けると1回だけDPして和が0になる所を探すだけでOKというの賢いなあ。

int main(){
    int h, w;
    while (cin >> h >> w){
        vvi vb(h, vi(w));
        vvi vw(h, vi(w));
        rep(i, h)rep(j, w){
            if ((i + j) & 1) cin >> vw[i][j];
            else cin >> vb[i][j];
        }

        vvi dpw(h + 1, vi(w + 1));
        vvi dpb(h + 1, vi(w + 1));

        rep(i, h)rep(j, w){
            dpw[i + 1][j + 1] = dpw[i + 1][j] + dpw[i][j + 1] - dpw[i][j] + vw[i][j];
            dpb[i + 1][j + 1] = dpb[i + 1][j] + dpb[i][j + 1] - dpb[i][j] + vb[i][j];
        }

        int ans = 0;
        rep(i, h)rep(j, w){
            for (int tw = 1; tw <= h - i; ++tw) {
                for (int th = 1; th <= w - j; ++th) {
                    int P = tw*th;
                    int ww = dpw[i + tw][j + th] - dpw[i][j + th] - dpw[i + tw][j] + dpw[i][j];
                    int bb = dpb[i + tw][j + th] - dpb[i][j + th] - dpb[i + tw][j] + dpb[i][j];
                    if (bb == ww) ans = max(ans, P);

                }
            }
        }
        cout << ans << endl;
    }
}

C

どちらも最適に動くので最短経路をとる。また、無向グラフなので先にゴールを決めてスタートを地点を目指してもよい。まずゴールから他の全ての頂点までの最短路を求める。カメの速さをt, うさぎの速さをrとおく。カメの頂点の距離がd1のとき、カメはtt = d1/tの時間がかかる。これよりも多くの時間がかかる頂点の数を数える。ウサギの頂点の距離をd2とおくと、tr = d2/rの時間がかかる。tr < tt ⇔ d2 > r/t * d1となるような頂点の数を足せばいいが、二分探索か尺取じゃないとTLEする。

r<cの場合と答えがintに入らないこともあるのに気づかなくてWAしまくる。結局とけず…

int main(){
    int n, m, r, t;
    while (cin >> n >> m >> r >> t){
        Graph g(n);
        rep(i, m){
            int a, b, c;
            cin >> a >> b >> c;
            a--, b--;
            g[a].eb(a, b, c);
            g[b].eb(b, a, c);
        }
        ll ans = 0;
        rep(i, n){
            vi hoge;
            vi d(n);
            dijk(g, i, d, hoge); // グラフgでiから各頂点までの最短距離をdに入れる
            sort(all(d));
            rep(j, n)if (j){
                int tt = d[j];
                int tr = tt * r / t + 1;
                int k = lower_bound(all(d), tr) - d.begin();
                int c = -(k <= j);
                c += n - k;
                ans += c;
            }
        }
        cout << ans << endl;
    }
}