  |
はてなキーワード: TRUEとは
だよね。
要するに参照型変数に保存されているオブジェクトを比較するときで言うと、
isEqualで等しいと判定される
==で等しいと判定される
もちろん神ではない人間からすると、isEqualで分子1個分の差異があることを
判定することはできないし、一瞬まばたきした瞬間に目の前にあったものが
別の物体とすり替えられていないかを判定することはできない。でも、
意図としては上記のような意味で「同じ」という単語を使っている。
日常生活では片方がtrueならほぼ確実に他方もtrueなので
それで問題ないが、テセウスの船を始めとする同一性を問題にする
この記事は Competitive Programming （その2） Advent Calendar 2015の12月20日の分です．12月19日はhadroriさんの競技プログラマー入門者用単語集，12月21日はroiti46さんです．
皆さんこんばんは．Mです．Advent Calendarを書くのは初めてなのでドキドキしていますが，どうぞよろしくおねがいします．普段あまり記事を書かないので anond を使わせてもらっています．
ここでは，ちょっと役立つ小ネタとして，今年書いたコードを１つ紹介します．「ビット行列を高速に乗算するコード」です．ごく簡単なコードですが定数倍効率化効果が大きいので嘘解法に使えます．
要素がブール値（True/False）であるような行列をビット行列と呼ぶことにします．このような行列に対する演算（特に乗算）はアルゴリズム理論ではよく出てきます．最も有名な例はグラフの推移包閉（各点から行ける点を全部求める）です；行列 A をグラフの隣接行列とし，和をbit-or, 積をbit-and で定義すると，行列のべき乗和「A^0 + A^1 + ... + A^{n-1}」の (i,j) 要素が True であることと，j から i に到達可能であることが同値になります．なお，このべき乗和は (I + A)^{n-1} と等しいので，高速べき乗で一発で求めることが可能です．グラフの推移包閉を求める現在（理論的に）最速の手法はこのアプローチに基づいており，計算量 O(n^\omega / log n) を達成します．O(n^\omega) は行列乗算の計算量で，現時点では \omega = 2.3728639... が最良です（Francois 2014）．また，log n は Method of Four Russians と呼ばれるビット演算を高速化する一般的なテクニックで，サイズ log n までの演算結果を全部ハッシュに突っ込んでおくものです．
さて，この Method of Four Russian というテクニックは，実際に実装してもあまり早くないことが知られています（テーブル引きが遅い・単純なループが早い）．ただし「いくつかのビットをブロック単位で計算する」というアイデアは実用的にも有用です．ブロック単位の演算をビット演算で実装できるとき，そのアルゴリズムは「ビットパラレルアルゴリズム」と呼ばれています．編集距離などの例が有名です．
ここでは，ビット行列に対するビットパラレル行列乗算を実装してみました．
A^n を計算するプログラムを書きました．実測結果を以下に示します．MacBook Pro; 2.8GHz Intel Core i7; 16GB 1600 MHz DDR3; g++ -std=c++11 -O3．実装は http://ideone.com/8AsuI2 にあります．
| n | 提案手法[s] | 通常手法[s] |
|---|---|---|
| 16 | 0.000014 | 0.000082 |
| 32 | 0.000025 | 0.000602 |
| 64 | 0.000074 | 0.004485 |
| 128 | 0.000440 | 0.036760 |
| 256 | 0.002757 | 0.311192 |
| 512 | 0.020163 | 2.847787 |
| 1024 | 0.200556 | 24.648609 |
| 2048 | 1.567657 | 205.503351 |
| 4096 | 13.894987 | --- |
| 8196 | 124.414617 | --- |
それなりに大きな n について 120倍くらい高速化しました．これだけ差があると嘘解法が通るようになります．
ビット行列を 8×8 のブロックに分割し，それぞれを unsigned long long (64bit) 1つで保存します．64が平方数というのが美しいですね．全体の乗算は8×8ブロックの乗算を普通に行えばよいので，結局 unsigned long longで表現された２つの8×8行列の積を考えれば十分です．
ここでは8×8行列の積を外積形式で実装します．外積形式というのは C = A B という積を C = (Aの1列目×Bの1行目) + ... + (Aのn列目×Bのn行目) という外積の和の形で表現するものです．各外積は，すべての列がAのk列目と等しい8×8行列とすべての行がBのk行目と等しい8×8行列の bit andに等しいので，Aからすべての列がAのk列目と等しい行列を作る方法とBからすべての行がBのk行目に等しい行列を作る方法を考えれば十分ですが，これはビットマスクして定数乗算すれば実装できます．
このコードはとある問題に対する嘘解法用に作成したものですが，結局普通のほうでも通るようになってしまったので，オフィシャルにお披露目する機会がありませんでした．
ご存じURは礼金保証人は不要だけど、敷金が3か月必要で家賃はややお高め。とはいえオートロックそのほかの設備はしっかりしてるし、家賃が高い分住民に変な人も少なかろうというセキュリティ面を評価して毎月高い家賃を払ってきた。
しかし、そんなURの物件内で、今年に入ってから見知らぬ外国人を見かけることが多くなってきた。最初の頃は外国籍の入居者が増えたんだろうくらいに思っていたんだけど、あまりに頻繁なのでふと思いついて調べてみると、マンション内の一室がAirBnBに登録されてた。つまり彼らはマンションの住人ではなくて、オートロック内に不特定多数が出入りしているセキュリティもクソもない状態になってたってこと。
しかもAirBnBに登録されている室内の写真を見る限り又貸ししている奴は住んでもいなくて、予約不可日≒稼働日として計算すると1室で毎月20万円程度の利益を上げているらしいこともわかった。
他の住民にコストやリスクを押し付けて金儲けしている奴がいるなんて状態はもちろん納得できないのでURに通報したんだけど、それからずいぶん経つのに相変わらずマンション内では見知らぬ外国人をちょくちょく見かけるし、AirBnBの物件ページには「ホストは素晴らしい人だった」みたいなレビューが投稿され続けている。
これってつまりバレてもURに強硬な手段を採られることはなく、問題なく運営を続けられるってことだよね？
金銭的なリスクも改装とかのコストもほとんど負うことなく年率100％近い利回りで不動産投資できるとかサイコーじゃん。家族の名義で数室借りれば、それだけで生活もできんじゃね？
俺も自分で住む部屋は別に借りて、今住んでる部屋はAirBnBで又貸ししようかな。AirBnBの利益で相殺すれば、今よりいい部屋に住めそうだし（笑）。
いやー来るね、UR賃貸でAirBnB運営。そのうちBIG tomorrowあたりが特集組むよ。そうなると競争率が高くなりそうだから、始めるなら今のうちがいい。Make moneyでYou gonna make your dream come trueやで！
