• このエントリーをはてなブックマークに追加

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

問題

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

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

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