した問題で面白いのがあったので紹介。http://www.topcoder.com/stat?c=problem_statement&pm=9954&rd=13506簡単に訳するとこんな感じ。立方体をn*n*n個の小さな立方体に分ける。そのあと、適当に小さな立方体を抜き取る。この立方体の写真を三方向(x軸、y軸、z軸方向)から取る。3枚の写真を見て、抜き取られた可能性のある小さな立方体の最小個数を求めよ。最近買ったルーブックキューブと睨めっこ・・・。この問題は、テクニックというより、生まれ持った才能による部分が大きい気がする・・・・。いえば、高校のとき「東大に行きたければ、数学は空間系の問題に強くならないとダメだ。」って先生が言ってたのを思い出した。まー、話を戻して、友達の回答を見て自分なりに書いたコードはこんな感じ。ret;}なるほど!そういうことか!ちょっと気になったのが、valid-checkのところ。なんか短くできそうな・・。Editorialに赤い人のコードが載っていたので、それを参考に書いてみた。ret;}ほう、逆の発想をすることで、判定のところがシンプルに書けるわけか。このコード理解するのに時間かかりました(笑)ちょっと、この才能の差を埋めるにはかなり時間がかかりそうだな~~~。誤差にまつわるエトセトラ今日は、浮動小数点小数の数値計算誤差について書こうと思う。以下のコードを実行してみましょう。0;}結果は以下のようになります。>10000000000000000.0000000>1>0>1.000000まず、case1から見ていきましょう。10000000000000000.000000に1を足しても10000000000000001.000000にはなりません。~10^15だからです。最初の15桁以下は丸められてしまいます。逆に言うと、10^15以下の整数ならdoubleで正確に表すことができます。この辺の話は昔投稿しているので、こちらをご覧ください。次に、case2です。これは、おもしろいです。y1とy2をビット列で表すとそれぞれ以下のようになります。10011100実は、この2つの数は、doubleの世界では連続する数値です。それにも関らず、(y1-y2)は1e-5程度です。連続する値なので、ほんの少しのエラーで、ある値がもう片方の値になりえます。数値計算を実施する際は、この2つは、同じ値とみなしてよいでしょう。1e-7)なんてやっちゃうと、この2つの値は、同値とは判定できません。何がまずかったのでしょう・・。doubleは浮動小数点なので、小数点の位置は固定ではありません。絶対的な値を誤差の許容範囲とするには無理があります。y1とするとよいでしょう。これは、やっかいです。y1を判定条件に用いればよいことを示しましたが、case3では、この判定条件は適切ではありません。同値とみなすべきz1とz2が同値とみなされません。符号が異なる2つの微量な数値を比較する場合は、case2の場合は適さないようです。case2とcase3を2つ使って判定しましょう。競技系プログラミングでは、小数が現れないように分母を他辺に掛けるテクニックが有効のようです。比較する値の絶対値が比較的小さいものであれば、絶対評価(case2)だけ十分でしょう。出典)http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals読んで理解したことを書こうと思ったら、ほぼ和訳みたいになりました(笑)英語が出来る人は、上の原文を読んだ方が分かりやすいはずです。ITトピック2010年11月21日日曜日C++で関数型プログラミング:accumulate編マルチパラダイム言語として知られるC++。競技系プログラミングばかりやっていると、手続き型でばかり書いてしまう。職場では、ぱっと見オブジェクト指向のようなスパゲッティソースを保守している。最近、C++で関数型プログラミングっぽいこともできることを発見。今日は「畳み込み関数」をC++でやってみます。畳み込み関数は、Pythonでいうreduce()です。0;}[実行結果]5536288003300-12100accumulate()のシグネチャーはこんな感じ。畳み込み対象の開始位置lastは畳み込み対象の終了位置initは初期値binary_opは引数を2つもつ関数のポインタです。第4引数を省略すると、operator+()が畳み込み関数として使用されます。注意ポイントは、accumulate()を使用する場合は、numericをincludeしないといけないという点です。algorithmではないので間違えないように!!やばいぞ、C++。C++好き度が上がりました。cpp2010年11月16日火曜日トポロジカルソート今日は、SRMの過去問をトポロジカルソートで解いてみた。有向グラフのトポロジーに注目したソートですが、トポロジーって一体・・・、なんか他にも似たような言葉がたくさんあるような・・・。物事の概念を意味・関係などで定義したもので、今回はトポロジカルソートです。簡単に言うと、どの接点も自分の子孫より先に来るようにソートすることです。Makeでコンパイルする順序を決めたり、PERTのスケジュール管理で使われるみたいです。