読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

競技プログラミング

今月のCodeChef(http://www.codechef.com/MARCH12/)は、5問解けた。簡単な問題が追加されたのでなんとか一問解くという目標が意味なくなったなw

Spoon in Matrix(http://www.codechef.com/MARCH12/problems/SPOON)

Ruby正規表現でチェックした。Rubyおせえ。
s[i]='S' and s[i+1]='P' and ...というのがダサいので、practice easyに移ったあと、長さ5の文字列を32進数とみなし比較する方法も試してみた。
セジウィックにラビン・カープという検索文字列のハッシュ値を比較するのがあったので。

Free Shuttle Service(http://www.codechef.com/MARCH12/problems/SHUTTLE)

パッと見、オイラーのphi関数 && ソースコードの制限が5万バイトなので、解答を埋めこませてもらったw
こういうの、最初の小さい数字でローカルで試してみて、それを元にオンライン整数列大辞典(http://oeis.org/?language=japanese)に頼るのもあるよね。
後からちゃんとphi関数を計算するプログラムも書いたが、0秒では終わらず。

Home Delivery(http://www.codechef.com/MARCH12/problems/HDELIVER)

最初に与えられたグラフの連結成分を求めておけば、各クエリーの処理はO(1)。
グラフの連結成分を求めたことがなかったので、セジウィックの「アルゴリズム」からコードをパクって幅優先探索で求める。
この辺、勉強になった。深さ優先でも同じとか。自分は基本ができていないのさー

Lucky Number(http://www.codechef.com/MARCH12/problems/LUCKY2)

まず、0からRまでのなかでF(X)が幸運数となるXの数G(R)を求めよう。求められれば、G(R)-G(L-1)で解答は求まる。
いきなりは難しいので、0から99999..9(n桁)をまず考えると、
F(X)=7となる数は、n個の場所(桁)から7個選びそこに{4,7}を置いていき、残りの箇所に{0,1,2,3,5,6,8,9}を置いていく組み合わせの数だね。
これって、(2+8)^nを展開した時のn_C_7*2^7*8^(n-7)だね。8は2^3だから冪は2で考えるとよさげ。最初に(2+2^3)^nの展開を計算しておこう。

さて、具体的に、R=5509111のときのG(R)は
0から999999
1000000から1999999
2000000から2999999
3000000から3999999
4000000から4999999
5000000から5509111
と区切って考える。
0から999999の中でF(X)=4となるものの数は6_C_4*2^4*8^(6-4)個ある。F(X)=7は無いね、6桁だから。
2000000から2999999も3000000から3999999も同じ個数だ。問題は、4000000から4999999だ。
というのも最初の桁が4なので、F(X)=4を求めてはダメで代わりにF(X)=3の数を求める必要がある。
次に、5000000から5509111だが、この場合は0から509111までのF(X)=4となるXの数を求めればいいね。(7000000から7509111なら0から509111までのF(X)=3となるXの数になるのに注意)
あれ?これってさっき同じ事をやったような・・・
ということで再帰的に書いてAC!

ちなみに最終日の終了4時間前に解けたので、非常に疲れました。しかも間違いがわからずプログラムがうんこになった、ひどすぎ。
結局、最初に(2+2^3)^nの展開を計算するところだったとは・・・

Xor it(http://www.codechef.com/MARCH12/problems/XOR)

問題は、n=10^5個の整数が与えられるのでxor演算して小さい順に出力してね、K=MAX25万個。
というシンプルなもので、どうしても解きたいと思った問題。全整数のペアを考えると0.5*10^10で明らかにTLEだよなあ。つーかメモリ足りなくね?なのだが・・・
xor演算なので2進法で考えるとよさげ。また、例えば、
00101
00110
11001
という3数があったら、最上位bit1の数と最上位bit0の数をxorしても小さくならないことがわかるので、与えられた整数の集合を上位m bit同じものでグルーピングしていけばよさそう。そのグループ内でxorすれば、その上位ビットは消えるので。
つまり次のような最大のmを求めることにする:
与えられた整数の集合を上位m bit同じものでグルーピングし、各グループのペア数(グループの元の数をxとするとx_C_2=x*(x-1)/2))の総和が25万以上。
TLE喰らうようだったら最終的にバイナリサーチしようと思っていたが、mを1ずつ増やしてチェックしてOKだった。
さて、そのようなmが求められたら、グループ内でxorした結果を別の配列に保持しておき、全グループのxorが終わった所でsortし、小さい順に出力する。
ちなみに提出したプログラムは、n=k*(k-1)/2の場合にバグがあったがそのような入力は用意されて無かったようだ。

来月もがんばろう〜