いうことで、Aの各桁の合計値を出してそれが(n-1)で割れるかどうかをみればOKです。C++のスパゲッティなソースを張っておきます。(dividable()の中で毎回合計値計算してるのは無駄ですね。最初まじめにHormerの公式を使って余りを計算して解こうとしていたのの名残です。最大クリーク問題http://poj.org/problem?id=3692を解いていて、「最大クリーク問題」という問題について知った。与えられたグラフの部分グラフのうち完全グラフとなるものをクリーク(clique)と呼ぶ。節点数が最大となるクリークを求める問題を「最大クリーク問題」という。この問題はNP完全らしい。graph(枝集合が空集合であるグラフ)であるので、あるグラフの最大クリークを求めることと、その補グラフの最大独立集合を求めることは同値である。二部グラフにおいては最小点カバーと最大マッチングが一致すること、および、一般のグラフにおいて最小点カバーと最大独立集合の和が節点数と一致することから、対象の補グラフが二部グラフである場合には最大クリークを簡単に求めることができる。”クリーク”という言葉は、社会学から生まれたらしい。ソーシャルグラフの中からお互いが全員知り合いであるような最大集合の大きさを求めたいというのが研究のはじまり。PKUの問題もこれと同様の問題。実際のソーシャルグラフの補グラフは必ずしも二部グラフになるとは限らないため、さまざまな近似アルゴリズムが研究されているらしい。PKUの問題の解答例を載せておきます。Pics結構前にgitはローカルとvpsともに入れていたのですが、GitHubにソースを上げるときくらいしか使ってませんでした。vpsにマスターのレポジトリを作って、ローカルにいくつかレポジトリを作ってpushしたりpullしたりして遊んでみました。簡単なメモを残します。sshのconfigファイルの設定sshを使ってリモートログインしたいサーバーが複数台ある場合は、configファイルを書いておくと便利です。サーバーのアドレスや、sshのポート番号、どのrsa秘密鍵を使うのか、などを記述しておくと、sshコマンドを使う際にいろいろとオプションを書かなくてよくて楽です。vpsのようにHOST名を書くだけでログインできるようになります。サーバー側にbareリポジトリを作る調べてみた感じだと、2つやり方があるようです。1つ目は、サーバー上で普通のレポジトリを作成して、それをbareリポジトリにcloneして、さらにそれをローカルにcloneするという方法。2つ目は、サーバー側にbareレポジトリを作成して、クライアント側でリモートサーバーを登録する方法です。1つ目の方法だと、cloneした時点で、push/pull先が自動でremoteに登録されるので明示的にリモートサーバー名を追加する必要はありません。サーバー側でcloneする前に、適当なファイルを作ってcommitしておかないといけません。initとするだけです。サーバーを明示的に追加する必要があります。ssh://vps/~taro/git/repos/helloとするのは面倒なので、登録しておいた方が便利。2つ目のやり方の方が一般的かと思います。MagicalSquareDPで解く問題。どのような状態を保持するかが悩ましかった。k文字まで埋まっている場合のパターン数を保持するようにした。jが決まれば一意にきまるので、dp[r][i][j]とした。50)であやしかったけど、投げてみる。ループの中にbreakを入れて枝狩りをしてみる。んー、通ったものの、計算量はもう一段階落ちると思う。文字列の比較をハッシュとか使ってやればいいのかなー。Editorialに期待します。dropcoins完敗(^O^)/どうせ探索問題だろうとおもったのが、すべての敗因でした。このやり方知ってるのに出て来なかったのは悔しい。ばか、もうほんとばか。SRM2011年11月27日日曜日C++の関数オブジェクト前から気になっていたのですが、C++にgreater<int>というものがあります。greater<int>());のようにして使います。>que;のようにします。ここで気になることがあります。sort()の場合は、greater<int>()と括弧つきで使用して、priority_queueの場合は括弧なしで使用しています。この違いは一体・・?そもそもこれは関数なのか、関数ポインタなのか?ということで調べてみました。http://www.geocities.jp/ky_webid/cpp/library/015.htmlこれは、関数オブジェクト(ファンクタ)と呼ばれるらしいです。operator()がオーバーロードされていてオブジェクトを通常の関数と同様の方法で呼び出し可能にする仕組みらしいです。いうことでgreater<int>()は以下のように使うことができます。falseまたは、こんなかんじ。こっちの書き方がオブジェクトを関数のように使ってるというのが分かりやすいかも。falseでも何だかもやもやしています。これって何が嬉しいんだろう。関数ポインタと一緒じゃ。いうことでまた調べてみました。http://d.hatena.ne.jp/pknight/20090818/1250584515#c関数ポインタと比べたときの関数オブジェクトの利点は以下の2つだそうです。コンパイラがインライン展開しやすいメンバ変数を持てるので状態を持った関数を作れるなるほど。2つ目の利点が面白そうで、これってクロージャとかジェネレータとかがつくれるってことなんじゃ?と思って書いてみました。クロージャ的なやつ(実行時に入力された数値によって挙動の異なる関数を生成したように見せかける)。0;}次に、ジェネレータ的なやつ(フィボナッチ数列生成器)。composition的なものを書いてみます。最初templateをプレースホルダーのように使って書いてみました。0;}そのあと、動的に渡すような形で書けないかなーと試行錯誤して以下のようなものを書きました。0;}書いた後、気付いたのですが、compositionの上のバージョンはpriority_queueと同様、下のバージョンはsort()と同様の書き方になっていました。やって見ると、priority_queueの場合は関数オブジェクトのクラスを、sort()の場合は関数オブジェクトのインスタンスを渡しているということに気付きます。たしかに、priority_queue<>の<>内で指定するものは"型"、sort()の引数で渡すのは実体を持った"値、または、インスタンス"であることを考えると、どっちに括弧付けないどっちに付けないのかってのは納得できます。実際にSTLのライブラリのソースを読んでみると、priority_queueの場合、第三引数で渡す_Compare(greater<int>に対応するもの)は"型"として使われていて、こういう使い方は関数ポインタだと書きづらいのかなと思いました。木構造のメモリ確保トライ木を使って以下の問題にトライしたところ、TLEを食らいました。http://poj.org/problem?id=3630最初に書いたコードはこれです。トライ木を構築して、語尾にあたる節点が子を持っていたらエラーとします。このエラー検出と同時に動的確保したメモリを解放しています。0;}なんとか高速化する方法はないかと調べていたら、komiyamさんの日記におもしろいアイディアがあったので、参考にさせていただきました。毎回メモリを動的確保するのではなく、予め必要な分だけ静的領域に確保しておき、節点を生成するときは予め確保しておいたメモリのアドレスを渡すという方法です。これにより、メモリの確保/解放に係るオーバーヘッドがなくなります。メモリの解放をせずにすむために枝狩りができます。私の最初のソースでは、エラーを検出してもトライ木全体をトラバースしていました。これはメモリを解放するためです。メモリの解放がいらなくなると、エラーを検出した時点で探索をやめることができます。0;}以上がメイントピックですが、3点ほどちょっとしたTipsを書いておきます。[C++のstructについて]C++のstructはCの構造体とは違います。C++の場合はstruct内にメンバ関数を持つことができます。classの場合アクセス修飾子を省略するとprivateになりますが、structの場合はpublicになるそうです。9のintに変換するとき、komiyamさんはおもしろいやり方をしています。intに変換されます。確かに、'0'は16進数だと0x30なので、0x0fでマスクしてあげるとintに変換できます。[ローカル変数のdelete]最初、rootの接点だけローカル変数で宣言していて、validateでメモリ解放するとクラッシュしました。当然っちゃ当然ですがスタックに積まれた変数をdeleteしようとすると予期せぬ結果が発生します。再帰的処理で一括してメモリ解放するときなどに、ある特別なデータだけスタック変数だったとか結構ありそうな落とし穴なので注意。arithmeticの絡んだ数論チックな問題(好きなタイプの問題)。tableを使って解いて、TLE。upすればいいので、priority_queueを利用したダイクストラ法のようなやり方をすればいいのに気付く。(追記)editorial読んだら、queueでいいっぽい。最初に埋まったやつがbestになるから、確かにqueueでOK。0.20.203)試してみました。Pseudo-Distributedモードでexampleをいくつか動かしてみました。ほとんど公式ホームページにあるとおりにやればOKですが、いくつかひっかかったところがあったので、メモしておきます。[SSHのオプション]SSHのポートをデフォルトの22以外にしている場合は設定ファイルにsshのオプションを設定。1234"[Webインターフェース]NameNode、JobTrackerのステータス確認用のwebインターフェースhttp://localhost:50070/http://localhost:50030/があって、プラスα的な機能かなと勝手に思い込んでいたら、このページを開かないとhdfsがきちんと機能しないらしい。[データ保存領域の設定]Ubuntuだと再起動後に、dfsのテンポラリーディレクトリに保存したファイルが消えてしまいます。保存先をデフォルトのtmpから変更してあげればOKです。conf/core-site.xmlに以下の設定を追記。xxxxは実行したいサンプル。outputのようにする。SSHのRSA鍵設定、rm、emacsの設定などvps初めて半年くらい経ちました。当初借りたは良いけど、何をしたらいいのか分からない状態でしたが、適当にwebサービスを作ったりしてまあまあ活用できている気がします。最近気に成っていたことがいくつかあったので、まとめて片づけました。するemacsのバックアップファイルを作成しないようにするまず1。プレインテキストでユーザー情報とかパスワード流すのやばいだろう。(※訂正:teratermのオプションにプレインテキストって書いてあったので平文で流れているのかと思いましたが、mojavy先生曰くsshではすべての通信が暗号化されているため、プレインテキストでパスワードが流れるなんてことは無いそうです。前々から思っていて、いつの間にか忘れていて、セキュリティの読み物見ていたら思い出して、即実行しました。http://d.hatena.ne.jp/elwoodblues/20070620/1182330984を参考にしました。上のサイトにあるようにローカルで鍵ペアを作成して、サーバーに公開鍵を送るようにしましょう。サーバーで作って、秘密鍵をローカルに転送とかやってたら本末転倒なので。termの初期設定ファイルに保存しておくとログインがらくです。「設定の保存」を選んで、INIファイルに設定を保存します。*とかやったら泣けるなーと思ってその予防策。~/.bashrcに以下追記。毎回チルダから始まるバックアップファイルを作っているのがemacsだと分かったので作らないように設定。~/.emacsに以下の設定追記。problem)という有名問題があります。これの一般解を求める式があるらしいので調べてみました。以下では、円を組む人の数をn、スキップ数をkとします。本来は、n番目(つまり最後に)処刑される人の番号を求めればよいのですが、より汎用的にs番目に処刑される人の位置を求めることにします。ここのページにあるように、以下のソースコードでs番目に処刑される人の位置がわかります。ret;}えーーっと、よくわかりません。いうことで、何故上のコードで答えがでるのか考えてみました。(結構がんばりました(汗)。1)という写像が何をするのか考えます。7・・・・・ふーむ、どうやらf_kは、自然数からなる点列(1,2,3,...)からkの倍数を取り除くような効果があるようです。本当か?ちょっと数学的に考えてみます。コンピュータの整数演算では2ですが、数学上は、2余り1です。k余り(k-1)です。f(k)は(k-1)余ってますが、(k-1)で割るのでこの余りは消えて商が1増えます。k+1)となりました。(k-1)で割った余りが0になる場所を調べます。(k-1))となります。先の例で正の整数の点列からkが除去されることを確認しました。2*k-1という場所は本来2*kがある場所です。(kが無くなってるから1引かれる)。ここで同様に商の繰り上がりがおこることから、2*kは点列から除去されます。同様に3*k-2に対応する3*kも除去されます。以降同様にして、kの倍数がすべて除去されるというわけです。ここまでで、写像f_kがkの倍数だけを除いた整数点列を生成できることが分かりました。k*s)にしたものを考えていることが分かります。ここから逆算して、k*sが区間[1,n]の整数のどれに対応しているかをみていこうというわけです。n)でnからはみ出ている分が分かります。このはみ出ている部分に対して、写像f_kを適用することで、retは消えたものを除いて数えた場合にそれがあるべき場所へとマッピングされます。nになるまで繰り返しているというわけです。説明足らずな感じなので、表で示します。