カードの順番を逆にしてTrie木を作り、ノードの数を数えて終わりです メモリが足りなかったりTLEしたりで、何どもやり直しました int main() { const string firstLetters[] = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"}; const string second…

フェリーには詰め込めるだけ詰め込めば良い 貪欲にシミュレーションするだけです int count(int l, const vector<int>& lengths) { int answer = 0; int sum = 0; for (vector<int>::const_iterator it = lengths.begin(); it != lengths.end(); ++it) { sum += *it; i</int></int>…

何日目にどの問題を解いているかというDPです この解答ではダイクストラ法チックに解いています int B[512]; int A[512]; int Bs[512][512]; int As[512][512]; int main() { int M, P; cin >> M >> P; for (int i = 0; i < P; ++i) { cin >> B[i] >> A[i]; …

ソートして貪欲にシミュレーションすれば良いようです struct Cow { ll t; ll d; bool operator<(const Cow& rh) const { return d * rh.t > rh.d * t; } }; int main() { int N; cin >> N; vector<Cow> cows; for (int i = 0; i < N; ++i) { Cow cow; cin >> cow</cow>…

最長部分繰り返し文字列という問題だと思います Spaghetti Sourceのライブラリをお借りしました #define SETNUM(rank, i,s) \ NUM[i] = make_pair(make_pair(rank[i], i+s

直接解をを求めようとすると難しいです ある値が与えられたとき、その値が解として正しいかどうかは線形時間で求めることができます コレを使って解を二分探索で求めることができます int pickupGreedy(const vector<int>& ds, int length) { int result = 0; int</int>…

k-th shortest pathという有名問題です Spaghetti Sourceのライブラリを使用しています static const int INF = INT_MAX / 2; #define REP(i,n) for(int i=0;i<(int)n;++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #def…

サイズが大きくないためDPで解けます 有るか無いかのビットフラグをキーにする典型的なDPです bool isValid(int value, int N) { bool last = false; for (int shift = 0; shift < N; ++shift) { if (last && (value & (1 << shift)) != 0) { return false; …

ハフマン木を作る要領で解けるようです 分割するのではなく、全部バラけた状態からくっつける方向で考えると解けるようです int main() { int N; cin >> N; priority_queue<ll, vector<ll>, greater<ll> > ls; for (int i = 0; i < N; ++i) { ll l; cin >> l; ls.push(l); } ll </ll></ll,>…

うまい解法が思いつかなかったためテーブル埋込みを使いました 2^20個を1セットとしてテーブルに持たせ、端数の部分を全探索しました int numofbits5(ulong bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (…

主人公(?)の位置と正方形の一辺を表すベクトルで全探索です N int main() { static char farm[128][128]; static char firstLine[128]; gets(firstLine); const int N = atoi(firstLine); for (int x = 0; x < N; ++x) { gets(farm[x]); } int answer = 0; f…

スタックを使って高さを管理していけば解けるようです int main() { vector<int> stk; int N; cin >> N; ll sum = 0; for (int i = 0; i < N; ++i) { int h; cin >> h; while (!stk.empty() && stk.back() <= h) { stk.pop_back(); } sum += stk.size(); stk.push</int>…

各桁のビットに着目して解いていく 各桁ごとにビットが立つ確率を求め、それらを2^i倍して足していけば良い 答えが合わずに困ってたら、1〜nまでで考えていたのが原因だった。本当は0〜n-1 G++で提出したらWA、C++だとACだった。やっぱり納得が行かない。 in…

答えの値で二分探索を行った 初めkの値の意味を取り違えており、毎ターンk+1乾燥させるようにしていた。WA 入力の直後に--kしたら、0割りでRE k==1の場合は自然乾燥させる場合と等価になるので、max_elementを返せば良い static int a[128 * 1024]; bool che…

問題文を見て目を疑った どう切っても良いので、とりあえずスライスしてみた コンパイラにG++を選択するとWAでC++だとPE or ACという、ちょっと納得の行かない結果になった %.15lfだとOLE、%.10lfだとPE、%.9lfだとACというのも納得が行かなかった int main(…

Twitter上で@tozangezanさんがつぶやいていた問題 サイズが500000なのでO(N log N)のアルゴリズムまでなら通る可能性が高い この回答では最初に500000まで求めてから、最後に入力を処理している #include <iostream> #include <set> using namespace std; static int a[5000</set></iostream>…