Android de memo

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

どちらも問題の理解はちょっと難しかったけど、なんとか解けてよかった。

2013年7月27日土曜日

倍精度と整数の対応

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

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

ただし、２のべき乗だけなら　63乗まで可能。

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を設定しないといけないみたいだし。

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

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

2013年7月22日月曜日

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

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

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

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

SRM 363 Easy MirroredClock

http://community.topcoder.com/stat?c=problem_statement&pm=8058&rd=10777
SRM 573 Easy SkiResortsEasy

http://community.topcoder.com/stat?c=problem_statement&pm=12469&rd=15493
SRM 572 Easy EasyHomeWork

http://community.topcoder.com/stat?c=problem_statement&pm=12387&rd=15492

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;

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

2013年7月10日水曜日

if -else を教えてる時に・・。

早速ですが、このコードの間違いを探してください。
（答えは本文で）

とある機会で、初歩からJavaプログラミングを教える機会があって、
前でプロジェクターで映しながら、こうやったらこうできますよみたいなハンズオンで説明してたんです。

文の最後には「セミコロンが要りますよ」とか基本的なことから教えて、

四則演算や%も教えました。

次に
if文を教えようと、奇数偶数を判定するようなコードを書いて、前に写して、
受講者の方に「こんなコード書いてみてください」と言って書いてもらったのですが、

そこ、受講者の方から
「奇数の時も偶数ですと出るのですが・・・」と質問されました。

そこで受講者の方が書いたのは、最初に載せたコードです。

私はパッと見た時に、すぐに気づきませんでした。。

わかりやすいようにフォーマッタをかけたのは下のコードです。