Home > Tags > c

c

TopCoder SRM 407

2008-06-28 (Sat)
default
c | TopCoder

レッドカーペットみてビール3缶飲んで、さあて寝るかと歯を磨いてたら、TwitterからTopCoderがどうたらというポストが流れていて、あ、今夜24時からだったんだ! と気づいたのが23:50。あわてて参加しました。

250 問題 : SpiralWalking

あたえられた矩形を時計まわりにぐるぐる周り、すべてのマス目を歩き尽くすまでに道にあったポイントを合計せよという問題。ぐるぐる周るのってどうするんだっけや、とか壁を表現するのはどういうテクニックをつかうんだったけな、とか試行錯誤してるうちに40分くらいたって、やっとsubmit。ひどす。

コード:

bool visited[52][52];
class SpiralWalking {
   public:
   int totalPoints(vector <string> levelMap) {
     for (int i(0); i<52; i++) for (int j(0); j<52; j++) visited[i][j] = false;
     for (int i(0); i<52; i++) {
       visited[i][0] = true; visited[i][51] = true;
       visited[0][i] = true; visited[51][i] = true;
     }
     int W(levelMap[0].size()), H(levelMap.size());
 
     for (int i(0); i<W+2; i++)
       visited[0][i] = true; visited[H+1][i] = true;
     for (int i(0); i<H+2; i++)
       visited[i][0] = true; visited[i][W+1] = true;
 
     int score(0), x(1), y(1), dx(1), dy(0);
     while (true) {
       int i(0);
       bool turned(false);
       for (; i<4; i++) {
         if (not visited[y+dy][x+dx]) break;
         if (dx > 0) {
           dx = 0; dy = 1; turned = true;
         } else if (dx < 0) {
           dx = 0; dy = -1; turned = true;
         } else if (dy > 0) {
           dx = -1; dy = 0; turned = true;
         } else if (dy < 0) {
           dx = 1; dy = 0; turned = true;
         }
       }
       if (4 == i) break;
       if (not turned) score += levelMap[y-1][x-1]-'0';
       visited[y][x] = true;
       x += dx; y += dy;
     }
     score += levelMap[y-1][x-1]-'0';
     return score;
   }
};

我ながらこれはひどい。でもいちおうSystem Testにパス。

500 問題 : CorporationSalary

Problem Statement

詳しい説明は nishioさんとこを参照。

250より500の方が簡単じゃないか! 再帰でいっぱつやん! と5分くらいで書いてsubmit。

コード:

class CorporationSalary {
   public:
   long long calcSalary(int x, vector <long long> &salaries, vector <string> &relations) {
     if (-1 != salaries[x]) return salaries[x];
 
     int count(0);
     int total(0);
     for (size_t i(0); i<relations.size(); i++) {
       if ('Y' == relations[x][i]) {
         total += calcSalary(i, salaries, relations); count++;
       }
     }
     if (0 == count) {
       salaries[x] = 1; return 1;
     }
     salaries[x] = total; return total;
   }
 
   long long totalSalary(vector <string> relations) {
     int N(relations.size());
     vector <long long> salaries(N, -1);
     for (int i(0); i<N; i++)
       salaries[i] = calcSalary(i, salaries, relations);
 
     long long total(0);
     for (int i(0); i<N; i++)
       total += salaries[i];
     return total;
   }
};