AtCoder Regular Contest 073

珍しくいい成績だったので書く.

oo-o 26th.

2206 -> 2297(+89).

C - Sentou

arc073.contest.atcoder.jp

解法

${1}$ 個前に押した時間を保存しておく.

今押した時間との差が ${T}$ 以下なら, ${T}$ 秒湯を出して, それ以外ならその差の時間だけ湯を出したことにする.

ソース

この問題難しくないですか….

僕は難しいと思います.

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
 
int main()
{
  int N, T;
 
  cin >> N >> T;
 
  int64 ret = 0, prev = -1;
  for(int i = 0; i < N; i++) {
    int64 A;
    cin >> A;
    if(i > 0) {
      if(prev + T >= A) ret += A - prev;
      else ret += T;
    }
    prev = A;
  }
 
  cout << ret + T << endl;
}

D - Simple Knapsack

arc073.contest.atcoder.jp

解法

あとD問題は問題文にナップザックって書かれていので強い意志を持ってナップザックをしなかったら解けた
— うし (@ei1333) 2017年4月29日

重さ ${w_i}$ が ${4}$ 種類しかないことに着目.

同じ重さの物については, 価値の大きい方から使ったほうがいいので, 価値の降順にソートしておく.

で, ある重さの物を何個使うかを考えると, ${O(n^4)}$ の総当りができる. 間に合う. やったぜ.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
 
int main()
{
  int N, W;
  int w1;
  cin >> N >> W;
 
  vector< int > st[4];
  for(int i = 0; i < N; i++) {
    int w, v;
    cin >> w >> v;
    if(i == 0) w1 = w;
    st[w - w1].push_back(v);
  }
  for(int i = 0; i < 4; i++) {
    sort(begin(st[i]), end(st[i]));
    st[i].push_back(0);
    reverse(begin(st[i]), end(st[i]));
    for(int j = 1; j < st[i].size(); j++) {
      st[i][j] += st[i][j - 1];
    }
  }
 
  int ret = 0;
  for(int64 i = 0; i < st[0].size(); i++) {
    for(int64 j = 0; j < st[1].size(); j++) {
      for(int64 k = 0; k < st[2].size(); k++) {
        for(int64 l = 0; l < st[3].size(); l++) {
          int64 fact = w1 * i + (w1 + 1) * j + (w1 + 2) * k + (w1 + 3) * l;
          if(fact <= W) {
            ret = max(ret, st[0][i] + st[1][j] + st[2][k] + st[3][l]);
          }
        }
      }
    }
  }
 
  cout << ret << endl;
}

E - Ball Coloring

arc073.contest.atcoder.jp

解法

簡単のため任意の ${i}$ に対し ${x_i \le y_i}$ とする(swapすればいいよね.

本番ではえいやって考えると, 最小値のボールを赤色と固定したときに, 最大値のボールが赤色か青色かで場合分けできるなぁということまで詰めていた.

min が赤で max が青のときは, まあはい. 任意の ${i}$ に対し ${x_i}$ を赤色にして, ${y_i}$ を青色にすれば勝ち.

min が赤で max が赤のときは, 僕の頭だとまあはいとはならなくて悲しい気持ちになってた.

赤のボールについては考えなくて良いので, どのボールを青にすべきかを着目する.

これはすごく考えると, 値が小さいほうから尺取りみたいなことができる.

最初, 以下の図のように, すべてのボールについて ${x_i}$ を青にすると仮定するとこうなる.

f:id:ei1333:20170501000644p:plain

で着目する範囲を, 左から右にずらしていくと….

f:id:ei1333:20170501001419p:plain

これはなんか気合いさえあればできそうな気がするので, †上手く†実装する.

ソース

これ無理！ｗ

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
const int64 INF = 1LL << 60;
 
int main()
{
  int64 N, X[200000], Y[200000];
 
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
    if(X[i] > Y[i]) swap(X[i], Y[i]);
  }
 
  int64 ret = INF;
 
  int64 latte = INF, malta = -INF;
  for(int i = 0; i < N; i++) {
    latte = min(latte, X[i]);
    malta = max(malta, Y[i]);
  }
 
  int64 beet = latte, ukuku = malta;
  for(int i = 0; i < N; i++) {
    beet = max(beet, X[i]);
    ukuku = min(ukuku, Y[i]);
  }
 
  ret = min(ret, (beet - latte) * (malta - ukuku));
 
  vector< pair< int64, int64 > > vs;
  for(int i = 0; i < N; i++) {
    vs.emplace_back(X[i], Y[i]);
  }
  sort(begin(vs), end(vs));
 
  int64 front = vs.front().first, back = vs.back().first;
  int64 len = max(beet, malta) - min(ukuku, latte);
 
  latte = max(beet, malta);
  malta = vs.back().first;
 
  for(int i = 0; i < N; i++) {
    ret = min(ret, len * (malta - min(latte, i == N ? INF : vs[i].first)));
    if(i == N) break;
    latte = min(latte, vs[i].second);
    malta = max(malta, vs[i].second);
  }
  cout << ret << endl;
}

F - Many Moves

arc073.contest.atcoder.jp

解法

実家のような安心感. アディダスのセグ木（？）.

どちらかのコマは, 必ず直前のマスにあることを考えると, すべてが上手く行ってセグ木を使ったDPができる.

いい感じに遷移して, ${i}$ 番目を見ているとする.

${dp[i-1][y] := }$ ${i - 1}$ 番目まで見た時, コマが ${x_{i-1}}$ と ${y}$ にあるときのコストの最小値とする.

${x_{i - 1}}$ にあるコマを ${x_{i}}$ に動かすか ${y}$ にあるコマを ${x_{i}}$ に動かすかのどちらかの状態遷移となる.

${x_{i - 1}}$ にあるコマを ${x_{i}}$ に動かす時は ${y}$ にあるコマ位置はそのままなので ${dp[i][y] = dp[i-1][y]+|x_{i-1}-x_{i}| }$ .
${y}$ にあるコマを ${x_{i}}$ に動かす時は, ${x_{i - 1}}$ のコマ位置はそのままなので ${dp[i][x_{i-1}] = \min \{dp[i-1][y]+|y-x_{i}|\} }$ .

1 の場合は, ${dp[i-1][y]}$ 全体の ${y}$ に ${|x_{i - 1} - x_{i}|}$ が足されていると考えてよい.

2 の場合がちょっとアレ. ${dp[i][x_{i-1}] = \min \{dp[i-1][y]+|y-x_{i}|\} }$ を整理する.

${y \ge x_{i}}$ のとき ${dp[i][x_{i-1}] = \min \{dp[i-1][y]+y-x_{i}\} }$ .

${y \lt x_{i}}$ のとき ${dp[i][x_{i-1}] = \min \{dp[i-1][y]-y+x_{i}\} }$ .

${A[y]=dp[i-1][y]+y}$ , ${B[y]=dp[i-1][y]-y}$ とすると, それぞれ ${dp[i][x_{i-1}] = \min_{y \ge x_{i}} \{A[y]\} -x_{i} }$ , ${dp[i][x_{i-1}] = \min_{y \lt x_{i}} \{B[y]\} +x_{i} }$ .

これはどうみても, ${A[y]}$ と ${B[y]}$ についての区間の最小値.

1 の全体加算は, 加算値の和を別で持っておく. 2 は俗に言うRMQ+一点更新ができればよいので, セグ木でえいっ.

ソース

これ解けてよかった…

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
const int64 INF = 1LL << 58;
 
struct SegmentTree
{
  vector< int64 > seg;
  int sz;
 
  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, INF);
  }
 
  int64 rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (INF);
    if(a <= l && r <= b) return (seg[k]);
    return (min(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
                rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }
 
  int64 rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }
 
  void update(int k, int64 x)
  {
    k += sz - 1;
    seg[k] = min(seg[k], x);
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = min(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }
 
};
 
 
int main()
{
  int N, Q, A, B, X[200000];
  cin >> N >> Q >> A >> B;
  --A, --B;
  for(int i = 0; i < Q; i++) cin >> X[i], --X[i];
 
  SegmentTree tree1(N), tree2(N);
  tree1.update(B, abs(A - X[0]) + B);
  tree2.update(B, abs(A - X[0]) - B);
  tree1.update(A, abs(B - X[0]) + A);
  tree2.update(A, abs(B - X[0]) - A);
  int64 sum = 0;
  for(int i = 1; i < Q; i++) {
    int64 latte = tree1.rmq(X[i], N) - X[i] - abs(X[i - 1] - X[i]);
    int64 malta = tree2.rmq(0, X[i]) + X[i] - abs(X[i - 1] - X[i]);
    tree1.update(X[i - 1], min(latte, malta) + X[i - 1]);
    tree2.update(X[i - 1], min(latte, malta) - X[i - 1]);
    sum += abs(X[i - 1] - X[i]);
  }
  int64 ret = INF;
  for(int i = 0; i < N; i++) ret = min(ret, tree1.rmq(i, i + 1) - i);
  cout << ret + sum << endl;
}

ei1333の日記

ぺこい

AtCoder Regular Contest 073

C - Sentou

解法

ソース

D - Simple Knapsack

解法

ソース

E - Ball Coloring

解法

ソース

F - Many Moves

解法

ソース