深さ優先探索を再帰関数なしで書くと速度はどうなるか？
気になったから適当に書いてみた。
続きを読む結果を出し続けることの大切さ
タイトルはちょっとかっこいい感じのオーラ出てますが、すっごいかっこ悪いことを書きます。
今、自分が紹介されたらどうなるか
「今回のゲストは高橋直大さんです！ 高橋さんは、Imagine Cup 2008 アルゴリズム部門で3位を獲得され、TopCoder Open 2010でも2位を獲得された、日本トップクラスの競技プログラマーです！ 現在は、AtCoder株式会社の代表取締役として、コンテストの運営側に回り、後進の指導に力を入れています。」
自分の言いたいこと
2010年までしか結果出してなくて今は運営に専念してるっぽい紹介されちゃうけど、現役選手だよ！？普通に出場しまくってるよ！？
要するに何が言いたいか
良い結果を出した後に、その後同等の成果が出ないと、いくら活動を続けていても、「昔の人」扱いされちゃいます。きちんと結果を出しましょう。
いや、でもね？ 去年だって、ICPFC2013で優勝したり、TopCoder Open 2013で世界5位取ったり、ちゃんとある程度の成果は出してるんだよ？ ね？だめ？ もっと結果出さないとだめ？
「実践・最強最速のアルゴリズム勉強会」開催します！
AtCoderを利用した、実践アルゴリズム講座を開催します！
概要とかは上に書いてありますが、無料講座で、3/9(日)から５週連続で開催します！
教育関係のをやりたくて会社を立ち上げたのもあるので、こうして勉強会を開けるのは凄い嬉しいです！
どんなことをやるの？
アルゴリズムの勉強、というのは、理論を学んでも、実践までするのはなかなか難しいし、実際コードにする機会というのは、なかなか少ないんじゃないかな、と思います。
例えば、「クイックソート」とか「マージソート」とか、「バブルソート」とか、名前は知っていても、仕組みは知らない人が多いと思うし、知っていても実装したことがある人は少ないんじゃないかなー？と思ってます。
とまぁ、アルゴリズムって、「自分で実装が出来る」か、「中身はよく知らなくても、ツールとして利用できる」のどっちかの状態にならないと、仕方ないと思うわけですね。
そこで、今回注目するのは、「自分で実装が出来る」のところ。汎用性が高く、ある程度自分で実装するべき、探索や動的計画法をベースとして、「どう探索するか」「探索過程をどうイメージするか」「どう計算を工夫するか」に焦点を当てて、勉強会を進めていこうと思っています。
どう進めるの？
進め方は、以下の３つの繰り返しとなります。
- 講義 これから練習するアルゴリズムの説明をします。
- 実践 具体的な問題を見た上で、どう実装するかをソースを見せて説明します。
- 演習 別の問題で、実際に自分で組んでみましょう！
講義、実践は自分が前で説明を行い、演習中は、手を動かす形になります。会場中を回りながら困っている人のヘルプに入るつもりですが、解らないことがあったら、手をあげて質問をしてもらえると楽で嬉しいです。
どんな人に来てほしいか
スケジュールが、こんな感じです。
- 03/09（日）第 1 回 シミュレーションと全探索
- 03/16（日）第 2 回 いろいろな全探索
- 03/23（日）第 3 回 動的計画法とメモ化再帰
- 03/30（日）第 4 回 動的計画法と計算量を減らす工夫
- 04/06（日）第 5 回 難問に挑戦！
１日目は、競技プログラミングってどんなものかな？というのを触れながら、まず形式に慣れてもらう形になります。ここは、競技プログラミング経験のある人が来ても、ちょっと退屈になっちゃうかもしれません。
２日目は、深さ優先探索・幅優先探索といった、全探索の手法の話をしていきます。競技プログラミング慣れしていない人は、ここから参加するとちょうど良いと思います。
３日目は、全探索が間に合わなくなった場合に、動的計画法・メモ化再帰で、計算量を減らす工夫について説明します。ここからは、愚直な実装では正解コードが書けなくなるので、難しくなってくるかもしれません。
４日目は、さらに難しくなった動的計画法の話と、その他のアルゴリズムの説明をします。今回はグラフを省こうと思っていて、探索のイメージから習得しやすい、二分探索や、尺取法、半分全列挙なんかをテーマに、計算量を減らす面白さを体感してもらえると良いな、と思っています。まだここもちょっと未定です。
５日目は、どれだけ難しくするかはまだ決めてません。４日目までの状況を見ながら、問題を選択するつもりでいます。これは演習が殆どになると思うので、少し経路が変わる毛色が変わるかもしれません。
はてなスターで誤字指摘するなら普通に教えてよ！！ｗ
ここまで見て、好きな日に参加してもらうのが、一番良いと思います。とりあえず全部登録して、大変そうだったら途中でリタイア、でもいいと思います。（まずかったらワークスさんごめんなさい＞＜）
ぜひお気軽に参加してもらえると嬉しいです！
最後に
競技プログラミングは、本当に面白いと思っていますし、普通のアルゴリズム教育とは、また違った視点でアルゴリズムが学べると思っています。少しでも興味がある方は、ぜひ遊びに来てくれると嬉しいです！
学校教育で鍛えられる「なんとなく」の力の大切さ
下から7割の人のための理科＆算数教育 - Chikirinの日記
これを読んで。自分は算数の人なので、理科をスルーして算数部分だけ。
そもそもの大前提
- リボ払いを選んだ場合の利子の額
- 大半の人が選んでしまう住宅ローンの“元利均等払い”の恐ろしさ
この2つを教えるべき、ということを具体例として教わっているのだけれども、まぁ、「すでに学校で教えている」ことだよね、というのは言うまでもないと思う。まさか、「計算過程は教えずに、リボ払いが危険だ」という事実だけ教えろ」なんて言うことではないだろうし、計算方法は習ってる。というのは、すでにみんなが突っ込んでると思う。
学校教育で覚えていること
じゃあ、なんでこんな話をしているのか。学校で習ったことなんてみんな忘れるからだろう。応仁の乱の年号とか覚えてないのと同様、きっとリボ払いの計算は出来ない人は多い。これ、凄く大切で、リボ払いが危険だーってならったとしても、将来的にリボ払いが危険だということを覚えているか解らんのだよね。ってことで、「リボ払いが危険」ということを教えたところで、リボ払いもしくはその類似品で嵌る人ってのはそんな減らないわけですよ。
リボ払いを回避できる人は、どうして回避出来ているのか
まぁ、多分、利子がどれくらいになるか、という計算を出来る人は少ないと思うし、それを実際にした人はもっと少ないわけですよ。けどまぁ、回避してる人、というのはいくらでもいるわけです。そのパターンは、大別して２つに分かれるわけです。
- 「リボ払いは危険」という知識だけ、他所から伝聞で知った
- 危険かどうかは計算してないが、なんとなく危険そう
まぁ、多分どっちかだと思うんですね。自分は後者です。
なんで後者みたいな判断が出来るか、っていったら、「指数」ってものを習って、指数ってのはぎゅいーんって増えていくもの、っていうのが分かった上で、「金利」ってワードが解りやすく指数なので、「これやばいんじゃね！？」って反応出来るわけですよ。まぁ指数っていうとちょいずれるけど、直感的にやばそう、ってのがある程度判断出来るよね。
目指すべきはここだと思うんですよ。正直大学受験の数学が今解けるか、って言われたら、自分はあんまり解けないです。だけど、そこで身につけた感覚、みたいなのは今でも残っていて、結構大切だよなぁ、と思ってるわけだ。
学校教育で直観力をつける
結局、学校教育で身に着けるべきものは、直観力だと思う。
算数、数学だったら、まぁある程度は計算出来たほうが嬉しいし、数字がどれくらいになるか、どう変化するかのイメージが掴めるのが大切なんじゃないのかな。で、数学を専門で勉強する人は、そこが厳密になっていれば良い。
リボ払いだとか、そういう金利計算を、ケーススタディとして学ぶのはもちろん良いんだけど、それじゃ根本解決にならんし、まんべんなく触れて、なんとなくこんな感じなんだな、って風になるように学べば良い。もちろん、大人になって何となく理解しているには、学生時代にある程度計算出来たりしないとダメだと思うけどねｗ
そもそも、「社会」「国語」とかを挙げずに、ちきりんさんが「算数」「理科」だけを列挙してる時点で、「社会」「国語」に対する理解が必要だって解ってるんじゃないかな。
歴史とかだって、別に自分はなんとなくわかれば良いので、例えば応仁の乱が何年くらいあったかとか全然知らないけど、「どういう事をしたら」「どういう風になった」はなんとなく掴んでいるし、そのあたりが、例えば選挙なんかの判断に、なんとなーく絡んでるよね。多分。
国語なんて言語だから解りやすいよね、言語なんて厳密にやらずに何となく把握して何となく出来るようになってる。
何となく、ってすっげー大切なわけです。その何となくを鍛えてるのが学校教育だと思うんです。ってことで、自分は今の学校教育好きだよ。
しかしまぁ、単語とかなんとなーくじゃ全く覚えられないので、全く出来ない英語は滅びれば良いと思う。ばーかばーか。
はてなブログに切り替えてみた
何となく、はてなブログに切り替えてみた。
大きな理由はそんなになくて、はてなダイアリーを使っていたら、周りがみんなはてなブログじゃなくてはてなダイアリーを使っていたから、という理由。前のブログとは語り口とか考え方とかだいぶ変わっていたので、ちょうどいいかな、とも。
はてなダイアリーをこっちに移行出来ないのかな？と思ってたのだけど、一応別サービスっぽいし、まぁ暫くこっち使ってみようかなぁ、みたいな感じ。
最近Twitterメインになっていて、長い文章を書く癖がなくなっていたので、ちょこちょこと更新しようかな、と思ってる。
追記
やっぱり移行できたみたいで、はてブの移行やリダイレクトも出来るらしい。移行記事を書こうと思ったら書けなくて困ってるけど、まぁそれくらいはいいかな。
もし僕が政治家を目指すなら、インターネットをこう使う
都知事選挙で、家入一真さんが立候補をしていた。インターネットを利用した政治、および選挙活動、というのは、僕も面白いと思ったし、着眼点は良いと思う。だがしかし、僕から見ると、家入さんが、インターネットを利用しきれているようには到底思えない。そこで、競技プログラミング世界ランカーの立場として、自分なりに、もし僕が政治家になるとしたら、どのようにインターネットを活用し、政治に繋げていくか、というのを書いていこうと思う。競技プログラミングの感覚で政治を語っているので、少しおかしな部分もあるとは思うが、最後まで読んで、意見を貰いたい。
インターネットで出来ること
インターネットの強さは、速さと手軽さだ。従来の選挙では、民意を知るために、わざわざ丸１日使って選挙を行わなければならない。これは非常に面倒だし、お金もかかるので、頻繁に開くことができない。なので、一つ一つの政策に関して議論をすることができないし、政策ではなく、政治を行う人を選ぶ、という行為を行わなければならない。
インターネットを使えば、簡単にアンケートを取るだけなら、適当なサービスを使えば一瞬でアンケートを取ることができる。もちろん、投票の割合や複数投票などの問題は抱えているが、その問題さえ解決可能であれば、あるトピックに限定して、民意を知ることは簡単だ。これによって、政策の立案も議論も、インターネット上で、国民一人ひとりが行える、というのが、インターネットの強みだと思う。
もちろん、これで得られるものは国民全員の民意ではなく、インターネットで政治参加した人全員の民意でしかない。だが、インターネットで政治参加した人の民意を元に政治活動を行う政党というものが悪いか、と言われたら、僕は良いと思うし、もしそういう政党があるのであれば、支持したいと思っている。
家入さんの「ぼくらの政策」の、何がいけないか
家入さんは、インターネットを通じた政治参加として、ぼくらの政策、というものを実施した。Twitterのハッシュタグ「#ぼくらの政策」に投稿された政策案から、家入さんがピックアップをして、政策を決定する、というものだ。これを用いて、家入さんは、「政治家よ、これが民意だ」とツイートしていた。冗談ではない。これは民意ではない。反例なんてすぐ挙げられる。僕がこのハッシュタグで「東京に原発を1000個作ってほしいです！」とツイートして、それを家入さんが120の中に加えたとしても、同じように「これが民意だ」と言えるだろうか？言えるわけがない。
何がまずいのか、というのは、もちろん、120個の政策を、家入さんが自分でピックアップしている点だ。他の政治家は、自分で政策を１から考えるのに対して、家入さんは、他の人の案を寄せ集めているので、自分で考える必要がないという点だけ少しネットを使った恩恵を受けれているかもしれない。だが、家入さんが選んでいる以上、これは民意ではなく、家入さんの政策だ。これじゃ、結局自分がこういう風にしたいな、というのを押し付けているだけなので、今までの政治家と大して変わらない。
「民意」から政策を作るにはどうしたら良いか？
家入さんの悪い点のみを列挙しているが、今回、約30000もの政策案をツイートさせた、というのは、非常に良いことだ。3万の立案をする、というのは、そう簡単なことではない。だが、問題があるのは、そこからの選び方だ。各政策に対して、賛成派のほうが多いことを主張しなければならない。今回は選び方が不透明なので、どう選んだのかが全く分からないが、それを主張するには、通常はもう１ステップを踏む必要がある。
たとえば、120の政策に対して、1つ1つ、120個のアンケートを設置し、賛成or反対の2択アンケートを作る、なんてこともできるだろう。それだけで、各政策が支持されているか、支持されていないか、一応の判断をすることができる。別に政策の候補を絞ること自体は、家入さんがやっても良い。だが、その承認を何らかの確認で得なければ、それは民意であるかどうか、確認することが出来ない。
ここまでは、簡単に実装可能そうな、現状から民意に近づける方法である。今回のように時間がなかった場合、僕だったら200の政策候補を出した後、アンケートで過半数を大きく上回るもののみを政策としたと思う。
そもそもなんで都知事選なの？
インターネットは、全国誰でも場所関係なく参加できる、というのが強い点だと思っているし、東京都だけに絞った話を、インターネット上でするのは、あまり向いていない。向いているのはやはり国政であり、都知事でなく国会議員を目指すべきなんじゃないのかなぁ、と思う。参議院選挙であれば比例代表があるし、インターネット上で、全国からまんべんなく少しずつ得票できれば、1議席を獲得するのは不可能ではないだろう。家入さんが大体今回1%の得票を得られたし、2%まで上げることができれば、比例代表選出議員は1回の選挙で48人だったはずなので、現実的なラインではないかと思う。ということで、ここからは国政の話に移る。
具体的なインターネット政治参加システムの提案
ここからが本題。昔からぼんやりと考えていた、インターネットユーザーが、政治に直接関わるのであれば、どういう形をとるべきか、という話をしていこうと思う。
単純なアンケートを取るだけでは、ただの集合知になってしまう。もちろんそれが必ずしも悪いわけではないが、やはり理想的な形を考えるのであれば、インターネット上で議論ができるようにするべきであるし、その議論の結果によって方針決定されるべきである。その、具体的なシステムについて語る。思い付きの範囲は出ないが、たたき台になってくれると嬉しい。
ネット国会・ネット議員を作る
ネット上で議論をする場は、いわばネット国会であり、そこで議論をするのはネット議員である。インターネットの速さ・手軽さを守るために、絶対に守ることは、以下のような点だ。
- ユーザーは、いつでもネット議員になることができる。
- ネット議員は、いつでも政策を提案することができる。
- ネット議員は、いつでも提案された政策について議論することができる。
- ユーザーは、いつでもネット議員に投票することができる。
各ユーザのパラメータ
各ユーザは、2つのパラメータを持つ。
議員ポイント
ユーザが、ネット国会において、何議席を持っているかを表すポイントである。
この値が高ければ高いほど、ネット国会において大きな影響力を持つことになる。
初期値は1であり、議論において、賛同を得られれば得られるほどポイントが高まり、反対をされれればされるほどポイントが低くなる。
投票ポイント
ユーザの投票が、何票分の影響力持っているかを示すものである。投票を行うことにより、各議員の影響力を高めたり、低めたりすることができる。
理想的には、全てのユーザが独立した人で構成されており、全員が1である。が、spam等が発生する可能性があるため、「人間っぽさ」を0〜1で表すことにより、スパムを防止する意図である。
具体的には、登録時にTwitterやfacebookなどと連携させることにより、Kloutやqru.stの値から、初期値を算出する。普通に使っていればほぼ1となるようにする。そこから、同一IPからの連続投稿などを検出したら、0に近づけていく。予算削減が目的なので、本人確認ができて0,1で計算できるのが一番良い。
各ユーザの出来ること
ユーザのできることは、以下の3つである。
立案
ユーザは、ネット議員として、政策を提案することが出来る。提案自体にユーザのパラメータは関係ない。
提案された政策は、webサイト上に一覧として表示される。
政策の提案には、「ユーザが提案したもの」と「政党が必要に応じて提案したもの」があり、後者が先に表示され、その後、議論が活発な順に表示される。
議論
ユーザは、ネット議員として、各政策について、意見を書き込むことが出来る。「賛成」「反対」のどちらかの立場を表明した上で、その論拠を書き込む。「中立」を表明しても良いが、その場合は、その政策が採用されるかどうかに影響を与えない。書いた意見が、他のユーザに賛成されることで、その意見の影響力が強くなり、反対されることで影響力が弱くなる。なお、賛成票より反対票のほうが多い場合は、影響力は0となる。
書き込みの雰囲気としては、Yahoo知恵袋の質問が立案で、その下の回答が議論内容、みたいなイメージを持ってもらえれば、大体問題ない。影響力の強い順に表示する。
投票
ユーザは、各政策に対して書き込まれた意見に対し、「賛成」「反対」（もっと軽く言えば、イイネのようなものと、その反対）が投票可能となる。政策自体の賛成・反対ではなく、その意見に対して良い意見か悪い意見かを投票する。この投票をすることにより、もし賛成票を投じた場合は、
- そのユーザの影響力が上昇する（内部的に言えば、議員ポイントが上昇する）
- その意見の影響力が上昇する
の2つが同時に起こる。
内部処理
意見の影響力の計算と、賛成反対の集計
- 意見の良い悪い
まず、各意見の、各意見の良い悪いを判定する必要がある。
(意見の良い悪い) = log(Σ(賛成した人の投票ポイント / その人のその提案に対する投票数) + A) - log(Σ(反対した人の投票ポイント / その人のその提案に対する投票数) + A)
Aは定数で100くらい。票数が少ないときに良い悪いが判定しづらいので、両方にAを足すことにより、少ない票数の時の影響力を弱める。logの底は1.1くらい。良い意見はプラスになり、悪い意見はマイナスになる。
- 意見の影響力
(意見の影響力) = 意見発信者の議員ポイント * max(0, (意見の良い悪い))
意見の良い悪いに、議員ポイントを掛け合わせることにより、意見の影響力を決定する。
webサイトに意見一覧を表示するときは、この影響力が高い順に表示する。
- 賛成・反対の集計
(政策ポイント) = Σ(賛成意見の影響力) - Σ(反対意見の影響力)
この政策ポイントが、ある正の一定値を超えた場合に、その政策は、民意によって定められた政策として認め、政党の政策に加える。
議員ポイントの変更
良い意見を発信したかどうかで、議員ポイントの変動を行う。
(議員ポイント) = log(max(1 + Σ(その人が出した意見の良い悪い)), 1) + 1
logを取ってあげることにより、議員ポイントが高まりすぎないようにする。悪い意見しか発信してなくても、最低1は残るようにする。底は1.2〜2くらいかな？数式があんまり綺麗にならないし、p乗(pは適当な0〜1の小数、たぶん0.3くらい)のがいいかもしれない。
自分は「賛成票を投じた」ということは、「その人が信頼できる意見を言っていることを認めた」ということであり、他の意見にも一定の信頼を寄せる可能性が高いだろう、ということで、こういう議員ポイントを持たせているけれども、ここは好みなので、好きな風に設定してもらえれば。
その他
たとえば、これを適当に流用すれば、「現在提出されているこの法案に対して賛成/反対をどうするか」なども同じ感じでできるし、結構いろんなところをカバーできるんじゃないかなー、と思ってる。政治家さんが普段何してるかわからんので、どれくらいカバーできるのかはよくわかんないです。
なぜ自分で立候補しないのか/システムを作らないのか。
ここまで好き勝手「ぼくのかんがえた最強の政治しすてむ」みたいなのを書いてきたわけだが、これを実装したり、立候補したりするつもりは今のところない。
僕は25歳なのでそもそも被選挙権はないが、そもそも、政治に関わる人間は、政治の事を第一に考えられる人間でなければいけないと思う。僕は政治の事なんて全く分からないし、そもそも今はAtCoderという、プログラミングコンテストを定期的に開催する会社を経営している。こうした状態でまともに政治参加するのはもったいないし、結局サービス上で集約された意見に従うわけだから、アルゴリズムができる人間がが政治家になってもしょうがない。その場で受け答えがちゃんとできる、政治が解る人間のほうが適任。
なんでシステム作ってからものを語らないか、というのは、まぁぶっちゃけた話、こういうシステムを作るのは結構大変で、ある程度はてブとかで賛同が得られるかどうかの確認をしないと、作って誰も使いませんでしたじゃあまりにもったいないので、確認を取りたい。民意を知りたいわけですね（笑） 上記の会社の仕事が結構忙しいので、もし賛同が得られてそうだったら、家入さんの周りの人が作ってくれるんじゃないかな、ってのに期待してこのタイミングに投稿してたりするわけです。そういう意図もあって、ほんとはもうちょい色々複雑なのを考えてたんだけど、とりあえず単純なシステムにしてみた。企画だけ作って実装やらない、典型的な慶應SFC生にありがちっぽい立ち回りになっちゃってるけど、まぁ自分の他のサービスあるから仕方ないね。
