SRM 541

Single Round Match 541 Round 1 - Division II

http://community.topcoder.com/stat?c=round_overview&er=5&rd=14733

250と500を提出。500はチャレンジされ、撃墜。チャレンジ1回成功。合計208.58点。

レートは753から866へ。白コーダー灰コーダーのまま。ルーム内4位。Room 63。全体で116位。

Problem Status Points
250 AkariDaisukiDiv2 Opened 158.58
500 AntsMeet Challenge Succeeded 0.0
1000 NonXorLife Unopened 0.0
  • 250に25分、500に50分という配分であった
  • 500はチャレンジで撃墜された
    • 撃墜されはしたが、自分の実装に振り回されることがなかったように思う
      • 何故か満足感の高いSRMであった
  • 1回チャレンジを成功させた
  • 次回の目標
    • 例題を理解する
    • 2問通す

AkariDaisukiDiv2

25分。158.58点。

  • 一見とても計算量が大きく見える問題のように思えた
    • しかし、DIV IIの250なので全探索に近い解法を考えるようにした
  • Waaiを決めてやる
    • X、Akari、Daisukiも順次決めてやって、整合性をチェックしてやればよい
      • 実際にはWai、X、Akari、X(2回目)、Daisukiを決め、XとX(2回目)が等しいときに記録するようにした
  • Waaiが長くなればなるほど残りの候補の長さが短くなるはず
    • 初めに感じたほど計算量は大きくないように思い始める
  • タプルが重複するかもしれない
    • 問題文に提示してあった
    • ならば、"..."をstd::stringをキーとしてstd::setでカウントしてしまおう
  • この方法がどのくらい実装にインパクトを与えるか未検証のまま投稿した
    • 本当にタプルが重複するのか検討しなかった
      • 重複しないように思える
    • システムテストは通ったが、自分の実装だけ通らなくてもおかしくないことをしてしまったようにも思える

実装は以下。ベタベタだが、よく書けたように思う。

class AkariDaisukiDiv2 {
public:
  int countTuples(std::string S) {
    int size = S.size();

    std::set<std::string> set;

    for (int i = 1; i < size; i ++)
      for (int j = i + 1; j < size; j ++)
        for (int k = j + 1; k < size; k ++)
          for (int l = k + 1; l < size; l ++) {
            std::string X = S.substr(i, j - i);

            if (X == S.substr(k, l - k))
              set.insert(S.substr(0, i)        + '.' +
                         S.substr(j, k - j)    + '.' +
                         S.substr(l, size - l) + '.' +
                         X);
          }
    
    return set.size();
  };
};
  • 競技プログラミングを始める前はこのような反復を以下のように書く癖があった
    • 「無駄なく、最適に」
    • 競技プログラミングを始めてから、「これはそれほど最適ではないのでは」と考えるようになってきた
  for (int i = 0; i < n - 1; i ++)
    for (int j = i + 1; j < n; j ++)
                  :
    • 最近は以下のように書くようになった
      • 実装ミスが激減した
  for (int i = 0; i < n; i ++)
    for (int j = i + 1; j < n; j ++)
                  :

AntsMeet

46分。222.89点。すぐ反復の回数の見積もりが甘いことに気付き、投稿し直す。170.09点。チャレンジで撃墜される。0点。

時間を0.5刻みでシミュレーションしなければならないことに気付き、チャレンジを1回成功させた。50点。しかし、このチャレンジはとても危ういものであったことに後で気付いたのであった。

  • 総括
    • 結局題意を理解していなかった
      • 今回は例題から題意を補完するパターン
    • シミュレーションの総ステップ数を読み違え、再提出した
    • 結果的に駄目ではあったのだが、実装を理解していた。自分の実装に振り回されることがなかった
      • 何故か満足している
  • 初めはマンハッタン幾何のような実装を要求されているのかと思った
    • この時点で、進行方向がSの(x, 1000)と進行方向がNの(x, -1000)が衝突するか否かを確認するのに必要な時間は高々大体1000であると考えてしまった


    • そのため、全体のシミュレーションのステップ数を1024として最後まで考えてしまった
    • しかし、例えば進行方向がEの(-1000, 1000)と進行方向がNの(2000,-1000)の場合、大体2000ステップ必要なのであった


      • 実装を提出後に気付き、再提出を行う原因となった
    • 問題から点の出現する範囲がx ∈ [-1000, 1000]、y ∈ [-1000, 1000]であることは認識できていた
    • 衝突はその領域外では起こらないことも想像出来ていた
    • 紙に領域を図示したことはした
    • しかし、最大ステップ数の考察に至らなかった
      • 一つ目の敗因
  • 0.5刻みのステップとした場合にも衝突するか
    • 問題文には明確に記載されていない
    • 0.5刻みで衝突する事例は例題に記載されていたが、読み落す
    • 1刻みのシミュレーションでテストケース0、1、2が通った
    • 実装を0.5刻みでシミュレーションするように実装変更
    • 何らかの原因でテストケース2が通らないようになってしまった
      • この時点で、0.5刻みのシミュレーションでは成立しない問題であると思い込む
      • 二つ目の敗因
    • テストケース2はよくできており、1刻みでも0.5刻みでも同じ結果となる
      • テストケースの解説を読むことによってのみ判断可能な出題方法
        • このようなケースは珍しいようだ
    • 投稿前に0.5刻みの実装を1刻みの実装に戻す(!)
    • 投稿。この時点で最大シミュレーションステップは1024ステップ。1ステップは1刻み
  • バケット法を使ってみた
    • 今まで実装したことがなかった
    • std::pairをキーとし、std::vectorを値とするstd::mapを用意すればよさそうなので、そうした
      • よい選択、よい実装だったと思う
      • 競技コンテストで培われた感が身につき始めているように思い、素直に嬉しい
      • 特にstd::mapの存在しないキーの要素にアクセスした場合の考察が効いているようだ。嬉しい
    • あるステップであるバケットに点が集中してしまうこともあるはず
      • バケット内の点の数をnとすると以下の計算量。nが50としても1225回の比較


      • 常に集中するわけではない
      • 実装的にさほど重そうな感じもしなかったので、このままにしてみる
      • 後で蟻本を読んでみよう
      • 正しくはbucket methodであった...
  • .(ドット)以外の文字をstd::count_ifで数え上げようとした
    • しかし、全体の文字数から.(ドット)の数を引けばよいことに気付く
    • この実装結構好きだ
    return size - std::count(ALL(direction), '.');
  • チャレンジされた
    • 撃墜された
    • チャレンジしてきた人がやたらとチャレンジしまくっている
      • 何か必勝パターンがあるに違いない
    • チャレンジされていない残された500が、チャレンジしていた人のものともう一問だけとなった
    • 双方の実装を眺めるに、チャレンジしまくっていた人の実装は1刻みで、チャレンジされていなかった人の実装は0.5刻みであった
    • 0.5刻みでシミュレーションを書いている人もやっぱりいたのだなと思い、問題を確認
      • 例題で0.5刻みでしミュレショーンしなければならないことに気付く
    • ならばチャレンジだ
      • x = {0, 1}、y = {0, 0}、direction = "EW"というごく簡単なデータでチャレンジ成功
      • 後々相手の実装を見直すに、0.5刻みでシミュレーションせずともある時点で隣合った場合、という処理をしていたようだ
      • 結果、運に助けられた

投稿した実装は以下(チャレンジで撃墜された実装)。

typedef std::map<std::pair<int, int>, std::vector<int> > backet_t;


class AntsMeet {
public:
  int countAnts(std::vector<int> x, std::vector<int> y, std::string direction) {
    int size = x.size();

    for (int t = 0; t < 2048; t ++) {
      backet_t backet;
 
      for (int i = 0; i < size; i ++) {
        if (direction[i] == '.')
          continue;
        
        switch (direction[i]) {
        case 'N':
          y[i] ++;
          break;
        case 'E':
          x[i] ++;
          break;
        case 'S':
          y[i] --;
          break;
        case 'W':
          x[i] --;
          break;
        default:
          break;
        }

        backet[std::make_pair(x[i] / 100, y[i] / 100)].push_back(i);
      }

      for (backet_t::iterator it = backet.begin(); it != backet.end(); ++ it) {
        int n = it->second.size();

        std::set<int> disapper;

        for (int i = 0; i < n; i ++)
          for (int j = i + 1; j < n; j ++) {
            int m = it->second[i], n = it->second[j];

            if (direction[m] != '.' && direction[n] != '.')
              if (x[m] == x[n] && y[m] == y[n]) {
                disapper.insert(m);
                disapper.insert(n);
              }
          }

        for (std::set<int>::iterator it2 = disapper.begin(); it2 != disapper.end(); ++ it2)
          direction[*it2] = '.';
      }
    }
    
    return size - std::count(ALL(direction), '.');
  };
};

以下はシステムテストを通る、0.5刻みの実装。

#define ALL(x) (x).begin(), (x).end()


#define EPS 1.0e-3


typedef std::map<std::pair<int, int>, std::vector<int> > backet_t;


class AntsMeet {
public:
  int countAnts(std::vector<int> x, std::vector<int> y, std::string direction) {
    int size = x.size();

    std::vector<double> X, Y;

    for (int i = 0; i < size; i ++) {
      X.push_back(x[i]);
      Y.push_back(y[i]);
    }

    for (int t = 0; t < 4096; t ++) {
      backet_t backet;
 
      for (int i = 0; i < size; i ++) {
	if (direction[i] == '.')
	  continue;
	
	switch (direction[i]) {
	case 'N':
	  Y[i] += 0.5;
	  break;
	case 'E':
	  X[i] += 0.5;
	  break;
	case 'S':
	  Y[i] -= 0.5;
	  break;
	case 'W':
	  X[i] -= 0.5;
	  break;
	default:
	  break;
	}

	backet[std::make_pair((int)X[i] / 50, (int)Y[i] / 50)].push_back(i);
      }

      for (backet_t::iterator it = backet.begin(); it != backet.end(); ++ it) {
	int n = it->second.size();

	std::set<int> disapper;

	for (int i = 0; i < n; i ++)
	  for (int j = i + 1; j < n; j ++) {
	    int m = it->second[i], n = it->second[j];

	    if (direction[m] != '.' && direction[n] != '.')
	      if (std::abs(X[m] - X[n]) < EPS &&
		  std::abs(Y[m] - Y[n]) < EPS) {

		disapper.insert(m);
		disapper.insert(n);
	      }
	  }

	for (std::set<int>::iterator it2 = disapper.begin(); it2 != disapper.end(); ++ it2)
	  direction[*it2] = '.';
      }
    }
    
    return size - std::count(ALL(direction), '.');
  };
};
  • komiyamさんが不動小数点演算を避ける方法について解説している
    • 射影した座標の空間で処理する
      • この場合、縦横共に2倍拡大した座標空間を用いる
      • 目から鱗
  • kojingharangさんも同様の実装をしていた
    • 衝突の判定を無条件にn^2回計算しているのが興味深い
      • n^2もΣ [1, n-1]もO(n^2)の計算量
      • n = 50のときの計算量は2500と1225
        • 倍違うが大勢には影響なさそう
        • 教科書で読む計算量の話だ
          • この辺の感覚はまだ身に付いておらず、戸惑う
      • 氏の実装は計算量について何か重要なことを気付かしてくれたように思える
  • 半分の計算量について考えてみる
    • 半分の計算量のアルゴリズムがどのくらい計算量を稼いでくれるかという観点で考えてみる
      • √2倍くらいだろう
      • 以下の式をxについて解けばよい


      • xについて解いたものが以下


      • n = 50とするとx = 71.718くらい
    • 大体√2倍くらいだ

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?