SRM 548 Div II - agwの日記

Single Round Match 548 Round 1

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

250に4分。500に1時間ほどかけ、完成しなかった。合計243.22点。レートは993から1010へ。緑コーダー。

	Problem	Status	Points
250	KingdomAndDucks	System Test Passed	243.22
500	KingdomAndTrees	Opened	0.00
1000	KingdomAndPassword	Unopened

250に4分。243.22点
500に70分
- 前半40分かけた実装は失敗と確信
- 考え直したが結局解けなかった
また250しか解けなかった
- レートが落ちてもおかしくない
- 2問必ず通すようにしなければならない
次回の目標
- 2問通す

KingdomAndDucks

http://community.topcoder.com/stat?c=problem_statement&pm=11985&rd=15170

4分。243.22点。

最頻値の登場回数と値の種類の積を求める
- 解くだけ

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

class KingdomAndDucks {
public:
  int minDucks(std::vector<int> duckTypes) {
    std::map<int, int> map;

    EACH(it, duckTypes)
      map[*it] ++;

    int s = 0;
    
    EACH(it, map)
      s = std::max(it->second, s);

    return s * map.size();
  };
};

KingdomAndTrees

http://community.topcoder.com/stat?c=problem_statement&pm=11967&rd=15170

40分間実装を行った。提出前にシステムテストで必ず落ちると確信し、提出しなかった。その後30分考え直すも全く検討も付かなかった。

40分間の実装を終え、提出しようとした
この問題ではサンプルを比較的多く思いついていた
- 提出直前に思いついた1 1 5 1 1という問題の答えは4であるはずなのだが、合わない
- 2 2 5 2 2、3 3 5 3 3等も思いついたが合わない
ここで提出を断念
違う方法論で考え始める
- 30分全く分からないまま終了

チャレンジフェーズにて見た実装は二分探索であった
- 理解が出来ない
Div IIトップはすごいに違いないと思い、その実装を読むことにした
をを
- 圧倒された
- 簡潔だ

以下はその実装を元に自分なりに整理したもの(システムテスト済)。

class KingdomAndTrees {
public:
  int minLevel(std::vector<int> heights) {
    int l = 0, r = std::numeric_limits<int>::max();

    if (check(heights, l))
      return l;

    while (l + 1 < r) {
      int m = (l + r) / 2;

      if (check(heights, m)) {
	r = m;
      }
      else {
	l = m;
      }
    }
    return r;
  };

private:
  bool check(std::vector<int> heights, int x) {
    for (int i = 0, size = heights.size(), lb = 0; i < size; i ++, lb ++) {
      int a = std::max(1, heights[i] - x), b = heights[i] + x;

      if (b < lb)
	return false;
      
      lb = std::max(a, lb);
    }
    return true;
  };
};