hotpepsiの練習帳

SRM 543

22:13

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。