今回は、TopCoderに参加前にEclipseCoderからログインできず、かなりあたふたしたが、なんとか登録完了。

安心して、開始時間までジョギングに出かけたら見事に遅刻したorz。

Level 1: EasyHomework

与えられた配列の要素の積の符号を求める問題。与えられた配列をそのまま計算すると桁あふれするので、1/-1に要約するのがポイント。これはチョロかった。

/*
*  TopCoder
*  SRM       : 572
*  Division  : 2
*  Level     : 1
*
*  Created on: 2013/03/07
*      Author: tsu_nera
*/
#include <string>
#include <vector>
using namespace std;

class EasyHomework {

     public: string determineSign(vector<int> A) {

          // Initialization
          int rslt_integer = 1;
          int now_integer = 0;

          // Search
          for (int i = 0; i < (int)A.size(); ++i) {

               if( A[i] == 0 )     return "ZERO";

               now_integer = ( A[i] > 0) ? 1 : -1;
               rslt_integer *= now_integer;
          }

          // Judge
          return ( rslt_integer > 0 ) ? "POSITIVE"
                                        : "NEGATIVE";
     }

};

Level2: NextOrPrev

与えられたstart文字列を規則に従ってgoal文字列まで変形する。

変形までにかかる最小コストを求める。

ただし、変形の過程で文字列の中の文字は一意であることが条件。

反例はわかったのだが、そのアルゴリズムがわからなかった。。。挫折。

/*
 *  TopCoder
 *  SRM       : 572
 *  Division  : 2
 *  Level     : 2
 *
 *  Created on: 2013/03/06
 *      Author: tsu_nera
 */
using namespace std;

#define debug(x) cout << #x << " = " << x << endl;
#define size(a) int ((a).size())

class NextOrPrev {

public: int getMinimum( int nextCost, int prevCost, string start, string goal) {

        int cost = 0;
        int distance = 0;

        for(int i = 0; i < size(start); i++) {
               for(int j = 0; j < size(start); j++) {
                      if( ((start[i] - start[j]) * (goal[i] - goal[j]) ) < 0 ) {
                            return -1;
                     }
              }
       }

        for(int i = 0; i < size(start); i++ ) {
              distance = ( goal[i] - start[i] );

               if( distance == 0) continue;

               if( distance > 0 ) {
                     cost += nextCost * distance;
              }
               else {
                     cost -= prevCost * distance;
              }
       }

        return cost;

}

};