Codeforces

Codeforces Croc Champ 2012 - Final D. T-shirt

重量mのTシャツをk枚以上持ってる期待値 それをすべての{m, k}について計算し、大きいものからn個とっていけばいいです。 普通にDPすると案の定TLEなので、僕は必要となる{m, k}の組がせいぜい2n個であることに注目し、遅延評価しました。 #include <cstdio> #includ</cstdio>…

Codeforces #121 Div1 D. Metro Scheme

(辺の数が奇数の頂点数)/2本の線は最低でも存在する事がすぐ分かります。 また、どのような線と円の置き方をしても、そこから線を結合(a~bという直線とb~cという直線をa~cという直線で置き換える)するという動作だけでその本数まで直線を減らせる事がわかり…

Codeforces #121 Div1 E. Lucky Array

解法としては平方分割です。 本来ならadd,count共にO(√n)ですが、countにはラッキーナンバーの数、30個程度が定数として掛かります。 よって最悪ケース、つまりすべてcount(2, n)ならば √n*m*30で約100000000、平方分割の定数もあって危ないです。 僕は絶望…

Coreforces #157 Div1 D. Little Elephant and Broken Sorting

n,m=1000なのでnmかな〜〜と言った感じで考えてたら解けました 結局O(nm)ですね多分 汚いプログラムになってしまいましたが、 dp[i][j](i<j):その時に考えられる数列のパターン(2^m通り)のなかで、i番目がj番目より大きくなっている物の可能性、割合 #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> …</sstream></vector></set></algorithm></iostream></ctime></cstring></cmath></j):その時に考えられる数列のパターン(2^m通り)のなかで、i番目がj番目より大きくなっている物の可能性、割合>

Codeforces #192 Div1 D The Evil Temple and the Moving Rocks

概要 石が動いていく、動くと止まったときに音が鳴る こどふぉのサイト見てください 回答 たぶん123779回鳴る回答です。通りました >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.v ^<.<.<.<.<.<.<.…