SRM 439

Single Round Match 439 Round 1 - Division II

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

練習。250に12分。問題を理解しておらず、WA。500に22分。こちらも見落としがあり、WA。

全敗だったが、時間中頭が真っ白という状態ではなかった。何故か満足感が高かった。

Problem Status Points
250 SquareOfDigits Opened WA
500 PouringWater Opened WA
1000 PalindromeFactory Unopened
  • 250に12分
    • 問題を見誤っていた。WA
  • 500に22分
    • 貪欲法を使った
    • コーナーケースに引っかかり、WA

SquareOfDigits

http://community.topcoder.com/stat?c=problem_statement&pm=10395&rd=13747

12分。問題を見誤っていた。投稿してシステムテストに落ちた。

  • 問題を読み終わって実装が全く想像できず、頭が真っ白になりかける
  • 同一行にて同じ数値のペアがあるかどうか探すのだよな
    • そうか、行内で数値のペアが見つかったら、 その後の行の同じ位置に同じ数値があるか調べればよさそうだ
      • この時点で正方形の探索ではなく、角の数値が等しい任意の矩形の探索に思考がすり替わってしまった
  • 実装してシステムテスト。WA
  • 正方形が条件の一つであることに気付き、実装し直す

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

class SquareOfDigits {
public:
  int getMax(std::vector<std::string> data) {
    int s = 1;

    int w = data[0].size(), h = data.size();

    for (int i = 0; i < h; i ++)
      for (int j = 0; j < w; j ++)
	for (int k = j + 1; k < w; k ++)
	  if (k - j + i < h)
	    if (data[i][j] == data[        i][k] &&
		data[i][j] == data[k - j + i][j] &&
		data[i][j] == data[k - j + i][k])

		s = std::max((k - j + 1) * (k - j + 1), s);
    
    return s;
  };
};

PouringWater

http://community.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747

22分で完成。投稿してシステムテストで落ちた。

  • 貪欲法な気がした
  • 一先ずN = 13をシミュレーションしてみた


  • 3本のボトルにまとまった
  • 2^n本のボトルは1つにまとまるようだ
    • K = 1なのであれば、ボトルを3本足してやればよさそうだ


  • K = 2の場合にはまず左側のボトルを8本をまとめてしまう
    • 残った5本のボトルは一つにまとめなければならないので、やはりボトルを3本足してやる


  • やはり貪欲法でよさそうだ
    • K = 3の場合もシミュレーションしてみる


  • まず8本のボトルをまとめる
    • 次に4本のボトルをまとめる
      • 残りは1本
  • 合っていそうだ
    • 実装しよう
  • ボトルを何本足しても成立しないときは-1を返すように書いてあった
    • 成立しないことがないように感じた
    • 迷ったがそのまま投稿した
      • 結果、やはり成立しないことはないようだ
  • システムテストでWA
    • N <= Kの場合を考えていなかった
      • Kを1つずつ減らして0にすることで頭が一杯になっていた
    • 書き足してシステムテストを通した

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

class PouringWater {
public:
  int getMinBottles(int N, int K) {
    return buy(N, K);
  };

  int buy(int N, int K) const {
    if (N <= K) {
      return 0;
    }
    else if (K == 1) {
      int a;

      for (a = 1; a < N; a *= 2)
	;

      return a - N;
    }
    else {
      int a;

      for (a = 1; a * 2 <= N; a *= 2)
	;
      
      return buy(N - a, K - 1);
    }
  }
};
  • log2とpowを避けようとして、微妙な実装をしてしまった
    • aとbとして書き出してみよう
  int a;

  for (a = 1; a * 2 <= N; a *= 2)
    ;

  int b;

  for (b = 1; b < N; b *= 2)
    ;
  • aとbは以下となる
N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a 1 2 2 4 4 4 4 8 8 8 8 8 8 8 8 16
b 1 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16
  • つまり
    • aはN以下の最大の2の冪乗の数
    • bはN以上で最小の2の冪乗の数
  • std::lower_bound、std::upper_bound的なノリを狙ったが、ひたすら分かり辛い
    • 後で考えよう