端っこから順番に条件を満たすか調べていく。 本番ではシステムテストで落ちた。 seq2の最初の要素が正であるかのチェックを忘れていた。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> </stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

topcoder初参戦。 以下の繰り返し。 一番大きい数字を選んでポイントに加算。 選んだ数字を非負の範囲で1減らす。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #i</cstdlib></cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

幅優先探索で、行ける所全部に最小到達歩数を記録。 到達不可能地点があるかチェック。あるなら、return -1。無い場合、最大の最小到達歩数を返す。 障害物で行けない地点は、走査時に除いて考える。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #in</algorithm></map></vector></string></sstream>…

結構考えて、時間ぎりぎりで解答が分かった。 列の中で同じ色が続いている部分を「連」と呼ぶことにする。色が4色あるので、連の両サイドがどんな色だったかを気にせずに必ず「(連の長さ) / 2」ステップで連の内部及び連の両端で同じ色が連続しないように出…

基本的には、全ジョブの所要時間合計が少ないユーザのジョブから実行すれば良い。 但し、辞書式順で最小のものを返すために、次のようなソート処理を行った。 各ジョブ番号iに対して [user[i]の全ジョブの所要時間合計, user[i]が最初に出てくるジョブ番号, …

2分探索 コメントで消しているのは、n買い目の支払い後の残高を明示的に書いた公式。これだと、テストケース0で駄目だった。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #i</cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

第i月に入る収入は、第i月以降で最もリターンの高い投資機会(株とタイミングの組み合わせ)に全額投資するのが最も効率的 上の考察をそのままコードに落とすだけ。 maxGain=1で初期化しているので、ループの最初のretの更新ではretは変化しない。けど、こうし…

emacsの背景を灰色にしたら、yatexの数式が見づらすぎて困った。こんな時は、init.elに (custom-set-faces '(YaTeX-font-lock-formula-face ((((class color) (background light)) (:foreground "DarkRed")) )) '(YaTeX-font-lock-math-sub-face ((((class c…

semi parametric splineのアルゴリズム了解。 semi parametric でもCVは同じように計算出来るらしい。 取り敢えず速度無視で逆行列直接計算で実験。 データを確保。

始められるやつから順番に始めて行く。ただそれだけ。サンプルデータでは合ってるんだけど、システムテストが通らない。。。何でだ。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #inc</stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

union findという便利なアルゴリズムをこの間のtopcoder養成講座で知った。簡単そうなので、練習。ここでの問題は、縦横nマスの碁盤目に文字が入っている(これは長さnの文字列のサイズnのリストとして与えられる)時に、単一の文字から成る連結領域で最大のも…

初めてDPっぽい問題のDPっぽい解答方針を自分で立てられた気がする。 DPというのは、「昨日までの結果が分かれば今日の結果はすぐわかっちゃうぜ」という問題に対する汎用的なメソッドだということがやっと理解出来た。 初めてDPを習ったのは多分大学3年の算…

やるだけ。 topcoderはグラフは隣接行列の文字列表現で与えられるぽいのでそれの練習的な。 このコードでは重複の処理を考えたくないので2友達かどうかを示すフラグテーブルを構成しているけど、@chokudai さんのライブコーディングではちゃんと重複が起こら…

DPの問題 格子状の道のある格子から別の格子に行くには何通り？という典型的な問題と同じタイプ。 但し、動きが複雑なのでちょっと見通しにくくなっている。 また、格子状の道と違い、あるマスからあるマスまで行く時に、行き方によってステップ数が異なるの…

メモ化再帰版 再帰する時に、同じ計算を何回もやるような場合は、メモを入れちゃえば、圧倒的に早くなる。 DPと両方使えるようになりたい。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>…

だいぶDPとメモ化再帰を行き来出来るようになった。 ただ、下のコードは桁あふれでシステムテストが通らない。 桁あふれぢゃないのかな。だけど、手元では合ってるんだよな。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #inclu</utility></iostream></algorithm></map></vector></string></sstream>…

適当な人を1番と決めて、時計回りに2, .., nと番号を振る。この時、1と3が握手しちゃうと、2が誰とも握手出来ない。同様の理由で、1が握手し得るのは2, 4, ..., n だけ。で、1とiの人が握手すると円卓がnより真に小さい部分グループに分かれる。この問題の構…

次のような問題設定を考える。

対称性からの群論入門 (Undergraduate Texts in Mathematics)作者: M.A.アームストロング(Mark Anthony Armstrong),佐藤信哉出版社/メーカー: シュプリンガー・ジャパン株式会社発売日: 2007/11/09メディア: 単行本購入: 1人 クリック: 6回この商品を含むブ…

spline + 定数スプレッドモデルの実装 B-Splineを勉強しないと駄目かも。 さらにそれに時間発展を加える 時系列解析を勉強せよ。 まぁVARとcointegrationの辺りか。 注文の離散性を取り込んだモデル化を考える すると、ベストレートだけでなくて、第二第三の…

仕事で、マルチファクターアフィンな金利モデルを扱っている。これは、自分的にはイマイチ納得感が無い感じが最近しているので、メモ。 以下、ここで述べているマルチファクターアフィン金利モデルについて簡単に述べる。マルチファクターアフィン金利モデル…

Reduceという関数がある。 > Reduce(paste, letters) [1] "a b c d e f g h i j k l m n o p q r s t u v w x y z" '...'引数は無いので、使いたければ無名関数を経由する。 > Reduce(function(x, y)paste(x, y, sep="/"), letters) [1] "a/b/c/d/e/f/g/h/i/…

再来週までにやるべき事 spline + 定数スプレッドでモデル推定 取り敢えず、rで書こう。 遅ければ、そして、遅い時に初めてc++で書き直すことを考えれば良い。 JGBのask bidの数値であることを忘れて、一般的な設定の関数にした方が良い。 その内やること。 …

ファイル共有でファイルを共有しているPCへのパスは /Volumes 以下に出てくる。

自分の使っているtopcoderヘルプツールで自動生成されるコードでは、実装対象のクラスオブジェクトがmainの自動変数として宣言されていることに気付かずちょっとはまった。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set></set></utility></iostream></algorithm></map></vector></string></sstream>…

#include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; class InterestingDigits{ pub…</cmath></cstdlib></cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>

int型からはみ出してしまって撃沈 -> longに修正 このコードだと、N=1e9, M=1 でタイムアウトになるみたい。 whileループがN回(i.e. 1e9回)のループになっちゃう。 それ以前に、N=1000000000, M=999999999 でおかしな値が出ているな。 この問題は、それなり…

ビット演算の練習 ビット演算は優先順位がとても低いらしい。 if(combi & (1 今回、関数名が思い出せなくて使わなかったけど__buildin_popcountという関数があるらしい。 空でない組み合わせの数は n C m - 1 なので、注意。 各数字に対して使うか使わないか…

仮引数書くのが面倒だったのでポインタにしたら余計面倒だった。 #include <sstream> #include <string> #include <vector> #include <map> #include <algorithm> #include <iostream> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #include <cmath> using namespace st…</cmath></cstdlib></cstdio></stack></queue></cctype></set></utility></iostream></algorithm></map></vector></string></sstream>

割と素直な方針で提出したんだけど、システムテストで撃沈。どこでバグっているのか不明。 昼休みに直そうと思ったけど、コード紛失。