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

始められるやつから順番に始めて行く。ただそれだけ。サンプルデータでは合ってるんだけど、システムテストが通らない。。。何でだ。 #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>…

初めて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より真に小さい部分グループに分かれる。この問題の構…

自分の使っている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>

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

クラス Cryptography 整数リストが与えられる。その中から一つだけを選んで+1する時、結果のリストの積を最大にするには？ 一番小さい数をインクリメントして積を返す これくらいの問題サイズなら全列挙しても良い。 red coderでも全列挙している人多し。 面…

メモ 便利リンク http://www.otinn.com http://iajust3.scm.ca/tcstats 目安として、1億回の演算くらいなら2秒で終わる でかい数の掛け算は、overflowに注意。