naoya_t@hatenablog

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

Google Code Jam 2018 - Round 1C

Round 1Bで勝ち抜けたので今回はvirtual参戦(スタバから)。

書いておいたコードを終了後にpracticeに投げたらaABcXで73点。(所要1h42mだから550位あたりに相当)

A - A Whole New Word

これ全パターン列挙してみて(高々2001番目まで)、既出でないやつを答えればいいだけでは
→AC

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

#define 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))


string solve(int N, int L, vector<string>& w) {
    if (N == 1) goto impossible;

    {
        vector<set<char>> tmp(L);
        rep(i,N){
            rep(j,L){
                tmp[j].insert(w[i][j]);
            }
        }
        vector<vector<char>> letters(L);
        vector<int> cn(L);
        ll p=1LL;
        rep(j,L){
            letters[j] = vector<char>(ALL(tmp[j]));
            cn[j] = letters[j].size();
            p *= cn[j];
        }
        if (p == N) goto impossible;

        set<string> sw(ALL(w));
        vector<int> ix(L+1, 0);
        rep(i, N+1) {
            vector<char> sp(L);
            rep(j,L) {
                sp[j] = letters[j][ ix[j] ];
            }
            string s(ALL(sp));
            if (!found(sw, s)) {
                return s;
            }

            ++ix[0];
            rep(j,L) {
                if (ix[j] == cn[j]) {
                    ix[j] = 0; ++ix[j+1];
                }
            }
        }
    }

impossible:
    return "-";
}

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

    for (int t=1; t<=T; ++t) {
        int N, L; cin >>N >>L;
        vector<string> w(N);
        rep(i,N) cin >>w[i];
        string ans = solve(N,L,w);
        printf("Case #%d: %s\n", t, ans.c_str());
    }
    return 0;
}

B - Lollipop Shop

インタラクティブ問題。(最後にやった)
統計を取っていって一番人気のないやつを売る作戦。
→AC

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

#define 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))


void say(int x) {
    cout << x << endl << flush;
}

void solve_case(int N){
    vector<int> stat(N, 0);
    vector<int> sold(N, false);

    rep1(n,N){
        int D; cin >> D;
        vector<int> L; // (D);
        rep(j,D) {
            int id; cin >> id;
            if (!sold[id]) L.pb(id);
            ++stat[id];
        }

        D = L.size();
        if (D == 0) goto disappointed;

        {
            vector<double> rate(D, 0);
            vector<pair<double,int>> di(D);
            double rate_sum = 0;
            rep(j,D){
                int id = L[j];
                rate[j] = (double)stat[id] / n;
                rate_sum += rate[j];
                di[j] = make_pair(rate[j], j);
            }

            bool _sell_something = false;

            // argmin
            sort(ALL(di)); reverse(ALL(di));
            for (int j=D-1; j>=0; --j) {
                int id = L[ di[j].second ];
                if (sold[id]) continue;

                say(id);
                _sell_something = true;
                sold[id] = true; break;
            }

            if (_sell_something) continue;
        }

    disappointed:
        say(-1);
    }
}
int main() {
    int T; cin >> T;

    for (int t=1; t<=T; ++t) {
        int N; cin >> N;
        solve_case(N);
    }
    return 0;
}

C - Ant Stack

蟻で組体操(縦一列)するやつ。(組体操は滅ぶべし。)
smallの制約なら適当にやっても通りそう。
largeはN=1e5の時とか死にそう。
→smallだけ通った

解説を読んで

なるほど、W≦1e9の範囲だと高々139段しか積めない、と。

st = [1]
wsum = sum(st)

while True:
    next = int((wsum+5) / 6)
    if next > 1e9:
        break
    st.append(next)
    wsum += next

print(len(st), st)
; => 139 [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 20, 23, 27, 32, 37, 43, 50, 59, 69, 80, 93, 109, 127, 148, 173, 202, 235, 275, 320, 374, 436, 509, 594, 693, 808, 943, 1100, 1283, 1497, 1747, 2038, 2377, 2774, 3236, 3775, 4404, 5138, 5995, 6994, 8160, 9520, 11106, 12957, 15117, 17636, 20576, 24005, 28006, 32673, 38119, 44472, 51884, 60531, 70620, 82390, 96122, 112142, 130832, 152638, 178077, 207757, 242383, 282780, 329910, 384895, 449044, 523885, 611199, 713066, 831910, 970562, 1132322, 1321042, 1541216, 1798085, 2097766, 2447394, 2855293, 3331175, 3886371, 4534099, 5289782, 6171413, 7199982, 8399979, 9799975, 11433304, 13338855, 15561997, 18155664, 21181608, 24711876, 28830522, 33635609, 39241543, 45781801, 53412101, 62314118, 72699804, 84816438, 98952511, 115444596, 134685362, 157132922, 183321743, 213875367, 249521261, 291108138, 339626161, 396230521, 462268941, 539313765, 629199392, 734065958, 856410284, 999145331]

solve() の q[] を139+1だけ用意しておいてjのカウントダウンを(iからではなく)139から回せば良さそう。
→AC

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

#define 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 INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}
int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    return i;
}


int solve(int N, vi& w){
    reverse(ALL(w));
    vector<ll> q(N+1, -1);

    rep(i,N){
        ll wi = w[i];

        int L = 1+i;
        for (int j=i; j>=0; --j) {
            if (j == 0) {
                q[1] = max(q[1], wi * 6);
            }
            if (wi <= q[j]) {
                q[j+1] = max(q[j+1], min(q[j] - wi, wi*6));
            }
        }
    }
    int cnt = 0;
    rep1(i, N){
        if (q[i] == -1) return i-1;
    }
    return N;
}

int main() {
    int T = loadint();

    for (int t=1; t<=T; ++t) {
        int N = loadint();
        vector<int> W(N);
        loadvec(W, N);
        int ans = solve(N, W);
        printf("Case #%d: %d\n", t, ans);
    }
    return 0;
}