naoya_t@hatenablog

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

Google Code Jam 2018 - Round 1A

出ました
aX--cX で3036位
Round 1B出場権を獲得
f:id:n4_t:20180415043027p:plain

終了直前はこれ
f:id:n4_t:20180415043054p:plain
今回は50点がボーダーだった

Practice roomが無いので検証ができず、振り返りをやる気が削がれる
お友達検索機能もないし、どうしてcodejamは劣化リニューアルしたんだ?

【4/22】Practiceモードが追加されたので修正コードを投げてみました(→全てAC)

A

二次元いもすして
行の切れ目(水平線を引ける場所)を探して
列の切れ目(垂直線を引ける場所)を探して

Largeで落ちた
最後HとV取り違えてた><
編集距離1文字系WA

[Practice]

1文字直しただけでAC;そういうの一番精神にくる
(↑テストケースをいくつか自分で追加すれば解決できる問題)

#include <bits/stdc++.h>
using namespace std;

#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))


bool solve(int R, int C, int H, int V, vector<string>& M) {
    vector<vector<int>> imos(R+1, vector<int>(C+1, 0));
    rep(r,R) {
        vector<int> line_accum(C+1, 0);
        rep(c,C) {
            if (M[r][c] == '@') {
                line_accum[1+c] = line_accum[c] + 1;
            } else {
                line_accum[1+c] = line_accum[c];
            }
        }
        rep(c,C) {
            imos[1+r][1+c] = imos[r][1+c] + line_accum[1+c];
        }
    }
    int cut = (H+1) * (V+1);

    vector<int> acc(R+1, 0);
    rep(r, R) acc[1+r] = imos[1+r][C];
    int num = imos[R][C];
    if (num == 0) return true;
    if (num % cut) return false;
    int portion = num / cut;
    int w = V+1, h = H+1;
    int pw = portion * w;
    int prev = 0;
    vector<vector<int>> diffs;
    rep1(i, h){
        int to_find = pw * i;
        int ix = lower_bound(acc.begin()+prev+1, acc.end(), to_find) - acc.begin();
        if (ix == R+1) return false;
        if (acc[ix] != to_find) return false;
        vector<int> diff(1+C, 0);
        rep(c, 1+C){
            diff[c] = imos[ix][c] - imos[prev][c];
        }
        diffs.pb(diff);

        prev = ix;
    }
    int checked = 0;
    rep1(c, C) {
        int to_find = (checked+1) * portion;
        bool good = true;
        rep(i, h) {
            if (diffs[i][c] != to_find) { good = false; break; }
        }
        if (good) {
            ++checked;
        }
    }
    return (checked == w);  // ここを return (checked == h); としていてLarge落としました
}

int main() {
    int T; cin >> T;

    for (int t=1; t<=T; ++t) {
        int R, C, H, V; cin >> R>>C>>H>>V;
        vector<string> M(R);
        rep(r,R){
            cin>>M[r];
        }
        printf("Case #%d: ", t);
        bool ans = solve(R,C,H,V,M);
        printf("%s\n", ans ? "POSSIBLE" : "IMPOSSIBLE");
    }
    return 0;
}

B

悩んだ挙句にskip
問題の制約を読み違えてた
ていうか
例えばあるレジで扱える商品(ビット数)が2つだったら、10個の商品を抱えたロボットが5回並び直すような問題を解こうとして悩んでいた
orz

G翻訳様が

Note that once a robot finishes interacting with its cashier, it cannot be given more bits and cannot interact with other cashiers.

他のキャッシャーと対話することはできません。

とのみ訳出してくださったお陰です。本当にありがとうございました。

というわけで
難しい問題を解こうとしてたけど、これ二分探索で簡単に解ける問題じゃん><

[Practice]

一発AC
(↑翻訳を参考にするならもっと直訳系の翻訳サービスのほうがいいのでは?)

#include <bits/stdc++.h>
using namespace std;

#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define CLAMP(v,lo,hi) min(max(lo,v),hi)

vector<int> M, S, P;

ll f(ll t, int R) {
    vector<ll> v;

    int C = M.size();
    rep(c,C){
        ll m=M[c], s=S[c], p=P[c];
        ll possible = CLAMP((t-p)/s, 0LL, m);
        v.pb(possible);
    }
    sort(ALL(v));
    reverse(ALL(v));
    return accumulate(v.begin(), v.begin()+R, 0LL);
}

ll solve(int R, int B, int C) {
    ll lo=0, hi=4e18;

    while (lo+1 < hi) {
        ll mi = mid(lo, hi);
        if (f(mi, R) >= B) {
            hi = mi;
        } else {
            lo = mi;
        }
    }

    return hi;
}

int main() {
    int T; cin >> T;

    for (int t=1; t<=T; ++t) {
        int R, B, C; cin >> R >> B >> C;
        M.resize(C);
        S.resize(C);
        P.resize(C);
        rep(c, C) {
            cin >> M[c] >> S[c] >> P[c];
        }
        printf("Case #%d: ", t);
        ll ans = solve(R,B,C);
        printf("%lld\n", ans);
    }
    return 0;
}

C

ナップサック的問題
Largeで落ちた
区間のマージがバグってるせいか

[Practice]

はい、区間のマージのバグでした
AC
(↑単にケアレス。落ち着いて図を書くなどすれば防げたのでは)

#include <bits/stdc++.h>
using namespace std;

#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))


vector<int> W, H;


double solve(int N, int P) {
    vector<dd> dp;
    dp.pb(dd(0,0));
    double room = P;
    rep(i, N) {
        double w = W[i], h = H[i];
        room -= (w + h)*2;
    }
    double stab = P - room;

    rep(i, N) {
        double w = W[i], h = H[i];
        double from = 2*min(w, h), to = 2*hypot(w, h);
        vector<dd> dp2;
        for (dd p : dp) {
            dp2.pb(p);
            double F = p.first + from, T = min(room, p.second + to);
            if (F <= room) {
                dp2.pb(dd(F, T));
            }
        }
        sort(ALL(dp2));
        int L = dp2.size();
        dp.clear();
        dp.pb(dp2[0]);
        for (int i=1; i<L; ++i) {
            if (dp2[i].first <= dp.back().second) {
                dp.back().second = max(dp.back().second, dp2[i].second);
            } else {
                dp.pb(dp2[i]);
            }
        }
    }
    return stab + dp.back().second;

}

int main() {
    int T; cin >> T;

    for (int t=1; t<=T; ++t) {
        int N, P; cin >> N >> P;
        W.resize(N); H.resize(N);
        rep(i, N) {
            cin >> W[i] >> H[i];
        }
        printf("Case #%d: ", t);
        double ans = solve(N,P);
        printf("%.6f\n", ans);
    }
    return 0;
}