GoogleCodeJam 2012 - Qualification Round / Problem B

Problem B. Dancing With the Googlers

このあたりから本番かな。small/large両方あるしね。

Google社員とダンスをするというシャレ乙な問題。
ただ、一般人がダンスするだけなのにスコア付けされるのかよ。

さてさて。
入力は3人の審査委員の点数の合計なのですが、3人の意見はいつも均衡に近い状況で、点差が3以上になることはないんだそうです。
つまり、合計点が15点なら(5,5,5)または(4,5,6)な感じで点数の組が分かれます。
もし、2点以上というか2点の差があれば"surprise"な組だと。
これって審査員談合してね？

surpriseな組の点数は合計をnとして、
n ≡ 0 (mod 3)なら: (floor(n/3)-1,  floor(n/3), floor(n/3)+1)
n ≡ 2 (mod 3)なら: (floor(n/3),  floor(n/3), floor(n/3)+2)
である。 n ≡ 1 (mod 3)ならsurpriseになりえない。
surpriseじゃない組も同じ感じで静的に求められる。
それぞれ、 make_triplet_surprise()と make_triplet_not_surprise()である。

main()の動きとしては、

1. はじめ全ての点数を"not surprise"な組にしておく。
2. 合計点の高いほうから順にS個を"surprise"な組にし直す。（"surprise"にできないならほっとく。）
3. is_above_p()を使って組の点数全てがpを超えている組をカウントする。

といった流れ。

コード全文は以下のような感じで。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <algorithm>
#include <functional>

#define CAN_SURPRISE(t)    ((t) ? (((t - ((t/3)*3))-1) ? 1 : 0) : 0)

typedef struct _Triplet{
    unsigned int t;
    unsigned int triplet[3];
} Triplet;

bool compareTriplet(Triplet &a, Triplet &b) {
    return a.t > b.t;
}

void make_triplet_not_surprise(unsigned int t, unsigned int* triplet) {
    unsigned int avg = t / 3;
    
    switch(t - (avg * 3)) {
    case 0:
        triplet[0] = triplet[1] = triplet[2] = avg;
        break;
    case 1:
        triplet[0] = avg+1;
        triplet[1] = triplet[2] = avg;
        break;
    case 2:
        triplet[0] = triplet[1] = avg+1;
        triplet[2] = avg;
        break;
    }
}

void make_triplet_surprise(unsigned int t, unsigned int* triplet) {
    int avg = t / 3;
    switch(t - (avg * 3)) {
    case 0:
        triplet[0] = avg+1;
        triplet[1] = avg;
        triplet[2] = avg-1;
        break;
    case 2:
        triplet[0] = avg+2;
        triplet[1] = triplet[2] = avg;
        break;
    }
}

int is_above_p(unsigned int p, unsigned int *triplet) {
    return ((triplet[0] >= p) || (triplet[1] >= p) || (triplet[2] >= p)) ? 1 : 0;
}

int main(int argc, char** argv) {
    unsigned int T, N, S, p, i, j, temp;
    unsigned int trip[3];
    
    //FILE *fp = fopen("input.txt","r");
    //FILE *fp = fopen("B-small-attempt0.in","r");
    FILE *fp = fopen("B-large.in","r");
    
    fscanf(fp, "%d\r\n", &T);
    
    for(j=0; j<T; ++j) {
        std::list<Triplet> t;
        std::list<Triplet>::iterator t_itr;
        
        fscanf(fp, "%d %d %d", &N, &S, &p);
        
        for(i=0; i<N; ++i) {
            fscanf(fp, "%d", &temp);
            make_triplet_not_surprise(temp, trip);
            Triplet tr;
            tr.t = temp;
            memmove(tr.triplet, trip, 3*sizeof(unsigned int));
            t.push_back(tr);
        }
        t.sort(compareTriplet);
        
        for(t_itr=t.begin(); t_itr!=t.end(); ++t_itr) {
            if(!is_above_p(p, t_itr->triplet) && CAN_SURPRISE(t_itr->t)) {
                if(S == 0) break;
                make_triplet_surprise(t_itr->t, t_itr->triplet);
                --S;
            }
        }
        
        temp = 0;
        for(t_itr=t.begin(); t_itr!=t.end(); ++t_itr) {
            if(is_above_p(p, t_itr->triplet)) ++temp;
        }
        
        printf("Case #%d: %d\n", j+1, temp);
    }
    fclose(fp);
    
    return EXIT_SUCCESS;
}

まぁこれもそんな難しくはないかな。