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(都市)が同じ数だけ登場するケースを考慮に入れていなかった
- 入力が"CVCV"であれば、答えは4になるはず
- 同様の誤りがある実装にチャレンジした
- まず失敗した
- 注意散漫過ぎだ
- その後、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; }; };
- んー
- 皆このように解いているのだろうか
- よく読んでいるブログを参考にしよう
- 解法が似通っている
- 自分のような実装をしている人はいない
- nodchipのTopCoder日記 - TopCoder部を読んでみる
- !
- 4の周期性を持っているようだ
- 実験してみる
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分とかで解くのだろう
- んー
- 何か目標が立てられそうだ