SRM 719 Div1 - ei1333の日記

SRM718につづいてMedを解けた(ぎりぎりだけど.

oo- 379.00pts 48th.

Easy (250) LongMansionDiv1

TopCoder Statistics - Problem Archive

問題概要

縦 ${N(1 \le N \le 50)}$ , 横幅無限大の二次元グリッドがある.

${(sX, sY)}$ から隣接するマスを通って ${(gX, gY)}$ ${(0 \le sX, gX \le N - 1, 0 \le sY, gY \le 10^9)}$ に移動する.

行ごとに同じ障害物があって, ${i(0 \le i \le N - 1)}$ 行目のすべてのマスでは時間 ${t_i(1 \le t_i \le 1000)}$ 費やす必要がある. スタートとゴール地点でもその時間だけ費やす.

ゴールに移動するための最短時間を求めよ.

解法

横移動する行を全探索すると適当にやっても ${O(N^2)}$ で間に合う.

${i}$ 行目を横移動するとする. ${(sX, sY)}$ から縦移動して ${(i, sY)}$ , 横移動して ${(i, gY)}$ , 縦移動して ${(gX, gY)}$ みたいな感じになる.

ここで横移動する行が複数行あるとすると, 例えば以下のようなアになる.

  ***
 ** *
**  *
S   *
    G

下のような部分は

 **
**

例えば

***
*

や

  *
***

に置き換えることでコストを削減することができるため, はいになる(上の行がコストが低いときは上, 下の行がコストが低いときは下を使ったほうがコストが小さい).

ソース

世界一Easyを解くのが遅い.

SRM,普段のeasyがhardなせいでeasyな解法を思いついてしまったらinf回正当性を疑ってしまう
— 素数うし (@ei1333) 2017年8月15日

解法自体は一瞬でこれしかないやろみたいな感じになったけど, 制約が小さすぎてホンマか？って思ってたら時間が経過していた.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
 
class LongMansionDiv1 {
public:
  long long minimalTime(vector<int> t, int sX, int sY, int eX, int eY)
  {
    int64 ret = numeric_limits< int64 >::max();
 
    if(eY == sY) {
      ret = 0;
      for(int j = min(sX, eX); j <= max(sX, eX); j++) {
        ret += t[j];
      }
    } else {
      for(int i = 0; i < t.size(); i++) {
        int64 latte = 1LL * t[i] * (abs(eY - sY) - 1);
        int64 malta = 0;
        for(int j = min(i, sX); j <= max(i, sX); j++) {
          malta += t[j];
        }
        for(int j = min(i, eX); j <= max(i, eX); j++) {
          malta += t[j];
        }
        ret = min(ret, latte + malta);
      }
    }
    return(ret);
  }
};

Med (500) OwaskiAndTree

TopCoder Statistics - Problem Statement

問題概要

${N(1 \le N \le 1000)}$ 頂点の無向木があって, 頂点 ${i}$ のうれしさは ${pleasure_i(-10^6 \le pleasure_i \le 10^6)}$ である.

頂点 ${0}$ からはじめて, 辺を辿っていくつかの頂点を訪れる. 頂点には何度訪れても良いが, 最初に訪れた頂点に関しては現在の自分のうれしさに ${pleasure_i}$ が加算される.

また自分のうれしさが負になることはなく, そのような場合はうれしさが ${0}$ になる.

得られるうれしさの最大値を求めよ.

解法

木DP. なんかよくわからないけど葉からもにょると通った.

ちょっと考察するとうれしさが負にならないことを, うれしさをある頂点で ${1}$ 回だけ ${0}$ にできるに置き換えても答えは変わらないことがわかる.

具体的には ${2}$ つのDP配列を用意する.

頂点 ${i}$ を根とする部分木で

${dphigh[i]}$ := 部分木の頂点でうれしさを既に ${1}$ 回 ${0}$ にしているときの, うれしさの最大値
${dplow[i]}$ := 部分木の頂点でうれしさをまだ ${0}$ にしていないときの, うれしさの最大値

とするとまあやるだけになる.

ソース

なんか解法の雰囲気は分かっていたけど厳密なアレはわからず苦手だと思いながら適当に遊んでたら, 終了10秒前くらいにサンプルが通ってウケた.

あとから自分の解法を理解した.

#include <bits/stdc++.h>
 
using namespace std;
 
class OwaskiAndTree {
public:
  int maximalScore(vector<int> parent, vector<int> pleasure) {
    int N = parent.size() + 1;
    vector< int > g[1000];
    int dplow[1000] = {}, dphigh[1000] = {};
    for(int i = 1; i < N; i++) g[parent[i - 1]].push_back(i);
    for(int i = N - 1; i >= 0; i--) {     
      for(auto& to : g[i]) dphigh[i] += dphigh[to], dplow[i] += dplow[to];
      dphigh[i] = max(dphigh[i], dplow[i] + pleasure[i]);
      dplow[i] = max(0, dplow[i] + pleasure[i]);
    }
    return(dphigh[0]);
  }
};