MovieSeatingnumFriends=1の場合を別に扱う必要がある。 #include <string> #include <vector> using namespace std; long long P( int n, int m ) { long long r = 1; for ( int i=0; i<m; i++ ) r *= n-i; return r; } class MovieSeating{public: long long getSeatings( int numFriends, vector <string> hall ) { int h = (int)hall.…</m;></vector></string>

DigitHoles class DigitHoles{public: int numHoles( int number ) { int hole[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 }; int ans = 0; for ( ; number>0; number/=10 ) ans += hole[number%10]; return ans; }};

BestApproximationDiv1A,Bの取り得る範囲を全部試しても間に合う。ただ誤差が怖い。本番の時はコメントアウトしているコードで通ったけど、例えば"%.10f"を"%.20f"とすると、 Problem: 250 Test Case: 10 Succeeded: No Execution Time: 221 ms Args: {656, …

Easy (250) 216.83 Medium (500) 0 Hard (900) 0 Challenge 0 Easyはfor(A=1;A

A decorative fence分からないのでカンニング。なるほど、途中まで板の長さを決めたときに残りの板の選び方が何通りあるかを先にDPで求めておくのか。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { const int M = 20; // [i][j][k] 残</algorithm></vector></iostream>…

Spell checker手抜きで編集距離=1としたらTLEだった。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; bool replace( string a, string b ); int main() { vector<string> dict; while ( true ) { string s; cin >> s; if ( s == "#" ) break; dict.</string></algorithm></vector></string></iostream>…

The dog task２部グラフの最大マッチング。 #include <iostream> #include <vector> #include <cmath> using namespace std; double dist( vector<int> a, vector<int> b ); /*int*/ vector<vector<bool> > maxmatch2( vector<vector<bool> > G ); /*int*/ vector<vector<int> > maxflow( vector<vector<int> > G, int s=0, int t=-1 ); i…</vector<int></vector<int></vector<bool></vector<bool></int></int></cmath></vector></iostream>

Gangsters動的計画法。O(NKT)は間に合わなかった。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, K, T; cin >> N >> K >> T; vector<int> t(N), P(N), S(N); for ( int i=0; i<N; i++ ) cin >> t[i]; for ( int i=0; i<N; i++ ) cin >> P[i]; for ( int i=0; i<N; i++ ) cin >> S…</n;></n;></n;></int></algorithm></vector></iostream>

Rating問題文の通りに実装。面倒。 #include <iostream> #include <vector> #include <sstream> #include <string> #include <algorithm> using namespace std; int main() { // Input const int N = 101; vector<vector<int> > team( N, vector<int>(2,-1) ); for ( int i=0; i<2; i++ ) { int n; cin >> n, cin.ignore(); i</int></vector<int></algorithm></string></sstream></vector></iostream>…

Defragment各ファイルを移動すべきクラスタは一意に定まる。そのようなクラスタが空いていればファイルを移動、空きがなければ位置が間違っているファイルを適当なクラスタに移動、が最善。O(n2)で間に合うようだ。 #include <iostream> #include <vector> using namespace std</vector></iostream>…

Parliamentグループは2つとは限らないのか。動的計画法。桁あふれするので、小さなNに対しての答えから法則を探した。 #include <iostream> #include <vector> using namespace std; int main() { int N; cin >> N; vector<int> v; int s = 0; for ( int i=2; s+i<=N; i++ ) v.push_</int></vector></iostream>…

Fence真面目に計算すると大変そうだけど、原点から見て360度のうちどれだけ壁が見えるかを考えれば良い。ある点を基準として最左と最右の点の角度を求める。ただし角度は最大で2π。 #include <iostream> #include <cmath> #include <algorithm> using namespace std; int main() { const </algorithm></cmath></iostream>…

BaseConfusionNまでの合計をs(N,B)とすると、答えはs(N,B)-s(M-1,B)。 s(N,B)は各桁に各数字がいくつ含まれているかを考える。例えばs(12,3)=0+1+2+10+11+12+20+21+22+100+101+102+110について、10の位には1が4個含まれていて、B+1を基数としたとき1*4*(B+1)…

LockersDivTwoDiv1より問題サイズが小さくなっている。 class LockersDivTwo{public: int lastOpened( int N ) { int ans = 1; for ( int n=0; ; n++ ) { int x=1; for ( int t=n; t>=1; t-- ) x = (x+t-1)/t*t; if ( x > N ) break; ans = x; } return ans;…

AverageAverage #include <vector> #include <numeric> using namespace std; class AverageAverage{public: double average( vector <int> numList ) { return (double)accumulate(numList.begin(),numList.end(),0) / numList.size(); }};</int></numeric></vector>

HanoiGoodAndBad問題文中のアルゴリズムを実装し、1手動かすごとに各円盤がどの棒にあるかを出力するようにして、法則を探した。 #include <vector> using namespace std; class HanoiGoodAndBad{public: int moves( int N, int Dave ) { vector<int> disk( N ); int d[2]</int></vector>…

偶数のみ追加の高速化が無くてもギリギリ通った。LockersDivOne #include <list> using namespace std; class LockersDivOne{public: int lastOpened( int N ) { if ( N == 1 ) return 1; list<int> locker; for ( int i=2; i<=N; i+=2 ) locker.push_back( i ); for ( </int></list>…

Easy (250) 107.46 今度は難しく考えすぎた普通に実装すれば間に合うのか。 Medium (500) 0 Hard (1000) 0 Challenge -25, -25, +50 TLEを狙うも失敗。実行時間の見積もりが難しい。 結果 1640 → 1619

BatchSystem待ち時間の平均を最小化とあるけどユーザー数は固定なので待ち時間の合計の最小化と同じ。あるユーザーの最後のジョブが終わる時刻がユーザーの待ち時間なので、同じユーザーのジョブはまとめて実行する。また、合計時間が短いユーザーからジョブ…

CircleMarket #include <vector> using namespace std; // a=b*x+yが成り立つ最小の非負整数yを返す int rem( int a, int b ) { return (a%b+b)%b; } class CircleMarket{public: int makePurchases( vector <int> openTime, vector <int> closeTime, int travelTime ) { int n</int></int></vector>…

Cryptography #include <vector> #include <algorithm> #include <numeric> #include <functional> using namespace std; class Cryptography{public: long long encrypt( vector <int> numbers ) { ++*min_element( numbers.begin(), numbers.end() ); return accumulate( numbers.begin(), numbers.end()</int></functional></numeric></algorithm></vector>…

NetworkSecurityトポロジカルソートの降順に処理を行う。自分が接続しているかつ、自分が接続しているクライアントが接続していないサーバーとの間にゲートを設置する。 #include <string> #include <vector> #include <set> using namespace std; class NetworkSecurity{public: </set></vector></string>…

BatchSystemRoulette待ち時間の平均を最小化とあるけどユーザー数は固定なので待ち時間の合計の最小化と同じ。あるユーザーの最後のジョブが終わる時刻がユーザーの待ち時間なので、同じユーザーのジョブはまとめて実行する。また、合計時間が短いユーザーか…

ChickenOraclelieCount人とliarCount人の答えを逆にして全員の答えを卵もしくは鶏にすると考える。答えを逆にできるのは、|lieCount-liarCount|以上、lieCount+liarCountおよびn-(lieCount+liarCount-n)以下、偶奇がlieCount-liarCountと一致する人数。 n-(l…

久しぶりのSRM。 Easy (250) challenge succeed Easyを難しく考えすぎることが多かったので、Easyは簡単だと自分に言い聞かせていたが、簡単に考えすぎた。 Medium (500) 251.84 Hard (1000) 0 Challenge 125 Mediumの合計をlong longにしていないコードを２…

InternetSecurityアルゴリズムが書かれているので、その通りに実装する。 #include <vector> #include <string> #include <set> #include <sstream> using namespace std; class InternetSecurity{public: vector <string> determineWebsite( vector <string> address, vector <string> keyword, vector <string> dangerous,</string></string></string></string></sstream></set></string></vector>…

旅行のため不参加。