SRM 546

Single Round Match 546 Round 1

http://community.topcoder.com/stat?c=round_overview&rd=14738

250に9分。550に23分。Room 55。レートは847から945へ。やっと緑コーダーに復帰できた。

Problem Status Points
250 ContestWinner Passed System Test 225.60
550 TwoRectangles Passed System Test 367.46
1000 FavouriteDigits Opened
  • 250に9分。225.60点
  • 550は23分。367.46点
  • 1000も開いた
    • 解ける気がした
    • 時間切れ
    • 後で解き直したが、3時間ほどかかった
      • 時間内で解けるものではなかった
      • それでも解けたのが嬉しい
  • 緑コーダーに復帰できて嬉しい
  • 次回の目標
    • 2問通す

ContestWinner

http://community.topcoder.com/stat?c=problem_statement&pm=12048&rd=14738

9分。225.60点。

  • 解法を思いつく前に実装を始めてしまった
    • 途中で頭真っ白
    • もう解けないときの頭真っ白とはまた違った
  • うーんと
    • 上位n位のアイテムを効率よく保持するには優先度つきキューを使うんだっけか
      • std::priority_queueを用意した
      • この時点で迷走が始まる
    • 番号の出てくる回数を保持しなきゃ
      • 配列が適切か。個数を#defineしておくか
        • CONTESTANTSに1,000,000を定義した
      • 待てよ? 渡されるイベント数の上限は高々50か
      • すかすかじゃないか...
        • std::mapに保持したほうがよいか
        • 結局定数を使わず放置してしまった
  • std::priority_queueにはどう保持しよう?
    • 要素を値としたstd::pairが妥当か
  • std::priority_queueでは大きいものほど優先されるんだっけ
    • 優先順位を決める基準が2つあるな...
    • キーを工夫するか...
      • 出現回数がより多いほうをより大きく設定しなきゃ
      • 回数が一緒の場合を考えて、その出現回数になったときの位置も畳み込まなければならないのか
        • 要素数は高々50だ
        • 大きいほうが優先される
        • よし、ならば50 - iとすればよいだろう
        • 出現回数は100倍しておこう
  • キーは以下のように計算した

提出した実装は以下(システムテストを通過)。

#define CONTESTANTS 1000000


class ContestWinner {
public:
  int getWinner(std::vector<int> events) {
    std::priority_queue<std::pair<int, int> > pq;

    std::map<int, int> counts;

    for (int i = 0, size = events.size(); i < size; i ++) {
      counts[events[i]] ++;

      pq.push(std::make_pair<int, int>(counts[events[i]] * 100 + (50 - i), events[i]));
    }

    return pq.top().second;
  };
};
  • グダグダだ...
    • まあいい(あまりよくない)
  • チャレンジフェーズにて他のコーダーの実装を見る
    • そうか、最大出現回数と要素の内容を記録しておけばよいのか
  • 終了後、試しに実装する(システムテストはしていない)
class ContestWinner {
public:
  int getWinner(std::vector<int> events) {
    int max_event, max_counts = 0;

    std::map<int, int> counts;

    for (int i = 0, size = events.size(); i < size; i ++) {
      counts[events[i]] ++;

      if (counts[events[i]] > max_counts) {
	max_event  = events[i];
	max_counts ++;
      }
    }

    return max_event;
  };
};
  • んー
    • あまり分かりやすい実装ではないな...?
    • 変数を2つ使っているからだろうか...?
  • そうだ
    • 提出した実装だと全要素をstd::priority_queueに保持してしまうな
    • std::priority_queueで上位からn位未満の要素を削除するのはどうするんだったっけ?
    • 調べてみる
      • ないみたい
      • ががーん

TwoRectangles

http://community.topcoder.com/stat?c=problem_statement&pm=12046&rd=14738

  • 550ということでビビリながら開いた
  • あ
  • まず、Separating Axis Theoremを使って、交差しているか(rectangle、segment、point)かしていないか(none)判断できそうだ
  if (A[2] < B[0] || B[2] < A[0] || A[3] < B[1] || B[3] < A[1])
    return "none";
  • Separating Axis Theoremは、二つの凸包を分かつ軸が存在する場合、その二つの凸包は交差しないことを表す定理
  • 以下の交差しない二つの矩形を考える


  • 二つの矩形の間に直線が存在すれば、二つの矩形は交差しない


  • この直線をSeparating Lineと呼ぶ
    • このとき、Separating Lineと直行する軸をSeparating Axisと呼ぶ
    • この場合、y軸がSeparating Axis
  • この問題のように矩形の各辺が軸に平行な場合、各軸で交差するかしないかをテストすればよい
  • x軸に直行したSeparating Lineが存在しないので、x軸はSeparating Axisではない


  • y軸に直行したSeparating Lineが存在するので、y軸はSeparating Axisである


  • つまり、軸ごとに考えてやればよい
    • これは射影という技法と関連する
  • 一般的には、Separating Axisは任意の軸であることを覚えておくとよい
    • こちらの図のほうがSeparating Axis Theoremをイメージしやすい


  • 二つの矩形が交差しているならば、重なった矩形を求めることができる


  • 重なった矩形は点、直線に縮退していることがある
    • 角と角が、縁と縁が重なっている等
    • x、y軸に射影した区間を使って判定すればよい

提出した実装は以下(システムテスト通過)。

class TwoRectangles {
public:
  std::string describeIntersection(std::vector<int> A, std::vector<int> B) {
    if (A[2] < B[0] || B[2] < A[0] || A[3] < B[1] || B[3] < A[1])
      return "none";

    std::vector<int> I = intersection(A, B);

    if (I[2] - I[0] == 0 && I[3] - I[1] == 0)
      return "point";

    if (I[2] - I[0] == 0 || I[3] - I[1] == 0)
      return "segment";

    return "rectangle";
  };

private:
  std::vector<int> intersection(std::vector<int> A, std::vector<int> B) const {
    std::vector<int> I;

    I.push_back(std::max(A[0], B[0]));
    I.push_back(std::max(A[1], B[1]));
    I.push_back(std::min(A[2], B[2]));
    I.push_back(std::min(A[3], B[3]));

    return I;
  };
};
  • テストを増やす方法を思いついた
    • AとBの内容を交換したものを追加する
    • 手間はかからず、倍のテストができた
    • 気休めだが、まあいい
  • SRM546 Div2 Medium(500) TwoRectangles - 赤コーダーになりたいを読む
    • をを
    • すごい
    • 簡潔だ
  • 各軸に射影した範囲の関係を以下のように判定している
    • 0: 重なっていない
    • 1: 範囲は端点のみにて重なっている
    • 2: 重なっている
  • この情報を元に、矩形の交差状況を判定している
  • 表にすると以下のようになる


  • をを
    • Separating Axis Theoremがやっていることは、noneとそれ以外を分かつこと
      • 表で見ると印象が全く違う
    • これは楽しい

FavouriteDigits

残りの40分を費やすも完成せず。後ほど3時間ほどかけて実装。

  • 与えられた数値N以上のある条件を満たす一番小さな数値を求める
  • んー
    • どこかで聞いたことがある
  • あ
  • 左側から1つずつ決めていく戦略を取ってみよう
  • 以下のようなイメージ


  • 0の扱いが面倒臭そうだ
    • んー
    • 文字列として処理してみる
  • std::istringstreamとstd::ostringstreamをstd::stringと数値の変換は以前考察した
    • 文字列から数値への変換は以下としていた
inline int stoi(const std::string& s)
{
  std::istringstream ss(s);

  int i;

  ss >> i;

  return i;
}
  • 今回はstd::istream_iteratorを使って実装してみた
inline long long stoll(const std::string& s)
{
  std::istringstream iss(s);

  std::istream_iterator<long long> it(ss);

  return *it;
}
  • をを
    • なんか好きだ
  • 探索をせずとも答えが出せる場合がある
    • count1、count2の双方とも0である場合
      • 答えはNとなる
  if (count1 == 0 && count2 == 0)
    return N;
    • Nが要求された数を満たす一番小さな数値より小さい場合
      • 答えは条件を満たす数値となる
  std::string s;

  if (digit1)
    for (int i = 0; i < count1; i ++)
	s.push_back('0' + digit1);
	
  if (digit2)
    for (int i = 0; i < count2; i ++)
	s.push_back('0' + digit2);

  std::sort(ALL(s));

  if (digit1 == 0)
    for (int i = 0; i < count1; i ++)
	s.push_back('0');
    
  if (digit2 == 0)
    for (int i = 0; i < count2; i ++)
	s.push_back('0');

  std::sort(s.begin() + 1, s.end());

  long long n = stoll(s);

  if (N <= n)
    return n;
  • 整列を二回している
  • digit1とdigit2の双方とも0でない場合


  • 全体を整列することによって


  • 最も小さい値を得る


  • digit1とdigit2の何れかが0である場合は、0を末尾に足すようにする


  • これは最も小さな値になるとは限らない(!)
  • 全体を整列してはいけない
    • この例だと00111、つまり111となってしまう
  • そこで、2文字目から後ろを整列してやると...


  • 最も小さい値を得る


  • Nがこの値より小さい場合は、この値を返せばよい
  • Nがこの値より大きい場合は探索を行う
    • 文字列が空の場合は条件を満たしたかチェックする
  if (s.empty())
    if (count1 > 0 || count2 > 0) {
      return INF;
    }
    else {
      return s;
    }
  • そうではない場合、先頭の数字が確定するまで探索する
  • 例えば


  • 先頭の数字が1であると仮定して、残りの数値を処理する


  • 成立しなかった場合は、次の数字を試す
    • 先頭を次の数字にした場合は残りの数値を0としなければならないことに注意


  • Nと同じ桁数で成立しなかった場合は、1桁多い数値で試す
    • Nが97であった場合は100

実装は以下(システムテスト済)。

#define INF "9999999999999999"


inline std::string lltos(long long n)
{
  std::ostringstream oss;

  oss << n;

  return oss.str();
}

inline long long stoll(const std::string& s)
{
  std::istringstream iss(s);

  std::istream_iterator<long long> it(iss);

  return *it;
}

class FavouriteDigits {
public:
  long long findNext(long long N, int digit1, int count1, int digit2, int count2) {
    if (count1 == 0 && count2 == 0)
      return N;

    std::string s;

    if (digit1)
      for (int i = 0; i < count1; i ++)
	s.push_back('0' + digit1);
	
    if (digit2)
      for (int i = 0; i < count2; i ++)
	s.push_back('0' + digit2);

    std::sort(ALL(s));

    if (digit1 == 0)
      for (int i = 0; i < count1; i ++)
	s.push_back('0');
      
    if (digit2 == 0)
      for (int i = 0; i < count2; i ++)
	s.push_back('0');

    std::sort(s.begin() + 1, s.end());

    long long n = stoll(s);

    if (N <= n)
      return n;

    for (s = lltos(N); ; s = '1' + std::string(s.size(), '0')) {
      std::string t = search(s, digit1, count1, digit2, count2);

      if (t != INF)
	return stoll(t);
    }
  };

private:
  std::string search(std::string s, int digit1, int count1, int digit2, int count2) const {
    if (s.size() < std::max(count1, 0) + std::max(count2, 0))
      return INF;

    if (s.empty())
      if (count1 > 0 || count2 > 0) {
	return INF;
      }
      else {
	return s;
      }

    for (char c = s[0]; c <= '9'; c ++) {
      std::string t = c + search(s.substr(1),
				 digit1, ('0' + digit1 == c) ? count1 - 1 : count1,
				 digit2, ('0' + digit2 == c) ? count2 - 1 : count2);

      if (stoll(t) < stoll(INF))
	return t;
      
      s = std::string(s.size(), '0');
    }

    return INF;
  };
};
  • 当初、[1, 1015 - 1]という条件を見て、結果もこの範囲で収まると思い込んでしまった
    • これは入力の条件であった
  • std::string(size_t n, char c)を習得した
    • 意外と便利だ
  • んー
    • グダグダではあるが、解けて嬉しい
    • 時間はかかったが、前回のSRMを考察してよかった