2012 TCO Algorithm > Round 1B

2012 TCO Algorithm > Round 1B

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

250のみ提出。システムテストを通らず、0点。レートは1019から961へ。何とか緑コーダーを維持。Room 22

Problem Status Points
250 FoxAndKgram Failed Sys. Test 0.0
500 FoxAndDoraemon Opened 0.0
1000 FoxAndPhotography Unopened 0.0
  • 250のみ提出
    • システムテストで落ちた。凡ミスとかそういうレベルのミスではないのが痛い
  • 初めて赤コーダーと同じ部屋になった
    • 問題を提出するのが恐ろし速くてビビった
    • しかも全問通していた。すごい
  • スタバでやってみた
    • リラックスしてできた感が大きい
    • 集中はできていなかったように思う
    • チャレンジ中にWi-Fiが切れた(2時間でWi-Fiの接続が切れるよう推測)
  • 次回の目標
    • 2問通す(次回はSRMなので、DIV II相当の難易度)

FoxAndKgram

実装に25分。155.98/250を獲得。システムテストで落ち、結果0点。

#define ALL(x) (x).begin(), (y).end()
      • 開いたマクロは発想になかった
      • std::sort、std::count等の記述が圧倒的に速かった
      • 実装が読みやすくなった
      • 正直こういうマクロはあまり好きではなかったのだが、今後少しずつ導入しようと思う
  • コードリーディング
    • 赤コーダーの実装が最も簡素であった
      • 考えられる範囲の答えを反復し、シミュレーションを行って妥当性を確認する実装であった
      • 初めて参加したSRM 535のFoxAndIntegersと同様のアイデアであることを再認識
        • このパターンを実装する前に計画できるようにしたい

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

class FoxAndKgram {
public:
  int maxK(std::vector<int> len) {
    int size = len.size(), total = std::accumulate(ALL(len), 0);

    total += size / 2;

    int ip = 0;

    for (int i = 1, c; i * i <= total; i ++) {
      c = std::count(ALL(len), i);

      for (int j = 1; j * j < i; j ++)
	if (j == i - j - 1) {
	  c += std::count(ALL(len), j) / 2;
	}
	else {
	  c += std::max(std::count(ALL(len), j), std::count(ALL(len), i - j - 1));
	}
      
      if (c >= i)
	ip = c;
    }
    
    return ip;
  };
  • k-gramは長さkの列がk列並んでいる
    • イメージとしてはこんな感じ


    • つまり正方形を成す
    • ならば面積はk * k
    • そのため最大のkは与えられた鉛筆の長さの合計に近い値の平方根の値に近いのではないか
      • 列は長さ1の空白を含む場合がある
        • 空白は鉛筆に挟まれていなければならない
        • 鉛筆の長さの合計に半分の鉛筆の数を足したのが最大の面積となりうる
        • つまり、kは以下の不等式を満たす1以上の範囲に収まる


        • 外側の反復の終了条件ではi * i <= totalとした
          • SRM 535でのコードリーディングと考察が実って嬉しい
        • ここまではとてもよかった
      • 内側の反復の終了条件でミス
        • 外側の反復の終了条件のノリで記述して間違えていることに気付かなかった
        • これじゃあ、j < √iとなってしまう
        • 実装しなければならなかったのはj + j + 1 <= iなのであった
      • 最大のkの更新でミス
        • ipをiで更新しなければならないのにcで更新してしまった
    • 合計がiとなる長さjの鉛筆とi - j - 1の鉛筆の数を求める
      • std::maxではなく、std::minでなければならなかった
        • 間違えてはいたけど、この実装結構好き
        • 任意の整数のリストから(x, y)のペアが何組あるか調べるのに良さそうだ(ただし、x ≠ yのとき)
  std::min(std::count(ALL(list), x), std::count(ALL(list), y));

上述を考慮して書き換えた実装は以下。

class FoxAndKgram {
public:
  int maxK(std::vector<int> len) {
    int size = len.size(), total = std::accumulate(ALL(len), 0);

    total += size / 2;

    int ip = 0;

    for (int i = 1, c; i * i <= total; i ++) {
      c = std::count(ALL(len), i);

      for (int j = 1; j + j + 1 <= i; j ++)
	if (j == i - j - 1) {
	  c += std::count(ALL(len), j) / 2;
	}
	else {
	  c += std::min(std::count(ALL(len), j), std::count(ALL(len), i - j - 1));
	}

      if (c >= i)
	ip = i;
    }
    
    return ip;
  };
};
      • 反復の内側でstd::countするのはすごく無駄
class FoxAndKgram {
public:
  int maxK(std::vector<int> len) {
    int size = len.size(), total = std::accumulate(ALL(len), 0);

    total += size / 2;

    std::map<int, int> dist;

    for (std::vector<int>::iterator it = len.begin(); it != len.end(); ++ it)
      dist[*it] ++;

    int ip = 0;

    for (int i = 1, c; i * i <= total; i ++) {
      c = dist[i];

      for (int j = 1; j + j + 1 <= i; j ++)
	if (j == i - j - 1) {
	  c += dist[j] / 2;
	}
	else {
	  c += std::min(dist[j], dist[i - j - 1]);
	}

      if (c >= i)
	ip = i;
    }
    
    return ip;
  };
};
    • 赤コーダーの実装を真似て、答えを反復しシミュレーションを行う実装をしてみる(システムテスト済)
class FoxAndKgram {
public:
  int maxK(std::vector<int> len) {
    int size = len.size();

    for (int i = 50; i >= 1; i --) {
      std::vector<bool> used(size, false);
      
      int c = std::count(ALL(len), i);
      
      for (int j = 0; j < size; j ++)
	for (int k = j + 1; ! used[j] && k < size; k ++)
	  if (! used[k] && len[j] + len[k] + 1 == i) {
	    used[j] = used[k] = true;
	    
	    c ++;
	  }

      if (c >= i)
	return i;
    }
    return 0;
  };
};

FoxAndDoraemon

  • 30分ほど考えても実装方法に検討も付かなかった
  • 後でやる