08 Sep 2013, 02:00

TopCoder SRM 590 div2 250

TopCoderに参戦!

深夜のTopCoderは起きてるのだけで辛い。。。>_<

CourseraのAlgorithms Part1のノルマをこなすために、この日は朝からずっとアルゴリズム漬けだった。15時間の勉強のあとに、TopCoder参戦。

Courseraはイバラの道だったな。。。休日が課題で潰れる。もっと平日定時退社できればいいのだけれども。

そんなこんなで、疲れ果ててほとんど問題が解けなかった。いつになっても全く成長できない。。。

 

27 Aug 2013, 13:00

TopCoder SRM : 587 Div2 Level1 Level2

TopCoder参戦!今日は、定時退社をしようとおもったけれども結局できずに、会社近くのカフェからTopCoder参戦した。

今週から、CourseraのAlgorithms PartⅠを受講中。本格的に、アルゴリズムの勉強に力を淹れている。


Algorithms, Part I | Coursera



Level1は、過去問で似たような問題を解いたことがあるので、mapを利用して難なくクリア。

Level2は、問題の意味を理解するのに苦戦。最後は、やっつけで条件を追加したらテストをパスしたのでそのまま提出。案の定、システムテストで落とされた。

10 Jul 2013, 13:15

TopCorder SRM 584 div2 250

久しぶりのTopCoder参加。そろそろ本気だして、アルゴリズムの勉強したい今日このごろ。

しかし、今日もTopCoder出来なさ過ぎて、ついに日本で下から5番目まで下がったので死にたい今日このごろ。

div2 250 TopFox

彼女の Family Name は FamilyName, given nameは givenName.

hundle nameを 以下のルールに従って決めようと思う。

  • s != null の Family name prefix
  • t != null の Family name prefix

handle name は s と tの組み合わせで選ぶ。FamilyNameとgivenNameが与えられるので、hundles の可能な組み合わせの数を求めよ。

解き方

きれいな解法を考えていたけれども、だんだん時間なくなってきて焦ったので、結局全探索する。連想配列のサイズを求めれば、もっとシンプルにできたかな。

12 Apr 2013, 03:22

[TopCoder日記] SRM 576, Division 2

久しぶりのTopCoder参戦 & 悲しい惨敗。。。

C++ の vector配列の使い方がわからず苦戦してた。

vector配列は動的配列なので、vec.push_back(hoge);で初期化する必要があったのだった。

Level1の問題は解けたのだが、Eclipse上ではテストは通ったがarena上ではテストが通らず、時間切れとなった。なぜだろう。

Level1 determineHumidity

N個のパーティションで区切られた空間ごとに水滴を垂らす。

水滴の数は、配列intensityで与えられる。水滴は長さLのスポンジによって受け止められる。

スポンジの位置は配列leftEndで与えられる。

スポンジには上から並べられているので、同じ位置の上下でスポンジがあるときは、下のスポンジには水滴はたらされない。

L個のスポンジにそれぞれたらされる水滴の数を求めよ。

 

07 Mar 2013, 14:33

[TopCoder日記] SRM 572, Division 2

今回は、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;

}

};

14 Feb 2013, 13:05

[TopCoder日記] SRM 570, Division 2, Level 1 : Chopsticks

TopCoder SRM570に参加した記録です。

当日の感想

今回で3回目の参戦。
英語の問題文にひるまないだけの度胸はついた。
当初思っていたよりも難しくはないことは分かった。

プログラミングをしているよりも、白紙に向かっていろいろと数式を書いている時間の方が長い。プログラミングは、考えた解法をそのまま書くだけと言った感じ。

言語の壁という点では、英語よりもC++の知識が乏しいのがつらい。
vectorの使い方がわからなかったり。(配列のサイズの求め方がわからん!)

わからなくなったら独習C++を元にガンパル。

Level 1 : Chopsticks

問題

異なる長さの箸がN本ある。
同じ長さのペアの数がパーティーに招待できる人数。
さあ、招待できる人数の最大値を求めよ。

システムテストで落とされた。なぜだろう。
連想配列を利用して、参考書を見ながらもう少し綺麗に書きなおした。
連想配列が空気を吸うように使いこなせればいいな。

/*  TopCoder
 *  SRM       : 570
 *  Division  : 1
 *  Level     : 2
 *
 *  Created on: 2013/02/14
 *      Author: tsu_nera<fox10225fox@gmail.com>
 */
 
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
 
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
 
class Chopsticks {
 
public: int getmax(vector<int> length) {
 
  map<int, int> dic;
 
  for (int i = 0; i < (int)length.size(); i++) {
    dic[length[i]] = 0;
  }
 
  for (int i = 0; i < (int)length.size(); i++) {
    dic[length[i]]++;
  }
 
  int ans = 0;
  map<int, int>::iterator it;
  for (it = dic.begin() ; it != dic.end(); it++) {
    ans += ( (*it).second /2);
  }
 
  return ans;
 
}
 
};

Level 2 : RobotHerbDiv2

問題

ロポットが与えられた配列と規則に従って移動する。

最終的に移動した場所の原点からの距離を求めよ。

規則を漸化式に起こそうとしたが、途中で時間切れ。