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

重複組み合わせの動的計画法での解法

蟻本で解説がよくわからなかったのでメモ

問題はn種類の品物があり、i番目の品物はa[i]個(配列)ある。同じ種類の品物は区別できない。これらの品物からm個選ぶときの組み合わせの総数を求めろ。

dp[i+1][j]をi番目までの品物からj個選ぶ組み合わせの総数としてdp[n][m]に解が入る。
dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-1-a[i]]が成り立つのがこれが成り立つ式の変形がよく分からなかったので個人的な解釈を示す。
問題の一例として具体例としてA,B,Cの品物がそれぞれ3,2,1個あり3個選択する場合を考える。 まずdp[i+1][j-1] + dp[i][j]は選ぶ個数を減らしたものと、選ぶ種類を減らしたものの和である。A,B,Cから3個選択する場合なら、
A,B,Cから2個選択する数とA,Bから3個選択する数との和である。
A,B,Cから2個選択する場合の数はAA,AB,BB,AC,BCである。
同様にA,Bから3個選択する場合の数はAAA,AAB,ABBである。
A,B,Cから3個選択する場合の数はAAC,ABC,BBC,(AAA,AAB,ABB)である。
カッコの中で囲った場合の数は、A,Bから3個選択する場合の数と同様である。それ以外の場合の数はA,B,Cから2個選択する場合の数の語尾にCを加えたものである。
よってdp[i+1][j-1]は語尾を加えて追加する場合の数、dp[i][j]は変化なしに場合の数に加える数だということがわかる。 しかしAC,BCの後ろにCがついた場合の数は、Cの数が一つなので存在できないため、dp[i+1][j-1] + dp[i][j]だと場合の数が大きくなる。
ここで減算分を考える。
上記の場合だとACCとBCCの分を消す必要がある。結論から言うと前述してあるとおり、dp[i][j-1-a[i]]が必要ない数である。
i-1番目の数を加えるということは、i番目の荷物が含まれていない数ということである。つまりj-1はa[i]が1だったら加わり得る事のできる数である。
上記の例だとA,B,Cから2個選択する場合の数はAA,AB,BB,AC,BCだが、この中のAA,AB,BBはA,Bから2個選択する数である。
しかしa[i] = 1であれば j-2の数は加えることができない。 A,Bから1個選択する場合の数はA,Bであり、ACC,BCCは除外する数である。
そのためdp[i][j-1-a[i]]を減算するのである。

説明が長い上にわかりにくい文ですごめんなさい

VirtualBoxでゲストが起動しないときの対応

BIOSからIntel VT-xを有効化するとできる(こともある)
Debianのイメージがブートしなかったので↑をしたらブートした。
VirtualBoxがCPUの仮想化機能使っていたとは初知り。VMWareとかはCPU関係なくできてKVMとかが必要だったような気がするけどよく分かりません。

mutexのメモ

mutex:マルチスレッドプログラミング時に共有される変数を書き換えたりするときに排他制御するやつ。排他制御いらないなら必要なし

pthread_mutexattr_init():mutexの属性を初期化。この属性がよくわからないが、速い、再帰的、エラーチェックの3つがあるらしい。通常は速いを使う。 pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZERみたいに初期化することもできるらしい。

pthread_mutex_init():mutex自体を初期化。上記のように静的に初期化した場合、こいつも不必要になるっぽい。

ただのメモ

[参考]

Man page of PTHREAD_MUTEX

Man page of PTHREAD_MUTEXATTR

pthread プログラミング要項

http://docs.oracle.com/cd/E19504-01/805-0672/6j0mrl70l/index.html

初公開TOEIC

日記

今日始めて公開TOEICを受験してきた。
結果は散々なものであるのは確実。
あんまり努力はしていないがそれでも、公式問題集のリスニングは殆ど覚えているし長文も精読したけどそれらも意味なし。
PART2が始まった辺りから頭が真っ白になってスピーチが全く耳に入ってこなくなった。
リーディングもPART5は辛うじてそこそこできたと思うが、PART6からまた何も頭に入ってこずにフリーズ状態。
今まで学校の勉強に加えて資格の勉強などをしてきたが、TOEICほど努力が点にならないテストは初めてである。
とりあえず今回は定期テスト直後であまり勉強できなかったのでもう一度来月頑張ってみようと思う。
初めての公開テストということで緊張して、このようになったのならばいいのだが次も続くようならばもう適当な所に就職しよう・・・

TOEICのリスニングが聞き取れない理由の考察

TOEICの勉強しているんですがリスニングがまじで聞き取れないので自分なりにその理由を考察してみた

単語の発音が正確にわからない

これは単純な単語でも起こりうることである。自分が知っている限り多くの学生は単語の発音練習を疎かにする。特に学校で発音練習をする際、ネイティブの発音を真似することが恥ずかしくて、カタカナ英語の発音しかしない。そのため正確な発音がわからず、長文のリスニングなどでは何を喋っているのかわからなくなる。発音練習は大事である。

リンキングがうざい

英語文は前後の単語で発音が変わってきたりする。しかし日本人は前述のように単語すらしっかり発音練習をしていないため英文の練習もカタカナ英語である。そのため発音の変化が分からず聞き取れなくなってしまう。

単語の発音が切れる

気のせいかもしれないがたまに発音が切れるような気がする。日本語では全く聞かないが例えば「山田くんは宿題を忘れた」という文を喋るとき「山田くんは 宿題を 忘れた」と発音をしても、「山田くんは 宿題を わす れた」という単語の途中で発音を切らすような発音を通常しないが「scientific」という単語を「scien tific」と発音している英文を聞いたことがある。こんなことをされれば「scien」と「tific」というそれぞれの単語に聞き分けてしまう。

thatなどをしっかり発音しない

個人的に最大の戦犯だと思う。友人に聞いたのだがネイティブは「a」や「that」、「I」など一部の代名詞や冠詞を他の単語より発音を目立たせない傾向にあるらしい。確かに聞いていてそのようなことはある。これの何が問題かというと、一応発音はしているということ。しかし自分のような英語の初心者はそれがわからないので他の単語にその音がひっつきこれらの単語のあとの単語が違う単語に聞こえてくるのだ。もっとしっかり喋れ、コンプかけるぞ。

興奮するな

スピーカーが興奮しているか知らないけど日本人の会話に比べて非常に早口である。もっと落ち着けよ

以上

Xcode8とswift3でのibeacon(BLE)の使用方法

beaconの信号強度読み込んで表示するだけのApp作りたかったのだけどネットには中々良いサイトがなくて苦労したのでメモ
※この記事はSwiftとiBeaconを使ってお母さんが自分の部屋に近づいて来た事を警告するアプリをつくるさまのコードをXcode8のswift3でコピペで動かすようにする誰得修正記事である
まず上記のリンク中のgithubからサンプルソースをコピペするとXcodeが問題点を適当に吐き出す。まずはそれを全てFixすると最終的に
case .Authorized, .AuthorizedWhenInUse:

if(UIDevice.currentDevice().systemVersion.substringToIndex(1).toInt() >= 8){

self.uuid.text = beacon.proximityUUID.UUIDString の3つのエラーがでるはずだ。この3つのうち一番最初のエラーはこのauthorizedかなんかのライブラリが勝手に使用を変更したせいでエラーがでている。
case .authorizedAlways, .authorizedWhenInUse:こう書き直せば解決するはずである。
次のエラーはsubstringToIndexメソッド(?)に関するエラーだが調べたがよくわからない。しかし丁寧なコメントのお陰でこの条件分岐はiOSのバージョンを確認していることがわかる。
Xcode8で開発対象となる最低のiOSはiOS8なのでそもそもここの条件分岐は必要ない。よって全て消すことでエラーは消える。
そしてここで重要なのがiOS8で初期化を行っているself.manager.requestAlwaysAuthorization()という許可の部分をself.manager.requestWhenInUseAuthorization()と書き換えておくように(理由は後術)
最後のエラーはFixしていくうちにUUIDをuuidに変更してしまっているので、self.uuid.text = beacon.proximityUUID.uuidStringとすればよい。
ここでアプリをデバッグしてみるとラベルの初期値が記述されているだけでありおそらくビーコンを受信できていない。
Swift2でビーコン受信さまの記事を見るとInfo.plistNSLocationWhenInUseUsageDescriptionのキーが必要とあるがXcode8でのInfo.plistのキー一覧を見てみてもそのようなキーはない。
よく探すと分かるのだがこのキー、実はキーの名前が変わっているのである。直接前のキー名を打てばオートコレクトしてくれるので直接打ち込めばOK
これは位置情報を許可するキーらしくこれがないとビーコンの信号を受信できないので忘れず設定するように。また先程self.manager.requestWhenInUseAuthorization()と許可するメソッドを変えたがこのキーの対応メソッドはこいつなのでこいつに変更したのである。Alwaysのほうのキーもあるのでメソッドを変更したくなければキーをAlwaysのほうにすれば恐らく大丈夫だろう。
これでもデータを読み込まなければlocationManagerの引数とかの注意がでているやつをFixすればデータを拾うかもしれない
3日か4日くらい唸っていたけど冷静に対処すればすぐ解決する問題だったなと思いました。

thinkpadのタッチパッドの過剰反応について

X220のタッチパッドが過剰反応して勝手にクリックされる問題に悩まされいたが、ultra navのタップが有効になっていただけだったという話
(ultra nav入っていない人は公式からダウンロードしよう!)
普通に使っていたら勝手にクリックされてめちゃくちゃむかつくんだがこの機能を喜んで使っている人はいるのだろうか・・・