2012/04/15(日)Google Code Jam 2012 Qualに参加して60点を取ったよ!

はてブ数 2012/04/15 19:03 計算機な日記::プロコンつーさ

問題: http://code.google.com/codejam/contest/1460488/dashboard

A 謎言語 Googlerese

Googlerese は、アルファベットを1対1で置き換えた新言語です。
たとえば、"a zoo"は"y qee"になります。
Gppglerese 表現が与えられるので元に戻してください。
この置換表はテストケースごとに変わったりしません。

謎問題というか斬新というか。
問題文中のヒントとサンプルインプットから推測すればよいのね。
q->z だけわからなかったので加えた。

#include <iostream>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i < (n); i++)
#define REP2(i,s,n) for(int i=(s); i < (n); i++)
#define COUNTOF(a) (sizeof(a) / sizeof(a[0]))

int main()
{
    string input[] = {
        "yeq",
        "ejp mysljylc kd kxveddknmc re jsicpdrysi",
        "rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd",
        "de kr kd eoya kw aej tysr re ujdr lkgc jv",
        "z",
    };

    string output[] = {
        "aoz",
        "our language is impossible to understand",
        "there are twenty six factorial possibilities",
        "so it is okay if you want to just give up",
        "q",
    };

    char table[26] = { };
    REP(i, COUNTOF(input)) REP(j, input[i].size())
        if (input[i][j] != ' ')
            table[input[i][j] - 'a'] = output[i][j];

    int TESTCASES; cin >> TESTCASES;
    string x; 
    getline(cin, x);
    for (int CASE = 1; CASE <= TESTCASES; CASE++)
    {
        getline(cin, x);
        REP(i, x.size())
            x[i] = x[i] == ' ' ? ' ' : table[x[i] - 'a'];

        cout << "Case #" << CASE << ": " << x << endl;

    }

    return 0;
}

B 10点!10点!10点!

3人の審判がダンスに対する点を付ける。最低0点から10点満点。
3人の審判の点のうち1番高いものを最高点、1番低いものを最低点、3人の審判の点を合計したものを合計点としよう。
3人の審判はだいたいおんなじ評価基準に沿ってるので 7点7点8点 とか、最高点と最低点が1点しか違わないのがほとんど。
最高点と最低点の差が2点(6点7点8点とか)になることは稀で「びっくり」だし、
まして、最高点と最低点の差が3点以上(6点7点9点とか)になることは絶対にありません。
今N人のダンサーが踊った。N個の合計点と「びっくり」点がついたダンサーがS人いる。
さて、最高点がp点以上のダンサーは最大で何人いると考えられるか答えよう。 N <= 100だよ。

問題の読解がちょっと大変だった。
p = 0 や p = 1 のときに気をつけないといけない。

#include <iostream>
using namespace std;

#define REP(i,n) for(int i=0; i < (n); i++)
#define REP2(i,s,n) for(int i=(s); i < (n); i++)

int main()
{
    int TESTCASES; cin >> TESTCASES;
    for (int CASE = 1; CASE <= TESTCASES; CASE++)
    {
        int N, S, p; cin >> N >> S >> p;
        int r = 0;
        
        REP(i, N) {
            int k; cin >> k;
            if (p == 0) { r++; }
            else if (p == 1) { 
                if (k >= 1) r++;
            } else {
                if (k >= p*3 - 2) r++;
                else if (k >= p*3 - 4 && S > 0) { S--; r++; }
            }
        }
        
        cout << "Case #" << CASE << ": " << r << endl;
    }

    return 0;
}

C 数字リサイクル

たとえば(12345, 34512) みたいな、ある整数nと、それを途中の桁でちょん切って前後を入れ替えたものmとでペア(n, m)を作ります。
指定された整数A, Bの間に A <= n < m <= B を満たす (n, m) はいくつあるでしょうか。 A <= B <= 2000000だよ。

問題原文のテレビが再放送(?)ばかりでつまらないという書き出しからだが何のつながりもない。
nが最大7桁の整数だから、1つの数字について試すのが7種類x200万。
まぁ、 121212 とかで同じのができるから、そのチェックでx7。
49x200万 1億。 愚直にやるだけ? 愚直にやるだけか。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i < (n); i++)
#define REP2(i,s,n) for(int i=(s); i < (n); i++)

int main()
{
    int TESTCASES; cin >> TESTCASES;
    for (int CASE = 1; CASE <= TESTCASES; CASE++)
    {
        int A, B; cin >> A >> B;
        int r = 0;

        vector<int> m;
        REP2(n, A, B)
        {
            m.clear();
            m.push_back(n);
#define TEST(v) { int x = v; if (x >= A && x <= B && x > n && find(m.begin(), m.end(), x) == m.end()) { r++; m.push_back(x); } }

            if (n < 10) {
            } else if (n < 100) {
                TEST(n / 10 + n % 10 * 10);
            } else if (n < 1000) {
                TEST(n / 10 + n % 10 * 100);
                TEST(n / 100 + n % 100 * 10);
            } else if (n < 10000) {
                TEST(n / 10 + n % 10 * 1000);
                TEST(n / 100 + n % 100 * 100);
                TEST(n / 1000 + n % 1000 * 10);
            } else if (n < 100000) {
                TEST(n / 10 + n % 10 * 10000);
                TEST(n / 100 + n % 100 * 1000);
                TEST(n / 1000 + n % 1000 * 100);
                TEST(n / 10000 + n % 10000 * 10);
            } else if (n < 1000000) {
                TEST(n / 10 + n % 10 * 100000);
                TEST(n / 100 + n % 100 * 10000);
                TEST(n / 1000 + n % 1000 * 1000);
                TEST(n / 10000 + n % 10000 * 100);
                TEST(n / 100000 + n % 100000 * 10);
            } else if (n < 10000000) {
                TEST(n / 10 + n % 10 * 1000000);
                TEST(n / 100 + n % 100 * 100000);
                TEST(n / 1000 + n % 1000 * 10000);
                TEST(n / 10000 + n % 10000 * 1000);
                TEST(n / 100000 + n % 100000 * 100);
                TEST(n / 1000000 + n % 1000000 * 10);
            }
        }

        cout << "Case #" << CASE << ": " << r << endl;
    }

    return 0;
}

D 反射する私

全面鏡張り、マス目に区切られた最高30x30の部屋があるよ。
マス(x,y)の真ん中に自分がいるよ。鏡に反射した自分の姿はいくつ見えるかな。
部屋は霧ってて距離D <= 50以上の光は届かないよ。部屋は最大30x30、最外周は必ず鏡だよ。

光系の幾何問題はなんか難しい。
光線が1本出るタイプのはレイトレすればいいんだけど、
こうやって放射状に光がどばーっと出てるタイプの問題はいまいちどう考えればいいのかわかんない。

未提出。

ちょっとインデントぐちゃぐちゃ。
昔はこんなに汚いコード書かなかったんだけど、
仕事によっていろんなルールを強制されたりで色々やってたら、
なんか自分が普段使ってるルールが曲がったりしてて、
もちっと、ちゃんとルール決めてちゃんとしないとなー、と思う。