はじめに Codeforces Round #344 Div. 2 Prob. A. Interview 問題：http://codeforces.com/contest/631/problem/A ある配列xについて、lからrまでの区間ですべての要素のorをとったものを、f(x,l,r)と定義する。 与えられた２つの配列a,bについて、max f(a,l,r)+f(b,l,r)を求める。 考え方 lとrについて全探索するだけ。計算量はO(n^2)。Div2のA…
Read more...はじめに Codeforces Round #344 Div. 2 Prob. B. Print Check 問題：http://codeforces.com/contest/631/problem/B 行か列を一気に色（数字で表現）で塗る。最後の状態を出力する。 考え方 各行、各列で最後に塗られた色と、塗られた時間を記録する。各要素は属する行と列の遅く塗られたほうの色になる。計算量はO(n*m + k)。 解法
Read more...はじめに Codeforces Round #344 Div. 2 Prob. C. Report 問題：http://codeforces.com/contest/631/problem/C 数列が与えられる。先頭からr番目の要素までを、降順または昇順でソートするクエリが順番に与えられる。最後の状態を出力。 考え方 クエリをrでソートして、後ろから確定するかんじ。確定されていない要素の中でのmaxかminの要素が後ろから並んでいく。確定されていない要素はmultisetで管理した。計算量はO…
Read more...はじめに CODE FESTIVAL 2015 予選B D問題 問題：http://code-festival-2015-qualb.contest.atcoder.jp/tasks/codefestival_2015_qualB_d 解けなかったのでブログに書いておく。 考え方 左方向に、すでに黒く塗られたところを飛ばしながら黒く塗っていく。 →黒く塗られた区間をsetで持ってマージしたりしながらシミュレーションするだけ。O(nlogn) これを解いた時は、競プロから離れすぎていてset…
Read more...はじめに Codeforces Round #333 Div. 2 Prob. A. Two Bases 問題：http://codeforces.com/contest/602/problem/A 解けなかったのでブログに書いておく。 考え方 やるだけ 全部mainに書いていたら、入力を受け取るvectorの初期化時に、サイズを添えるコンストラクタ呼び出しで変数を間違えた。vector<int> x(n),y(n);とかしていた。 x用のvectorの宣言時に、m…
Read more...はじめに Codeforces Round #333 Div. 1 Prob. A. The Two Routes 問題:http://codeforces.com/contest/601/problem/A Codeforces Round #333 Div. 2 Prob. C. The Two Routes 問題：http://codeforces.com/contest/602/problem/C…
Read more...はじめに Codeforces Round #333 Div. 2 Prob. B. Approximating a Constant Range 問題：http://codeforces.com/contest/602/problem/B 与えられた数列で、minとmaxの差が1になる区間の最大サイズを求める。 解けたけど効率悪い実装していたので書いておく。 考え方 multisetに数字を突っ込んだり削除したりしながらしゃくとりするだけ。計算量はO(nlogn) ACしたけどmultiset…
Read more...はじめに Codeforces Round #332 Div. 2 Prob. C. Day at the Beach 問題：http://codeforces.com/contest/599/problem/C 解けなかったのでブログに書いておく。 考え方 重複がある数列をソートしたいとき、ある区間でのソートが全体でのソートと一致した数列になるかどうか、という問題はその区間での各数字の出現回数が一致することを調べればよい。 →mapで数えて一致するかどうかを確認する。毎回map…
Read more...はじめに Codeforces Round #330 Div. 2 Prob. B. Pasha and Phone 問題：http://codeforces.com/contest/595/problem/B 解けなかったのでブログに書いておく。 考え方 各ブロックが、biで始まらないかつaiで割り切れる数字で構成される組み合わせの数え上げ（のMOD）。 →各ブロックを条件の通りで数えた後掛け算してmodするだけ 解けなかったのはstlのpowの返り値がdouble…
Read more...はじめに Electron( http://electron.atom.io/ )使ってみてえという気持ちが高まったのでCygwinにNode.jsをインストールしようとしたお話し。 結論：Cygwinはサポート外でいろいろ試しても超古いバージョンしか動かなかった。普通に公式からWindows用のバイナリをインスコしようぜ。 今回はWindows10にNode.js 5.0.0をインストールした。 Node.js公式( https://nodejs.org/en/ ) Cygwin…
Read more...はじめに CODE FESTIVAL 2015 予選A D問題 問題：http://code-festival-2015-quala.contest.atcoder.jp/tasks/codefestival_2015_qualA_d 解けなかったのでブログに書いておく。 考え方 Xを決めたとき、「全員がX回移動できるときにすべて埋められるかどうか」は整備士を左からなめていって高速に判定できる。 →二分探索で最大のXを求める。 制約を見てもdp…
Read more...はじめに CygwinにC++用行列計算ライブラリEigenをインストールする方法です。 公式：http://eigen.tuxfamily.org/index.php?title=Main_Page 依存の解決 以下のパッケージをcygwinのsetup.exeからインストールしてください。 gcc-g++ gcc-fortran make cmake wget（ダウンロードにつかう） （正直よくわからん。追加で必要なもの知っていたら教えてくださるとうれしいです。） インストール wget…
Read more...はじめに Cygwinに高速特異値分解ライブラリredsvdをインストールする方法です。 redsvdを使うと大規模疎行列に対する特異値分解が高速に計算できるらしい。 作者のブログ：http://hillbig.cocolog-nifty.com/do/2010/08/redsvd-aa59.html 公式：https://code.google.com/p/redsvd/ 依存の解決 redsvdはEigenを使っているのでインストールしてないなら、CygwinにEigen…
Read more...はじめに 日本語の自然言語処理に欠かせない形態素解析エンジンMeCabをCygwinにインストールします。 MeCabの最新バージョンは0.996ですが、Cygwinでは0.996がビルドに失敗するため、0.98を使ってる人が多いようです。 少し前までは、0.99xをビルドできるようにするパッチを公開している方が居たようですが、現在は非公開になってしまいました。 僕もずっとそのパッチを探していたのですが、見つからなかったので作りました。 依存の解決 以下のパッケージをcygwinのsetup…
Read more...はじめに SciPyというライブラリを使うとPythonで簡単に最適化問題が解けます。以下にインストール方法を書いておきます。環境はWindows8.1、Cygwin64です。Python3を使うならpipをpip3に適当に読み替えてください。 pipとmatplotlibを先にインストールしておきましょう。 Cygwin上でpipとsetuptoolsをインストールする方法 Cygwin上でMatplotlibをインストールする。 依存の解決 以下のパッケージをcygwinのsetup.exe…
Read more...はじめに nanocでfontawesome使えるようにするのに手間取ったので手順をメモする。 gemfileに'font-awesome-sass'を追加 あぷでと fontawesomeのデータを追加 fontawesome.zipをダウンロードして解凍して中身のfontsフォルダだけcssと同じディレクトリ（/stylesheets/）にコピー compassのこんふぃぐについか scssファイルについか nanocのコンパイルでスルーされるように設定 おわり 色変えたいなら
Read more...はじめに nanocでbootstrapを使おうとしたときに、bootstrapで使われているLessが動かなくて困りました。 nanoc+bootstrapのサンプルはここ(https://github.com/mmc1ntyre/nanoc-bootstrap) （たしか）windowsとcygwinはパスの形式の違いに由来する問題で動きませんでした。（もうだいぶ前のことで詳細は覚えていない。また必要になった時にやったら書きます） 'gem install less'して'lessc…
Read more...はじめに Matplotlibの1.4.0がリリースされたようです。 それに伴ってCygwin上でMatplotlibをインストールする。で書いたバグも直っているようです。記事に書いたパッチの適用は必要なくなりました。 つまり、依存するパッケージをインストールして、pipを動くようにしたらpip install matplotlibとするだけでインストールは完了です。 （アップデートならpip install -U matplotlib…
Read more...はじめに Rubygemsが動かない ので、直しました。 選択肢 apt-cygを使うなら、ruby自体のバージョンを2.1に上げれば動きそう 64bit版Cygwinをインストールしてapt-cygするまで(http://dqn.sakusakutto.jp/2013/12/64bit_cygwin_apt-cyg.html) Cygwinrbenvとruby-buildで最新のrubyを入れる(http://dqn.sakusakutto.jp/2013/12/cygwin_rbenv…
Read more...はじめに nanocでレイアウトをいじりながらデザインを試行錯誤する時には、 nanoc view でローカルホストのサーバーを起動し、ブラウザでlocalhost:3000を開くという一連の動作を何度も繰り返すことになります。 今回はCygwin上で作業を行ってるとします。Cygwinでは cygstart http://localhost:300…
Read more...はじめに Cygwin上でpipとsetuptoolsをインストールする方法で書いた、Cygwin64で最新版のpipが動かない問題の解決策がわかったので書き直しました。 Cygwinのsetup-x86_64.exeから、binutils と libuuid-devel の２つのパッケージを追加でインストールすれば動くようになります。64bitのwindows8とwindows7で確認しました。 一応以下に一連の手順を書いておきます。 依存の解決 pip…
Read more...!!!この記事の内容は古いです。 Cygwin上でMatplotlibをインストールする。 を参照してください。!!! はじめに 前回pipをインストールしたのはMatplotlibを使うためでした。 しかし、pip install matplotlibとするとビルド時にエラーを吐いて止まりました。 調べてみると、これはCygwin固有のバグのようで、既に報告されており次のバージョンでは直ると思います。 修正方法もわかっていたので、練習も兼ねてpatch…
Read more...!!!この記事の内容は古いです。 Cygwin上でpipとsetuptoolsをインストールする方法 を参照してください。!!! はじめに 最近Pythonを使うようになりました。 Windows8（とWindows7）、64bit、Cygwinという環境だとpipを使えるようにするのに手間取ったのでメモしておきます。 Rubyには標準でgemという便利なパッケージ管理ツールがついてきますが、Pythonには何もついてこないので自分でインストールする必要があります。今はpip…
Read more...はじめに MathJaxを使ってtex形式で書いた数式を表示できるようにしました。 通常はhtmlに数行追加するだけで使えるようになります。 ただ、markdownでも数式を書けるようにするためには、レンダラの定義が必要だったのでメモしておきます。 nanoc(http://nanoc.ws) Redcarpet(https://github.com/vmg/redcarpet) MathJax(http://www.mathjax.org) インストール まずはテンプレートにMathJax…
Read more...はじめに このブログでは記事をMarkdownで書いて、Redcarpetとnanocで静的なHTMLを生成しています。 Redcarpetは、レンダラを独自に定義することで拡張が可能です。 そこで、CodeRay使ってMarkdown内のコードブロックにシンタックスハイライトを適用してみます。 nanoc(http://nanoc.ws) Redcarpet(https://github.com/vmg/redcarpet) CodeRay(http://coderay.rubychan.de…
Read more...nanocという静的HTMLを吐き出すCMSを使ってブログを作ることにしました。 Rubyを勉強するきっかけも兼ねています。つまりRubyも1から勉強します。
Read more...