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

naoya_t@hatenablog

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

Google Code Jam 2017 - Round 1A

問題AでつまづいてRound 1B進出を決めた。
(12pts, 4533rd place)

4/15(土) 10:00am JST〜(2時間半)

今回もスタバでスコーンを齧りながら待機。

特に考えもなしに問題

A. Alphabet Cake (8pts / 13pts)

同じ文字は1度しか現れない、という制約が頭の中で効いていなくて問題を難しくしていた。


(↑同志)
とはいえbrute force解すらまともに書けず、力不足を感じる。
45分ぐらいごりごりやった末に一旦離脱しBへ。

B. Ratatouille (12pts / 23pts)

こっちの方が楽だったか。
smallの制約を最初2x8と8x2で勘違いしてコードを書いていて時間をロス。
(smallをsubmitしようと思ってデータをダウンロードしてから気づいた)
2組できるかどうかを求めるのに二部グラフの最大マッチングを使ったけど多分要らない。
とりあえずsmallを通せて、largeに行かずAに戻って(そのまま死亡)。

#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 N, nP;
vector<int> R;
vector<vector<int> > P;
vector<dd> rng;
vector<int> Q;

#define infty 987654321
int maximum_match_count(vector<pair<int, int> >& possible_pairs) {
    int M = possible_pairs.size();
    if (M <= 1) return M;

    set<int> _part1, _part2;
    for (int i=0; i<M; ++i) {
        int p1 = possible_pairs[i].first, p2 = possible_pairs[i].second;
        _part1.insert(p1);
        _part2.insert(p2);

    }
    vector<int> part1(all(_part1)), part2(all(_part2));
    int P1 = part1.size(), P2 = part2.size();
    map<int, int> part1_map, part2_map;
    for (int i=0; i<P1; ++i) part1_map[part1[i]] = i;
    for (int i=0; i<P2; ++i) part2_map[part2[i]] = i;

    int w = 1 + P1 + P2 + 1;

    vector<vector<int> > capacity(w, vector<int>(w, 0));
    for (int i=0; i<P1; ++i) {
        capacity[0][1+i] = 1;
    }
    for (int i=0; i<M; ++i) {
        int p1 = part1_map[possible_pairs[i].first];
        int p2 = part2_map[possible_pairs[i].second];
        assert((0 <= p1 && p1 < P1) && (0 <= p2 && p2 < P2));

        capacity[1+p1][1+P1+p2] = 1;
    }
    for (int i=0; i<P2; ++i) {
        capacity[1+P1+i][1+P1+P2] = 1;
    }

    int s = 0, t = w-1;

    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;
        }
    }

    int total = 0;
    for (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;
}

bool possible(int r, int p) {
    int xmin = floor(p / (1.1*r));
    if (xmin == 0) ++xmin;
    int xmax = ceil(p / (.9*r));
    for (int x=xmin; x<=xmax; ++x) {
        double imin = .9*r*x, imax = 1.1*r*x;
        if (imin <= p && p <= imax) return true;
    }
    return false;
}

bool ok() {
    double p0 = Q[0];
    int xmin = floor(p0 / (1.1*R[0]));
    if (xmin == 0) ++xmin;
    int xmax = ceil(p0 / (.9*R[0]));

    for (int x=xmin; x<=xmax; ++x) {
        int cnt = 0;
        for (int i=0; i<N; ++i) {
            double imin = .9*R[i]*x, imax = 1.1*R[i]*x;

            if (imin <= Q[i] && Q[i] <= imax) ++cnt;
            else break;
        }
        if (cnt == N) return true;
    }
    return false;
}

int solve_s(){
    if (N > 2 || nP > 8) return -1;

    if (N == 1) {
        int cnt = 0;
        rep(j, nP) {
            if (possible(R[0], P[0][j])) ++cnt;
        }
        return cnt;
    }

    Q.resize(2);
    vector<vector<bool> > u(nP, vector<bool>(nP, false));

    vector<ii> possible_pairs;
    rep(i,nP) rep(j,nP) {
        Q[0] = P[0][i]; Q[1] = P[1][j];
        if (ok()) possible_pairs.push_back(ii(i, j));
    }
    return maximum_match_count(possible_pairs);
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      cin >> N >> nP;
      R.resize(N);
      P.assign(N, vector<int>(nP));

      rep(n,N) cin >> R[n];
      rep(n,N) {
          rep(p,nP) {
              cin >> P[n][p];
          }
          sort(all(P[n]));
      }

      int ans = solve_s();

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

C. Play the Dragon (19pts / 25pts)

開いてない

【終了後】

C.

priority queueにぶち込んでいく方式のシミュレーションが正しい答えを出してくれない。何か間違ってる。

B.

後で何個組にするかを小さい方から順に試してgreedyに取っていけばいいのでは、と思って書いたやつでsmall/large投げたらlargeがWA。doubleで演算した誤差か。これ10倍して整数演算にしたらと思って試したらオーバーフローした。(long longでないと11x1000000x1000000は扱えない!)

#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;

// #define DEBUG 1

#ifdef DEBUG
#include "cout11.h"
#define NDEBUG
#endif
#include <cassert>

int N, nP;
vector<int> R;
vector<vector<int> > P;

int solve(){
    int ans = 0;

    vector<ll> rmin(N), rmax(N);
    rep(n, N) {
        rmin[n] = 9LL * R[n];
        rmax[n] = 11LL * R[n];
    }

    vector<int> px(N), jx(N);
    for (int x=1; x<=1000000; ++x) {
        do {
            int c = 0;
            rep(n, N) {
                jx[n] = px[n] = -1;
                if (P[n].size() > 0) ++c;
            }
            if (c < N) return ans;

            rep(n, N) {
                int rn = R[n];
                ll xmin = rmin[n]*x, xmax = rmax[n]*x;
                int nPn = P[n].size();
                assert(nPn <= nP);

                px[n] = -1;
                rep(i, nPn) {
                    ll pni = 10LL * P[n][i];
                    if (xmin <= pni && pni <= xmax) {
                        px[n] = i;
                        break;
                    }
                }
                if (px[n] == -1) goto next;
            }
            ++ans;
            rep(n, N) {

                P[n].erase(P[n].begin(), P[n].begin()+px[n]+1);
            }
        } while (true);
    next:
        ;
    }
    return ans;
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      cin >> N >> nP;
      R.resize(N);
      P.assign(N, vector<int>(nP));

      rep(n,N) cin >> R[n];
      rep(n,N) {
          rep(p,nP) {
              cin >> P[n][p];
          }
          sort(all(P[n]));
      }

      int ans = solve();

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

解説を読んでも(え、それで行けるの?例外あるんじゃない?)と疑心暗鬼だったのは、同じ文字が複数回現れる可能性をずっと考えてていたから。
なんだ、1行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())

#ifdef DEBUG
# include "cout11.h"
# define NDEBUG
#endif
#include <cassert>

typedef pair<int,int> ii;


int main(){
    int _T; cin>>_T;
    rep(_t,_T){
        cout << "Case #" << (1+_t) << ": " << endl;

        int R, C; cin >> R >> C;
        vector<vector<char> > M(R, vector<char>(C, '?'));

        rep(r, R) {
            string s; cin >> s;

            rep(c, C) {
                char ch = s[c];
                M[r][c] = ch;
            }
        }

        rep(r, R) {
            char last = '?';
            int first_c = C;
            rep(c, C) {
                if (M[r][c] == '?') {
                    M[r][c] = last;
                } else {
                    last = M[r][c];
                    first_c = min(first_c, c);
                }
            }
            if (last == '?') {
                ;
            } else {
                if (M[r][0] == '?') {
                    char first = M[r][first_c];
                    rep(c, first_c) {
                        M[r][c] = first;
                    }
                }
            }
        }

        int first_r = R;
        rep(r, R) {
            if (M[r][0] != '?') { first_r = r; break; }
        }
        assert(first_r < R);
        if (first_r != 0) {
            rep(r, first_r) {
                M[r].assign(all(M[first_r]));
            }
        }
        for(int r=first_r+1; r<R; ++r) {
            if (M[r][0] == '?') {
                M[r].assign(all(M[r-1]));
            }
        }

        rep(r,R) {
            rep(c,C) {
                putchar(M[r][c]);
            }
            cout << endl;
        }
    }
}