解いた問題

10/27/2011

SRM470 Div1 Easy

目的の部屋の右側にしかない色、左側にしかない色、両方にある色の3つに分類する。
その後は、実際にドアを開けて試してみる。
自分の側にしかない色を優先して開けるのが最善手。
実際に開けなくても、計算して出せる気もする。。。

class DoorsGame {
public:
  int determineOutcome(string d, int tro) {

    set<char> J, G, common;
    for (int i = 0; i < d.size(); ++i) {
      if (i == tro) break;
      J.insert(d[i]);
    }   
    for (int i = d.size(); 0 <= i; --i) {
      if (i == tro) break;
      G.insert(d[i - 1]);
    }       

    for (int i = 0; i < d.size(); ++i) {
      if (J.count(d[i]) && G.count(d[i])) {
        common.insert(d[i]);
        J.erase(d[i]);
        G.erase(d[i]);
      }
    }

    int turn = 0;
    while (true) {
      ++turn;
      { // J
        if (J.size()) J.erase(J.begin());
        else common.erase(common.begin());
      }
      if (common.empty()) {
        if (J.empty() && G.empty()) return 0;
        if (J.empty()) return +turn;
        if (G.empty()) return -turn;
      }
      ++turn;
      { // G
        if (G.size()) G.erase(G.begin());
        else common.erase(common.begin());
      }
      if (common.empty()) {
        if (J.empty() && G.empty()) return 0;
        if (J.empty()) return +turn;
        if (G.empty()) return -turn;
      }
    }

    return turn;
  }

0 件のコメント :

コメントを投稿