http://www.topcoder.com/stat?c=problem_statement&pm=9824&rd=12179ソースは、これ。定型的なアルゴリズムがあるようですが、とりあえず、自己流で出力辺の無い接点を取り出して、その接点はグラフ集合からのぞいて・・・を繰り返しています。fill_n今日は、便利なSTLについて。fillfill_nを紹介します。その名の通り、配列やコンテナをある値で”埋める”ことができる関数です。初期化のときに重宝します。同じような標準関数にmemset()がありますが、こちらは1byte単位で値を初期化するため、charの初期化には有効ですが、intの初期化にはあまり都合がよくありません。(0で初期化するのであれば問題ありませんが、1や-1で初期化するのは面倒。詳しくは、memset()とmemcpy()を参照。)これに対して、fill()、fill_n()は、その型に対応した単位で初期化を実行できるためとても便利です。それでは、実際に動かしてみます。last)区間の要素をvalueにセットします。0;}次に、fill_n。first+n)までの要素をvalueにセットします。0;}要素数が可変なコンテナ(vectorなど)に対してはfill()を、要素数が固定長の配列の場合は、fill_n()を使うといいかと思います。直観でこの問題は簡単と思って、1時間もあれば・・って思ったけど、落とし穴があって結局3時間かかってしまった(泣)でも、初めて何にも頼らず自力で解けたというのは大きな進歩だと思う。これが、赤色への記念すべき歴史的第一歩となることを願うばかりである。ヘタレすぎるコードですが、記念ということで貼っておきます。基本的な動的計画なのですが、・・・、同じ高さのところの処理をどうするかでかなり悩みました。解説や赤色の人のコードを参考にスマートな解法を探ってみます。SRM2010年11月10日水曜日ヒープを作ってみよう!今日は、ヒープを自分で実装してみます。昔、「二分木は配列で実装できます。」みたいなことを読んだことがありました。そのときは、??だったが、今ならできる!!では、早速ソースを。tail;};で、ちゃんと動くか確認してみましょう。0;}はい、動きました。実際に自分で作ってみると、ヒープのオーダーについての理解も深まります。n)なのは明らかですね。部分和を列挙する今日は、昨日練習したTopCoderの問題について書きます。numberを列挙せよ。そのような組み合わせが複数個ある場合は、個数が最小のもの、さらにそれが複数個ある場合は、辞書順で最小になるものを求めよ。詳しくは、上のTopCoderのサイトを参照ください。赤い人のコードを参考に復習しました。1.ですが再帰で書くとかなりスマートに書けます。2.は部分和問題と同等の方法で書けます。numberの最小値をキャッシュします。numberをvectorにぶち込んでキャッシュしてました。これだと、メモリ制限や時間制限でoutになりました。)3.は2.で作った配列を元に経路復元みたいなことをやります。その際、なるべく小さい数をたくさん取るように(辞書順で小さくなるように)greedyで復元します。以下、(赤い人を参考に)私が書いたコードを張っておきます。}};あと、気付きですが、TopCoderの過去問を解くのはPOJを解くよりも良いかもしれません。問題のレベル分けがきちんとなされている赤い人のコードや解説(editorial)が読めるすべての問題が種類別にカテゴライズされている。3.のカテゴライズは今日気付きました。manipulation」とか「recursive」とか選択できるみたいです。swapSTLを使いこなすことは、アルゴリズムコンテストを勝ち抜くうえでとても重要である。しらないSTLがたくさんあるようだ。Algorithmsのswap()。その名のとおり、変数の値をswapできます。0;}次に、swapを用いて選択ソートをしてみます。0;}これは、かなり便利そう。これから、重宝しそうです。algorithmsの紹介。配列の最大値、最大解(最大値を与える要素)を出力するプログラムを普通に書いてみます。0;}これが何気に面倒臭かったりします。最大値だけならそうでもない(ループ内でmax使えばいいだけ)ですが、最大値を与えるindexを求める場合は、ちょっとだけソースコードが長くなってしまい面倒です。Algorithmsの出番です。最大値・最大解と、ついでに最小値・最小解も求めてみましょう。0;}かなりシンプルですね。戻り値はiteratorですが、配列の場合はポインタとの引き算もできるみたいです。Postsmemset()とmemcpy()恥ずかしながら、Cのmemset()とmemcpy()を今まで使ったことがなかった。みたいな話を聞いたことがあったので、「あーじゃ要らない機能なんだー。editorialに投稿された解答がmems...便利なPythonライブラリ(5)retryデコレータつけるだけで、リトライしてくれるという便利ライブラリ。失敗するかもしれない不安定な関数に@retryをつけると成功するまで実行してくれる。ret...S3のファイルを一般公開するAWSのS3のファイルを一般公開する方法について説明します。2つの場合に分けて説明します。本番中ゴリ押し解を思いつくには思いついたのだが、C++でマルチスレッドの処理を書いたことが無くて、ごにょごにょやってるうちにタイムアップとなってしまった。C++...C#入門(9)Action、Func、Predicateの違いAction、Func、Predicateについて簡単に整理しておく。メソッドへのDelegate。メソッドへのDelegate。スライド区間に対するクエリ処理の種類とそれに対するアルゴリズムをいくつか紹介します。「スライド区間」の定義ですが、窓関数のようなものを想像してください。まではコンピュータの力を使って正多面体をt色以下で塗るパターン数を数えていました。今回は手計算で計算してみようと思います。そのためにはまず回転を表す対称群をうまく列挙するために回転軸について考える必要があります。見聞きする木の用語を整理しておく。節点vから最も離れた節点をwとする。w)の長さをvの離心数と呼ぶ。記号で表すときは、ε(v)と書く。使って遊んでみました。いった便利な機能を提供してくれるテストフレームワークです。repor...キャッシュヒット率の測定perfというツールを使ってキャッシュヒット率を測定してみた。キャッシュの影響なんてたかが知れていると甘くみていたら、痛い目るので要注意。知らない用語がちらほらあったので、簡単にまとめておく。