読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2014 - Round 2


晩御飯たべて風邪薬のんで寝落ちして、気がつけば開始30分過ぎてました…orz

気を取り直して問題を開いて
...

A-small, A-large だけ通して、Bではまり。
「参加賞」Tシャツに手が届かず、今年の夏は終わりました。

来年またお会いしましょう。

A. Data Packing

  • 大きい順に詰めていったら良いでしょ
  • small/largeともにAC
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N, X; cin >> N >> X;
    vector<int> s(N);
    rep(n,N) cin >> s[n];
    sort(all(s)); reverse(all(s));

    priority_queue<int> pq;
    int cnt = 0;
    rep(i,N){
      int si = s[i];
      if (!pq.empty()) {
        int t = pq.top();
        if (si <= t) {
          pq.pop();
        } else {
          // waste
          pq.push(X - si);
          ++cnt;
        }
      } else {
        pq.push(X - si);
        ++cnt;
      }
    }

 answer:
    cout << "Case #" << (1+_t) << ": " << cnt << endl;
  }
}

B. Up and Down

  • とりあえず、数を小さい順に 0 ... N-1 にリナンバリングして
  • m, 即ち「一番大きな数(N-1)がどこに来るか」をN通り試すことを考えて
  • 一番大きな数を位置mに移動するコスト、mの左側を小さい順に並べるコスト、mの右側を大きい順に並べるコスト、の和の一番小さなmを探してた
  • でもこれでは駄目なんですね
  • 一番大きな数を移動する前にいくつかの数を並べ直すことで、これより低コストな解が出るからです
  • ここで嵌って試合終了でした
  • で。
  • 小さい順に、左端までの移動距離(=自分より大きな数が自分の左にいくつあるか)と右端までの移動距離(自分より大きな数が自分の右にいくつあるか)を比べて小さい方へ投げ飛ばしていくだけでした
  • こんな感じ:
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N;
    cin >> N; // 10,1000
    vector<int> a(N);
    rep(n,N) cin >> a[n];

    vector<int> a_(all(a)), b(N);
    sort(all(a_));
    map<int,int> m;
    rep(n,N) {
      m[a_[n]] = n;
    }

    vector<int> r(N);
    rep(n,N) {
      b[n] = m[a[n]];
      r[b[n]] = n;
    }

    int score = 0;
    rep(n,N){
      int at = r[n];
      int left = 0, right = 0;
      for (int i=at-1; i>=0; --i) {
        if (b[i] > n) ++left;
      }
      for (int i=at+1; i<N; ++i) {
        if (b[i] > n) ++right;
      }
      score += min(left, right);
    }

 answer:
    cout << "Case #" << (1+_t) << ": " << score << endl;
  }
}

C. Don't Break The Nile

  • 開いてない
  • ので以下は翌日解
  • 最大フローですね。制約をどう表現する?
  • W x H 個のノードがあって、隣接するノード間をキャパ1で繋げる?
  • 違うな
  • 各ノード(というかセル)のキャパが1 ということを言いたい
  • 各セルの「入口」「出口」をそれぞれノードとして表現して、入口から出口にキャパ1の弧を張って
  • 出口から、水が流れることのできる隣接セル(高々4つ)の入口へキャパ1の弧を張る
  • スタートノードを用意。ここから、最南端セル(W個)の「入口」ノードへキャパ1の弧を張る
  • ゴールノードを用意。最北端セル(W個)の「出口」ノードからゴールノードへキャパ1の弧を張る。
  • あとは最大フロー問題
  • LargeはHがでかすぎるから、マップの縦方向を圧縮するなどしないと間に合わないっしょ…多分、同じ感じの行は圧縮できると思う ←嘘
  • (略)
  • とりあえずPracticeのsmallでAC
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> II;

#define SRC(n) (1+(n)*2)
#define SINK(n) (1+(n)*2+1)

int maximumFlow(vector<vector<int> >& arc, int start, int goal) {
  int w = arc.size(), infty = w + 1;
  // residual networks
  vector<map<int,int> > resid(w, map<int,int>());
  rep(from, w){
    tr(it, arc[from]) {
      int to = *it;
      resid[from][to] = 1;
      resid[to][from] = 0;
    }
  }

  // find another way
  for (int total=0; ;++total) {
    bool another_way = false;
    vector<int> prev(w, infty);
    queue<II> q; q.push(II(start, -1));
    set<int> visited;
    while (!q.empty()) {
      int node, prev_node;
      tie(node, prev_node) = q.front();
      q.pop();

      prev[node] = prev_node;
      if (node == goal) { another_way = true; break; }

      tr(it,resid[node]){
        int i = it->first, r = it->second;
        if (r == 0) continue; // if (resid[node][i] == 0) continue;
        if (prev[i] < infty) continue;

        if (found(visited,i)) continue; // これやらないとループしてしまうね
        visited.insert(i);

        q.push(II(i,node));
      }
    }

    // no more ways
    if (!another_way) return total;
    for (int node=goal; node != start; node=prev[node]) {
      int prev_node = prev[node];
      resid[prev_node][node]--;
      resid[node][prev_node]++;
    }
  }

  return 0;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int W,H,B; // 3-100 3-500 0-1000 or 3-1000 3-1e8 0-1000
    cin >> W >> H >> B;
    // vector<int> X0(B), Y0(B), X1(B), Y1(B);
    vector<vector<bool> > c(H, vector<bool>(W, true)); // small
    rep(b,B){
      int x0,y0,x1,y1;
      cin >> x0 >> y0 >> x1 >> y1;

      // X0[b] = x0; Y0[b] = y0;
      // X1[b] = x1; Y1[b] = y1;

      for (int y=y0; y<=y1; ++y) {
        for (int x=x0; x<=x1; ++x) {
          c[y][x] = false;
        }
      }
    }

    int nodes = W * H; // 100 x 500 x (src/sink)
    int start = 0, goal = 1 + nodes*2;

    // arc[from] = [ to#0, to#1, ... ]
    vector<vector<int> > arc(1+nodes*2+1, vector<int>());
    rep(x,W){
      if (!c[0][x]) continue;

      int here = x;
      arc[start].pb(SRC(here));
    }

    rep(y,H){
      rep(x,W){
        if (!c[y][x]) continue;

        // src -> sink
        int here = W*y + x;
        arc[SRC(here)].pb(SINK(here));

        // down
        if (0 < y) {
          if (c[y-1][x]) {
            arc[SINK(here)].pb(SRC(here-W));
          }
        }

        // up
        if (y < H-1) {
          if (c[y+1][x]) {
            arc[SINK(here)].pb(SRC(here+W));
          }
        } else if (y == H-1) {
          arc[SINK(here)].pb(goal);
        }

        // left
        if (0 < x) {
          if (c[y][x-1]) {
            arc[SINK(here)].pb(SRC(here-1));
          }
        }

        // right
        if (x < W-1) {
          if (c[y][x+1]) {
            arc[SINK(here)].pb(SRC(here+1));
          }
        }

      }
    }

    int ans = maximumFlow(arc, start, goal);

 answer:
    cout << "Case #" << (1+_t) << ": " << ans << endl;
  }
}

D. Trie Sharding

  • 開いてない