naoya_t@hatenablog

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

Google Code Jam 2018 - Round 1B

4/30(月) 1:00am - 3:30am JST

aaAbX--- で35点609位でRound 2進出。
f:id:n4_t:20180430050933p:plain

今回は25点(aaAまたはb--c--)の途中 (2:17:48) がボーダーライン(ちょい難しめ)。aa-b- の24点では通らないのでa-Largeが通っててよかった。

A - Rounding Error (5pt 9pt 11pt)

最高のプログラミング言語はどれなのか、N人に投票してもらった結果を集計する話。
(まだ全員分の投票は集まっていない)
%を四捨五入するので合計が100%を上回ったり下回ったりするのだけれど、全員分の投票が集まった時に合計として考えられる最大の%を求める。

分母Nの分数で、%表示した時に四捨五入で切り上がる数(というかその分子)を配列で持っておけば、最寄りのその数は lower_bound() で(=O(logN)で)求められる。そんな数が見つからないこともある。その配列は空である可能性もある。
C[ ] の中で%表示で切り下がる数について、切り上がる数にすることができるとしたらあと何票必要か(コスト)をそうやって求める。
このコストの低い順に未投票分を割り当てて、なるべく多く切り上がるようにする。
それでも未投票が余った場合、一番小さい切り上がる数(最小コスト数:例の配列の最初の数)をC[ ]に可能なだけ追加していく。(例の配列が空の場合はここはスキップ)
それでも余った未投票分をまとめてC[ ]の末尾に追加。
そして切り上げ集計した結果を返す。

1投目全滅。
↓最小コスト数より大きい補填はしないようにした
2投目1つだけAC。
↓コスト低い順ではなくC[ ]の先頭から貪欲に割り当ててしまっているのをコスト低い順に修正
3投目で3つとも(コンテスト中は前2つ)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,int L,vi& a) {
    int rest = N;
    for(int ai : a) rest -= ai;
    assert(rest >= 0);

    vector<double> rem(N+1);
    rep(i,N+1){
        double x = 100.0 * i / N;
        rem[i] = x - (int) x;
    }
    vector<int> plus;
    rep(i,N+1){
        if (rem[i] >= 0.5) plus.pb(i);
    }
    int P = plus.size();

    int smallest = (P > 0) ? plus[0] : -1;

    vector<ii> ad;

    if (P > 0) {
        rep(i, L){
            int ai = a[i];

            double x = 100.0 * ai / N;
            if ((x - (int)x) >= 0.5) continue;

            int ix = lower_bound(ALL(plus), ai) - plus.begin();
            if (ix == P) continue;

            int us = plus[ix] - ai;
            if (us < smallest) {
                ad.pb(ii(us, i));
            }
        }

        sort(ALL(ad));

        for(ii p : ad){
            int us = p.first, i = p.second;
            if (us < smallest && us <= rest) {
                a[i] += us;
                rest -= us;
            }
        }
    }
    if (rest > 0) {
        if (P == 0) {
            a.pb(rest);
            rest = 0;
        } else {
            while (rest >= smallest) {
                a.pb(smallest);
                rest -= smallest;
            }
            assert(rest < smallest);
            if (rest > 0) {
                a.pb(rest);
                rest = 0;
            }
        }
    }
    int ans = 0;
    for(int ai : a) {
        double x = 100.0 * ai / N;
        ans += (int)(x + 0.5);
    }
    return ans;
}

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

    vector<int> a;
    a.reserve(100000);

    for (int t=1; t<=T; ++t) {
        loadvec(a, 2);
        int N=a[0], L=a[1];
        loadvec(a, L);
        int ans = solve(N,L,a);
        printf("Case #%d: %d\n", t, ans);
    }
    return 0;
}

B - Mysterious Road Signs (10pt 20pt)

東西に伸びる1本の道があって、いくつかの標識が立っていて、それぞれの標識の表と裏(西側と東側)に別の数字が書いてある。
多分標識からどこか別の地点までの距離だろう(西側の数字はそこから東へその数だけ進んだ地点を指し、東側の数字はそこから西へ(略))と推察。どちらかの面の数字は間違っているかもしれない。
同じ地点のペアを指している連続した標識の集合の一番大きいやつと、そのサイズの集合がいくつあるか求める問題。

とりあえずsmallを通しに行こう。max(S)=100。

標識はS=100本あって、地点の候補が東面(M)=S箇所, 西面(N)=S箇所あるので (M, N) の組み合わせとしてはS^2=10000通りある。
(M, N) の組み合わせそれぞれについて、連続する標識集合を数えていく。これはO(S)。自分のコードではsetを使ってるので最悪O(SlogS)か。
なので O(S^3logS) だけど間に合うはず。
→AC
Largeは飛ばしてCを見る。

#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 solveS(int S, vi& D, vi& A, vi& B) {
    vi m(S), n(S);
    rep(i,S){
        m[i] = D[i] + A[i];
        n[i] = D[i] - B[i];
    }
    set<int> Ms(ALL(m)), Ns(ALL(n));
    vi Mu(ALL(Ms)), Nu(ALL(Ns));
    int mun=Mu.size(), nun=Nu.size();

    vector<set<int>> st(S+1);
    rep(u,mun) rep(v,nun){
        int mi = Mu[u], ni = Nu[v];
        int good=0;
        rep(i,S){
            if (m[i]==mi || n[i]==ni) {
                ++good;
            } else {
                if(good) st[good].insert(i);
                good = 0;
            }
        }
        if(good) st[good].insert(S);
    }
    for(int i=S; i>=0; --i) {
        if (st[i].size() > 0) {
            printf("%d %d\n", i, (int)st[i].size());
            return;
        }
    }

    printf("0 0\n");
}

int main() {
    int T; cin >> T;
    for (int t=1; t<=T; ++t) {
        int S; cin >> S;
        vector<int> D(S), A(S), B(S);
        rep(i, S){
            cin >> D[i] >> A[i] >> B[i];
        }
        printf("Case #%d: ", t);
        solveS(S,D,A,B);
    }
    return 0;
}

C - Transmutation (15pt 18pt 12pt)

錬金術問題。M種類の金属があって、2つの金属から1つの金属を錬成する式がM個あって、各金属の量の初期値が与えられていて、鉛を最大量錬成したいという話。
材料に鉛を使う錬成式は(出来た金属を後で使って最終的に鉛ができるとしても、徒に他の金属を消費するだけなので)無視できる、というのは分かる。
とりあえず各金属の量を状態とするBFSを書いて実験。(サンプルケースは通るが15pt(M=8)の最悪ケースが通らない遅さ)

(その辺りで2:26ぐらいだったのでここで試合終了してA-largeが通りますようにお祈りモードに移行)