GoogleCodeJam 2012 - Qualification Round / Problem C

Problem C. Recycled Numbers
さて、Preblem C。ここまでは余裕だったが、これはどうだろう。

問題文曰く、

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don't care about television, but I do sometimes feel that way about numbers.

だそうだが、個人的には筆者の方が変態だと思う。

C++のSTLからsetを使う。Pair型の<演算子も定義する。(n, m)でnの方が優先。
recycleはnのstartから後ろを前に持ってきた数字を返す。
あとはひたすら全通り試していく。
ひたすらsetにinsertしても重複しないから便利。
でもって表示はsize()メソッドで表示すればfor文カウントもせずに終了できる。

コード全文は以下。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>

#define IN_RANGE(x, A, B)    ((A <= x)&&(x <= B))

typedef struct _pair{
    unsigned int n;
    unsigned int m;
} Pair;

bool operator<(const Pair& a, const Pair& b) {
    if(a.n == b.n) return a.m < b.m;
    else return a.n < b.n;
}

unsigned int NUMBER_OF_DIGITS;

int recycle(const unsigned int n, const unsigned int start) {
    unsigned int div_base = pow(10, start), temp = n % div_base;
    return (n / div_base) + (temp * pow(10, NUMBER_OF_DIGITS - start));
}

int main(int argc, char** argv) {
    unsigned int T, A, B, i, n, k, m;
    
    //FILE *fp = fopen("input.txt", "r");
    //FILE *fp = fopen("C-small-attempt0.in", "r");
    FILE *fp = fopen("C-large.in", "r");
    fscanf(fp, "%d", &T);
    
    for(i=0; i<T; ++i) {
        fscanf(fp, "%d %d", &A, &B);
        NUMBER_OF_DIGITS = log10(A)+1;
        if(NUMBER_OF_DIGITS == 1) {
            printf("Case #%d: %d\n", i+1, 0);
            continue;
        }
        
        std::set<Pair> pairs;
        
        for(n=A; n<=B; ++n) {
            for(k=1; k<NUMBER_OF_DIGITS; ++k) {
                m = recycle(n, k);
                if(n == m) continue;
                Pair new_pair = ((n < m) ? (Pair){n, m} : (Pair){m, n});
                if(IN_RANGE(m, A, B))
                    pairs.insert(new_pair);
            }
        }
        
        printf("Case #%d: %d\n", i+1, pairs.size());
    }
    
    fclose(fp);
    
    return EXIT_SUCCESS;
}

意外と楽だったかな。

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

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

GoogleCodeJam 2012 - Qualification Round / Problem A

Problem A. Speaking in Tongues


肩慣らし。

簡単な文字列置換のはなし。
テーブル作って1文字ずつ置換する。

問題文曰く、

Googlerese is based on the best possible replacement mapping, and we will never change it. It will always be the same. In every test case. We will not tell you the rest of our mapping because that would make the problem too easy, but there are a few examples below that may help.

だそうで、 テーブルはSampleのInputとOutputを照らし合わせればOKで、足りない2文字もswapして突っ込めばいい。

ちなみに、

char table[26] = {'y', 'h', 'e', 's', 'o', 'c', 'v', 'x', 'd', 'u', 'i', 'g', 'l', 'b', 'k', 'r', 'z', 't', 'n', 'w', 'j', 'p', 'f', 'm', 'a', 'q'};

こんな感じになるはず。

C言語で書くことにする。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char table[26] = {'y', 'h', 'e', 's', 'o', 'c', 'v', 'x', 'd', 'u', 'i', 'g', 'l', 'b', 'k', 'r', 'z', 't', 'n', 'w', 'j', 'p', 'f', 'm', 'a', 'q'};

void make_table() {
    unsigned int T, i, j;
    char ans[100];
    char str[100];
    
    FILE *fp = fopen("input.txt","r");
    FILE* fpA = fopen("ans.txt", "r");
    
    fscanf(fp, "%d\r\n", &T);
    for(i=0; i<T; ++i) {
        for(j=0; 1; ++j) {
            fscanf(fp, "%c", &str[j]);
            if(str[j] == '\n') break;
        }
        str[j] = '\0';
        
        for(j=0; 1; ++j) {
            fscanf(fpA, "%c", &ans[j]);
            if(ans[j] == '\n') break;
        }
        ans[j] = '\0';
        
        for(j=0; str[j] != '\0'; ++j) {
            table[(str[j] - 'a')] = ans[j];
        }
        printf("%s\n%s\n", str, ans);
    }
    
    fclose(fp);
    fclose(fpA);
    
    for(i=0; i<26; ++i) {
        printf("%c -> %c\t", i+'a', table[i]);
        //printf("\'%c\', ", table[i]);
        if((i+1) % 7 == 0) putchar('\n');
    }
}

void translate(char* buf, const char* str) {
    unsigned int i;
    
    for(i=0; str[i] != '\0'; ++i) {
        if(str[i] == ' ') buf[i] = ' ';
        else buf[i] = table[(str[i] - 'a')];
    }
    buf[i] = '\0';
}

int main(int argc, char** argv) {
    unsigned int T, i, j;
    //char str[100], buf[100];
    char *str = (char*)malloc(100);
    char *buf = (char*)malloc(100);
    
    //FILE *fp = fopen("input.txt","r");
    FILE *fp = fopen("A-small-attempt0.in","r");
    fscanf(fp, "%d\r\n", &T);
    for(i=0; i<T; ++i) {
        for(j=0; 1; ++j) {
            fscanf(fp, "%c", &str[j]);
            if(str[j] == '\n') break;
        }
        str[j] = '\0';
        translate(buf, str);
        printf("Case #%d: %s\n", i+1, buf);
    }
    fclose(fp);
    
    return EXIT_SUCCESS;
}

make_table()は初めにchar teble[];をつくるときにつかったもの。
main()とは別に用いていて、呼び出しはしていない。

ほかにコメントすることはないなぁ。。。