SRM 551 Div II

Single Round Match 551 Round 1

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

250に6分。500に1時間ほどかけ、完成しなかった。合計239.62点。レートは1096から1095へ微減。緑コーダー。Room 62。

Problem Status Points
250 ColorfulBricks System Test Passed 239.62
550 ColorfulChocolates Opened 0.00
1000 ColorfulCupcakesDivTwo Unopened
  • 250に6分。239.62点
  • 500に1時間ほどかけ、完成しなかった
    • またやってしまった...
  • 次回の目標
    • 2問通す

ColorfulBricks

http://community.topcoder.com/stat?c=problem_statement&pm=12136&rd=15173

6分。239.62点。

  • レンガの種類を数え上げる
    • 2種類であれば、答えは2
    • 1種類であれば、答えは1
    • それ以外の場合、答えは0

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

class ColorfulBricks {
public:
  int countLayouts(std::string bricks) {
    std::set<char> set;

    EACH(it, bricks)
      set.insert(*it);

    int size = set.size();

    return (size <= 2) ? size : 0;
  };
};
  • コンテナのコンストラクタにイテレータを指定できることを忘れがちだ
    • 今回も忘れた

後ほど行った実装は以下(システムテスト済)。

class ColorfulBricks {
public:
  int countLayouts(std::string bricks) {
    std::set<char> set(ALL(bricks));

    int size = set.size();

    return (size <= 2) ? size : 0;
  };
};
  • すごく重要なことなのに、実践で出てこない

Effective STL―STLを効果的に使いこなす50の鉄則

Effective STL―STLを効果的に使いこなす50の鉄則

  • 作者: スコットメイヤーズ,Scott Meyers,細谷昭
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2002/01
  • メディア: 単行本
  • 購入: 9人 クリック: 155回
  • この商品を含むブログ (95件) を見る

ColorfulChocolates

http://community.topcoder.com/stat?c=problem_statement&pm=12137&rd=15173

1時間かけ、時間切れ。

  • チョコレートが高々1回しか現れない場合は、無視してよい


  • この場合、AとDが現れるのは高々1回


  • BとCについて考えればよい
    • Cについて考えてみる
  • まず、Cの取る範囲の中央に集めればよいように考えた


  • 次の場合も考える


  • この場合の中央は整数値にならない
    • 実数を使った


  • 求めたcの周りにCを集めるシミュレーターを書いた
    • 答えが全然合わない
  • 当然だった
    • この方法は分布を全く加味していないからだ
  • 以下は分布に偏りがある例


  • 次に、コストを算出することを考えた
    • まず点を定義し、その点からチョコレートへの距離を足し込んだものとした


  • シミュレーターに反映
    • 正解率は上がったが、合わない答えがある
  • ここで時間切れ
  • 考えてみると、当然だった
    • ここでのコストは以下のように算出している
      • xはコストを算出する点。x_iはチョコレートの位置


  • 算出すべきコストは以下であった


  • V(i)はチョコレートiが使われるかどうかを表す関数とし、0か1を取る
    • 0-1確率変数みたいなものだ
  • 以下を満たすV(i)を求めたい
    • KはmaxSwapsとして与えられる係数だ


  • だが、これでもうまくいかない
    • 点に集める、という発想がよくなかった
  • チョコレートを集める個数と場所を予め決めてしまおう
    • Cを3枚集める場合は、以下のようにコストを算出する
    • 以下の場合のコストは、7


  • 集める場所を1つ右にずらした場合は以下のようになる
    • この場合のコストは、6


  • このように集める場所をずらして、Cを3枚集めた場合のコストを計算してやる
  • 同様に、Cを2枚集める場合を考える
  • 集める場所だけではなく、集めるCもずらしていく
    • 以下の場合のそれぞれのコストは4と7



  • 集める場所をずらす
    • 以下の場合のそれぞれのコストは4と5


これを実装したものが、以下(システムテスト済)。

class ColorfulChocolates {
public:
  int maximumSpread(std::string chocolates, int maxSwaps) {
    int result = 0;
    
    int size = chocolates.size();
    
    std::set<char> set(ALL(chocolates));

    EACH (it, set) {
      std::vector<int> pos;

      for (int i = 0; i < size; i ++)
	if (chocolates[i] == *it)
	  pos.push_back(i);

      for (int l = 0; l < size; l ++)
	for (int r = l; r < size; r ++) {
	  int len = r - l + 1;

	  if (len > pos.size())
	    break;

	  for (int i = 0; i < pos.size(); i ++)
	    if (i + len - 1 < pos.size()) {
	      int swaps = 0;

	      for (int j = 0; j < len; j ++)
		swaps += std::abs(l + j - pos[i + j]);

	      if (swaps <= maxSwaps)
		result = std::max(len, result);
	    }
	}
    }
    return result;
  }
};
  • touristさんの実装を多いに参考にした
    • 10分以内で実装しているのか...
  • Red CoderはDiv II Medium相当の問題を10分以内で解くのだな
    • 次回からDiv II Mediumを開く前に、超頑張れば10分以内で解ける程度の問題だと暗示をかけることにする
    • そうすれば1時間以内には解けるようになるのではないかと生暖かく期待している