2011-07-01から1ヶ月間の記事一覧

追記

文字列以外に利用できるバッファサイズはc log n bits (cは任意の定数)となったみたいですね。 今メソッドの先頭で定義している変数は now_char : 英数字だけなら最大 7 bits eql_count : 最大 log(n/2) bits str_size : log(n) bits count : 最大 log(n/2)…

PFIのサマーインターンの問題を考えてみた

http://research.preferred.jp/2011/07/intern2011_problem/ 長さnの文字列中で出現回数が最大の文字をO(n)時間で答えるプログラムを書いてください。 但し、出現回数が最大の文字の出現回数はn/2より大きいとします。 条件として、文字列以外に利用できるバ…

花札シャッフル

ACM ICPCのこのページの問題文を参考にして書いてみた。 部分配列を連結してるから、もっとマシな書き方があるはず。 def getDatasets(lines) sets = [] while !(lines.empty?) set = {'n' => 0, 'cuts' => []} line = lines[0].split(' ') set['n'] = line[…

RubyのArray#dupで引っかかった

その引っかかった原因から。 2次元配列へのArray#map! あるテストケースにおいて、予期されるオブジェクトを作るために 元のオブジェクトをdupでコピー コピーしたオブジェクトに色々する メソッドの適用結果と比較 とするはずだったのに、結果がおかしい。 …