SRM 543

Single Round Match 543 Round 1 - Division II

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

250に4分。チャレンジされ撃墜。

残り時間を500に費やす。システムテストで落ちた。

チャレンジ2回成功、1回失敗。レートは830から780へ。白コーダー。

Problem Status Points
250 EllysTSP Challenge Succeeded 0+100-25
500 EllysXors Failed System Test 0
1000 EllysThreeRivers Unopened
  • 250に4分。245.20ポイント
    • チャレンジされ撃墜
  • 残りを500に費やす
    • コーディングフェーズ終了間際に提出。190.44ポイント
    • 反復の条件が誤っており、システムテストで落ちた
  • チャレンジフェーズ前に250の実装の誤りに気付く
    • 同様の誤りをしている実装にチャレンジ。2回成功。100ポイント。1回成功。-25ポイント
  • 結局75ポイント
    • レートがさらに下がっていく...
  • 次回の目標
    • 250を通す

EllysTSP

http://community.topcoder.com/stat?c=problem_statement&pm=11907&rd=14735

4分。考慮していないケースがあった。チャレンジされ撃墜。

  • 実装を終え、テストもパスしたので投稿した

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

class EllysTSP {
public:
  int getMax(std::string places) {
    size_t n = std::count(ALL(places), 'C');

    return std::min(n, places.size() - n) * 2 + 1;
  };
};
  • チャレンジフェーズの前に、いつでも奇数になってしまうことに気付いた
    • 入力が"CVCV"であれば、答えは4になるはず
      • V(村)とC(都市)が同じ数だけ登場するケースを考慮に入れていなかった
  • 同様の誤りがある実装にチャレンジした
    • まず失敗した
      • 注意散漫過ぎだ
    • その後、2回成功した

以下は書き直した実装(システムテスト済み)。

class EllysTSP {
public:
  int getMax(std::string places) {
    int size = places.size();

    int n = std::count(ALL(places), 'C');

    if (n == size - n) {
      return size;
    }
    else {
      return std::min(n, size - n) * 2 + 1;
    }
  };
};

EllysXors

http://community.topcoder.com/stat?c=problem_statement&pm=11907&rd=14735

70分費やした。反復の終了条件を誤り、システムテストで落ちた。

  • ビットごとにXORをする戦略を立てた
    • 立っているビットが奇数個であれば1となる
    • 立っているビットが偶数個であれば0となる
  • 0から15までを二進数で書き出してみた


  • L = 3、R = 10とするとこんな感じ


  • この結果は二進数で1000、つまり8となる
  • それぞれの桁のビットには周期性がある


  • 塊がLとRに内包されている場合は、個数と塊の中のビット数を乗じてやる
    • 最下位ビットであれば1、2ビット目は2、3ビット目は4
    • ビットの位置をiとして表すと、2i(最下位ビットのiは0)
  • 塊が部分的に内包されている場合は、交差している範囲を考えてやる
    • 以下のようにすると考えやすい


  • L = 3、R = 10とするとこんな感じ


  • 例えば最下位ビットでは塊を3つ内包している

実装しよう(システムテストを通らない)。

class EllysXors {
public:
  ll getXor(ll L, ll R) {
    ll result = 0;

    for (ll a = 2, b = 1, i = 0; ; a *= 2, b *= 2, i ++) {
      ll l = L / a * a, r = R / a * a, n = 0;

      if (l <= r)
	n += (r - (l == L ? l : l + a)) / a * b;

      if (L >= l + b)
	n += l + a - L;

      if (R >= r + b)
	n += R - r - b + 1;

      if (n % 2)
	result |= 1LL << i;

      if (a >= R)
	break;
    }
    return result;
  };
};
  • システムテストで落ちた
    • 反復の終了判定を間違えていた
    • a >= Rではなく、a > Rであった

以下はシステムテストを通る実装。

class EllysXors {
public:
  ll getXor(ll L, ll R) {
    ll result = 0;

    for (ll a = 2, b = 1, i = 0; ; a *= 2, b *= 2, i ++) {
      ll l = L / a * a, r = R / a * a, n = 0;

      if (l <= r)
	n += (r - (l == L ? l : l + a)) / a * b;

      if (L >= l + b)
	n += l + a - L;

      if (R >= r + b)
	n += R - r - b + 1;

      if (n % 2)
	result |= 1LL << i;

      if (a > R)
	break;
    }
    return result;
  };
};
xor.py:

#!/usr/local/bin/python3.2 -t

if __name__ == '__main__':
    for i in range(0, 16+1):
        s = 0
        for j in range(0, i+1):
            s ^= j
        print('%2d %8s' % (i, bin(s)[2:]))
> ./xor.py
 0        0
 1        1
 2       11
 3        0
 4      100
 5        1
 6      111
 7        0
 8     1000
 9        1
10     1011
11        0
12     1100
13        1
14     1111
15        0
16    10000
  • すごい!
  • 解説のまねをして書き出してみる
    • 自分の分かりやすい方法から始めてみよう
  • nを4の倍数とする
    • n % 4が0のときは、n
    • (n + 1) % 4は1である。そのとき、n ^ (n + 1)は1
    • (n + 2) % 4は2である。そのとき、1 ^ (n + 2)はn + 3
    • (n + 3) % 4は3である。そのとき、(n + 3) ^ (n + 3)は0
  • この結果を元に、xが任意の自然数である場合を考えてみよう
    • x % 4が0のときは、x
    • x % 4が1のときは、1
    • x % 4が2のときは、x + 1
    • x % 4が3のときは、0
  • これは勉強になった
  • SRM 543 - firewoodの練習帳 - TopCoder部を読む
    • 「ある偶数と次の奇数とのXORは2n^(2n+1)=1」
    • をを
    • なるほど、こういうことか


  • これが2回繰り返されると0となる
  • 書き出してみよう


  • n' = n + 1とおくと


  • つまり


  • また、以下のように書き出す方法もあった


  • Div IIで500の問題はDiv Iで250の問題のはずだ
    • Div Iの人達はこれを10分とかで解くのだろう
    • んー
    • 何か目標が立てられそうだ