2012-05-26
SRM 543
Div1 Easy (250) EllysXors
問題
- LからRまでの全数のXORを求めよ
方針
- 2個単位でゼロになるのかな
- 合わない...
- (終了後)
- 紙に列挙してようやく理解
- ある偶数と次の奇数とのXORは2n^(2n+1)=1
- 1 XOR 1 = 0なので、ある偶数2nから連続する4数のXORはゼロ
- ループで計算する際、奇数まで計算した時点で、残りが4以上なら飛ばすことができる
- また0からxまでのXOR f(x)は、4n,1,4n+3,0の繰り返しとなるので、f(L-1)^f(R)でも求まる
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_543/EllysXors.cpp
Div2 Easy (250) EllysTSP
問題
- 町と村の数が与えられる
- 町と村を交互に移動する場合、最大何回移動できるかを求める
方針
- 読解問題
- 少ないほうをL、多いほうをMとする
- 整理すると、L+min(L+1,M)回
- https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_543/EllysTSP.cpp
結果
0pt 660th rating 1414 -> 1333
適正レートに落ちてしまった。
2個単位で1になるのは即気づくべき。なんとunsigned intだと40億回ループでも間に合うらしい。そこを突いてくるのはすばらしい。
div2 easyは差が2以上のときと同数のときのテストケースが通ればOK。
コメントを書く
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120526
リンク元
- 42 https://topcoder-g-hatena-ne-jp.jag-icpc.org/
- 2 https://topcoder-g-hatena-ne-jp.jag-icpc.org/diarylist
- 2 http://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CFYQFjAB&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120106/1325873167&ei=sWTDT46yAYSZiQeCt4CcCg&usg=AFQjCNFrbh5G5KRUfLYY3ZwhYI51ziANvg&sig2=ySYSnlfjoEJVQpzwlrfDQA
- 1 http://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CFMQFjAA&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20111027/1319732512&ei=bVPDT9n7AqyOmQXM4ei1Cg&usg=AFQjCNEni1jQFLxa-xdo1elZIL8RP3tISQ&sig2=QLnZP-85Ux-Nwrrs8EHHlw
- 1 http://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CFMQFjAA&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20111027/1319732512&ei=OFnDT8SUJaHhmAW5_q1W&usg=AFQjCNEni1jQFLxa-xdo1elZIL8RP3tISQ&sig2=nKwkmbTqap7ay2oARH5_6Q
- 1 http://www.google.co.jp/url?sa=t&rct=j&q=b.kingdom ゲーム&source=web&cd=2&ved=0CGUQFjAB&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120428/1335623971&ei=W3rET8OMN-7LmAXDrry_Cg&usg=AFQjCNERKYHZksVGrCeR_ws_lRC15CYtsg&sig2=S3SJQEsjThbJDlIk_i_DOw
- 1 http://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CFoQFjAC&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/firewood/20120526/1338037995&ei=ca3ET8YOo4mZBfanjaoK&usg=AFQjCNEnTyPEAtgN_FFHyIihljehZ3Sn4g&sig2=ODmBuNTpzySf8kvRe_4O_g