2013年8月4日日曜日

[TopCoder]自分の解いた問題一覧を出してみました。

GitHubのMarkDownが面白そうだったので、せっかくなのでTopCoderの自分の解いた問題を一覧で表示するようにしてみました。

https://github.com/yuki2006/topcoder

ローカル側でREADME.mdを生成し、githubにあげたらいい感じに見えるようになってます。

今まで、どの過去問を解いたかなどの管理が一苦労だったので、これだけでも十分です。



こちらから一部ソースを拝借しました。
https://github.com/fornwall/eclipsecoder-archive
投稿者 時刻: 0 件のコメント:
ラベル:

2013年8月2日金曜日

[TopCoder]SRM 587 Div2


Easy InsertZ

問題
http://community.topcoder.com/stat?c=problem_statement&pm=12700&rd=15699&rm=318350&cr=23018525

回答



Medium JumpFurther 

問題 




JumpFurther の方は、DP?　DFS?とか結構悩んだけど、貪欲で行ってbadStepになってしまったら、最初の１stepを進まずにとどまるようにすれば、最大になります。

結構いい問題。
投稿者 時刻: 0 件のコメント:
ラベル:

2013年7月28日日曜日

[TopCoder]SRM 586 Div 2

SRM 586 Div 2


Easy TeamsSelection

問題：
http://community.topcoder.com/stat?c=problem_statement&pm=12696&rd=15698

回答：

https://github.com/yuki2006/topcoder/blob/master/src/TeamsSelection.java


Midium PiecewiseLinearFunctionDiv2

問題：
http://community.topcoder.com/stat?c=problem_statement&pm=12698&rd=15698

回答：

https://github.com/yuki2006/topcoder/blob/master/src/PiecewiseLinearFunctionDiv2.java


どちらも問題の理解はちょっと難しかったけど、なんとか解けてよかった。
投稿者 時刻: 0 件のコメント:
ラベル:

2013年7月27日土曜日

倍精度と整数の対応

Wikipedia「倍精度」
http://ja.wikipedia.org/wiki/%E5%80%8D%E7%B2%BE%E5%BA%A6


double型で　整数の対応可能(longに変換可能）なのは2の 53乗まで、

ただし、２のべき乗だけなら　63乗まで可能。
投稿者 時刻: 0 件のコメント:
ラベル:

2013年7月26日金曜日

[Android]ActionBarSherlockからSupport Library v18 のActionBarへの移行

先日、新しいNexus7とともにAndroid 4.3 が発表されましたが、新しいOSとともに発表されるのが、Android SDKのバージョンアップ！

個人的にはこっちのほうが楽しみだったりします。


さて、今回　Android SDK付属の Android Support Libraryがv18 になり
なんと（やっと？）Action Bar UI に対応しました。
http://developer.android.com/tools/support-library/index.html

設定方法はこちらの「Adding libraries with resources」をどうぞ
http://developer.android.com/tools/support-library/setup.html


さて、わたしは今まで ActionBarSherlock　というありがたいライブラリを使っておりましたが、
http://actionbarsherlock.com/

公式で対応したということで移行処理をしてみました。



単純なものは、移行は簡単なのですが、もうちょっとGoogleさんには少し頑張ってもらいたかったところ。

相変わらず onCreate時にsetThemeを設定しないといけないみたいだし。

（自分が知ったかぎりもの）
各対応するもの表にしました。

（軽い動作確認は行いましたが、コードの正確性は保証いたしませんのでご注意ください。）


投稿者 時刻: 0 件のコメント:
ラベル:

2013年7月22日月曜日

[TopCoder]初心者にオススメ問題

今回も、自分用のまとめです。
気づいた時に更新します。


始めてTopCoderをする方用にオススメの練習問題。
（わかりやすい問題）



もちろんすべてDiv2、上な問題ほどわかりやすいはず。





投稿者 時刻: 0 件のコメント:
ラベル:

2013年7月20日土曜日

[TopCoder]SRM 585 Div 2

ブログを書くネタもあまりないので、プログラミングつながりということで 自分のまとめも兼ねてTopCoderのソースコードも公開して行きたいと思います。
 #本当は、ちゃんとしたアーカイブしたいけど

 ちなみに、ソースコードはGitHubのURLを貼るだけです。
 #リクエストがあれば何かするかも

 TopCoder自体は2年くらい前からやってましたが、スコアは低いです。頑張ります。

 というわけで早速。


 SRM 585 Div 2

 Easy

 LISNumberDivTwo
http://community.topcoder.com/stat?c=problem_statement&pm=12446

 ソース:
 https://raw.github.com/yuki2006/topcoder/master/src/LISNumberDivTwo.java 


 Medium 

TrafficCongestionDivTwo
http://community.topcoder.com/stat?c=problem_statement&pm=12697

 ソース:
https://github.com/yuki2006/topcoder/blob/master/src/TrafficCongestionDivTwo.java



特に、TrafficCongestionDivTwo の方は、興味深かったので説明書きます。

本番で書いたコードはなんとなく見つけた法則でのメモ化再起なんですが
SRM終了後に
他の人のエレガントなアルゴリズムを考えていた時に、見つけたアルゴリズムです。
（System Testには通りましたが、理論的に説明できません。。）

しかも、「倍数の証明 ジェネレータ」
http://tma.main.jp/baisuu/

というさらに興味深いサービス見つけたので、更にはかどりました。


高さh+1の完全二分木のノード数 は 2^h -1 です。

ここで問題でいう１つのパスを　葉のノード　→その上のノード　→右下の葉のノード
を順番にやっていくと最小のパス集合数になるのではと思いました。
（理論的に証明できません。。


ここで、 hが偶数のとき, ノード数は3の倍数になることの証明はこちら

2^(2n)  -1 = 4^n  -1 が 3の倍数であることの証明
http://tma.main.jp/baisuu/baisuu.php?eq=4%5En-1&num=3


また hが奇数の時、ノード数は3で割ったら1余る証明はこちら　（少し変形してます

2^(2n+1)  -1 -1 が  3の倍数であることの証明
http://tma.main.jp/baisuu/baisuu.php?eq=2%5E%282*n%2B1%29-2+&num=3


つまり、
hが偶数の時は、先ほどの長さ3のパスの組み合わせで構成可能
hが奇数の時は、長さ3のパスの組み合わせで構成すると根のノードだけ残る（あまり１）

つまり、
  (2^h -1)/3 の切り上げの値が　最小のパス集合の数と等しくなるではないかと思いました。

2^h-1 % 3のあまりの最大値は１なので

切り上げを表現するためにテクニカルな方法を用いて+2にしました
つまりreturn文はなんと一行で表現出来ました。

return ((long) Math.pow(2, treeHeight + 1) - 1 + 2) / 3;

ツッコミお待ちしております。




投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)