naoya_t@hatenablog

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

Google Code Jam 2017 - Round 2

aAb----- 23pt 1078位、で(去年の1112位よりはTシャツに近づいたものの)敗退。
明日のDistributed Code Jam Round 1も頑張ろう。
f:id:n4_t:20170514042734p:plain

A. Fresh Chocolate

https://code.google.com/codejam/contest/5314486/dashboard#s=p0

small (6pt; AC): P in (2,3)
large (10pt; AC): P in (2,3,4)

P=2の場合:人数が偶数(G[i]%2==0)の組を先に通す(毎回新品)。奇数の組(G[i]%2==1)を2つずつ対にして、うち1つは残り物に甘んじてもらう。あぶれた組があるなら新しいパッケージを1つ開封。
P=3の場合:各組の人数G[i]を3で割った余り(0,1,2)で3クラスタに分類。割り切れる組を一緒に通す(毎回新品)。1の組と2の組をできるだけ沢山対にして、どちらか1つに残り物に甘んじてもらう。対にならなかった組(1のみか2のみになる)を3つずつ束ねて、うち2つには残り物に甘んじてもらう。あぶれた組があるなら新しいパッケージを1つ開封。
P=4の場合:余り(0,1,2,3)で4クラスタに分類。割り切れる組は最初に通して新品開封。2の組は2つずつペアにして、1つずつが残り物。1,3をペアにして、1つずつが残り物。この時点で、2が0組または1組、1か3のどちらかが何組か。2があるなら1(または3)2つと束ねる。残りの1(または3)は4つずつ束ねる。余れば新しいパッケージを1つ開封。

P=2,P=3の場合について書いてとりあえずsmallを通し、P=4の場合を書き足してlargeを通した。
// smallで一回WA食らってるのはtypo("+="と書くべきところが1ヶ所"="になってた)。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) 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;
typedef pair<double,double> dd;

#include <cassert>

int solve(int N, int P, vector<int>& G) {
    map<int,int> m;
    rep(i,N) {
        int r = G[i] % P;
        m[r]++;
    }
    int ans = m[0];
    switch (P) {
        case 2:{
            ans += (m[1]+1)/2;
            break;
        }
        case 3:{
            int x = min(m[1], m[2]);
            ans += x;
            m[1] -= x; m[2] -= x;

            int y = m[1]+m[2];
            ans += (y+2)/3;

            break;
        }
        case 4:{
            ans += m[2]/2;
            m[2] %= 2;

            int x = min(m[1], m[3]);
            ans += x;
            m[1] -= x; m[3] -= x;

            int y = m[1]+m[3];
            if (m[2]) {
                if (y>=2) {
                    ans++; y-=2;
                    ans += (y+3)/4;
                } else {
                    ans++;
                }
            } else {
                ans += (y+3)/4;
            }
            break;
        }
    }
    return ans;
}

int main(){
    int _T; cin>>_T;
    rep(_t,_T){
        int N, P; cin >> N >> P;
        vector<int> G(N);
        rep(n,N) cin >> G[n];
        int ans = solve(N,P,G);
    answer:
        cout << "Case #" << (1+_t) << ": " << ans << endl;
    }
}

B. Roller Coaster Scheduling

https://code.google.com/codejam/contest/5314486/dashboard#s=p1

small (7pt; AC)
large (14pt; TLE)

source →[各客のチケット所持枚数]→ 客1人1人 →[1]→ 座席(チケット記載の席番号〜#1まで1つずつ)→[便数]→ sink
みたいなネットワークで、便数を1から(いや、客1人あたりの最大所持チケット枚数から)増やしていって最大流が総チケット枚数になる便数を求めたらいいか?
そこからpromotionなしの流量(チケット記載の席番号にだけ繋げばいい)を引いたらpromotionの必要数が分かる、はず。

でsmallは通ったけどlargeでTLE。(N=C=M=1000でかなりの時間を消費する…)
ちゃんと計算量を考えられてなかった。

// (略)
#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
  int w = capacity.size();

  vector<vector<int> > resid(w, vector<int>(w,0));
  for(int j=0; j<w-1; ++j){
    for(int k=j+1; k<w; ++k){
      resid[j][k] = capacity[j][k];
      resid[k][j] = 0;
    }
  }

  for (int total=0; ;++total) {
    bool another_way = false;
    vector<int> prev(w, infty);
    queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
    while (!q.empty()) {
      pair<int,int> p = q.front();
      int node = p.first, prev_node = p.second;
      q.pop();
      prev[node] = prev_node;
      if (node==t) { another_way = true; break; }
      rep(i,w) {
        if (resid[node][i] == 0) continue;
        if (prev[i] < infty) continue;
        q.push(pair<int,int>(i,node));
      }
    }

    if (!another_way) return total;
    for (int node=t; node!=s; node=prev[node]) {
      int prev_node = prev[node];
      resid[prev_node][node]--;
      resid[node][prev_node]++;
    }
  }
  return 0;
}

ii solve(int N,int C,int M,vector<int>& P,vector<int>& B) {
    map<int,int> cn;
    int maxn = 0;
    rep(i,M) {
        int c = B[i]; cn[c]++;
        maxn = max(maxn, cn[c]);
    }

    int w = 1 + C + N + 1;
    vector<vector<int> > cap(w, vector<int>(w, 0));
    rep(i, M) {
        int s = P[i], c = B[i];
        cap[0][c]++;
        for (int j=s; j>=1; --j)
            cap[c][C+j]++;
    }

    int m = maxn;
    while (true) {
        rep(i, N) {
            cap[C+1+i][w-1] = m;
        }
        int k = maximumFlow(cap, 0, w-1);
        if (k == M) break;
        ++m;
    }

    vector<vector<int> > cap1(w, vector<int>(w, 0));
    rep(i, M) {
        int s = P[i], c = B[i];
        cap1[0][c]++;
        cap1[c][C+s]++;
    }
    rep(i, N) {
        cap1[C+1+i][w-1] = m;
    }
    int k1 = maximumFlow(cap1, 0, w-1);


    return ii(m, M-k1);
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      int N,C,M; cin >> N >> C >> M;
      vector<int> P(M), B(M);
      rep(i,M){
          cin >> P[i] >> B[i];
      }
      ii ans = solve(N,C,M,P,B);
 answer:
    cout << "Case #" << (1+_t) << ": " << ans.first << " " << ans.second << endl;
  }
}

C. Beaming With Joy

https://code.google.com/codejam/contest/5314486/dashboard#s=p2

small (12pt)
large (17pt)

各光源の向けていい方向を調べて、縦横どちらにも向けられない光源があるならIMPOSSIBLE。
縦横どちらにも向けられる光源について、どちらを向ければいいか、フローで解けるかな、と思って書いてたけど間に合わず。

D. Shoot the Turrets

https://code.google.com/codejam/contest/5314486/dashboard#s=p3

small (13pt)
large (21pt)

開いてない