2014-08-01から1ヶ月間の記事一覧
class RevealTriangle { public: vector <string> calcTriangle(vector <string> Q) { int N = Q.size(); int cnt; do { cnt = 0; for(int i=0; i</string></string>
解法 メモ化再帰 class RandomSort { public: map<vector<int>, double> mp; double getExpected(vector <int> permutation) { if(mp.count(permutation)) { return mp[permutation]; } double ret = 0.; double cnt = 0.; for(int i=0; i</int></vector<int>
class TheLuckyNumbers { private: int solve(long long n, int a, int b) { if(n > b) return 0; return solve(10*n+4, a, b) + solve(10*n+7, a, b) + (a<=n&&n<=b); } public: int count(int a, int b) { return solve(0, a, b); } };
解法 与えられたデータを用いたとき、最大の対象な分割のための線分の数を求める。 要素数が8までなので、next_permutation で回して累積和を取り+50となる要素のペアを数え上げる。 #define ALL(x) (x).begin(), (x).end() class SymmetricPie { public: in…
以下のコードは他の人の解答を参考にした。 int ps[3], pr[2], now[3]; bool cards[53]; int main() { while(1) { memset(cards, 0, sizeof cards); for(int i=0; i<3; i++) cin >> ps[i], cards[ps[i]] = true; for(int i=0; i<2; i++) cin >> pr[i], cards…
解法 カタラン数を求めるとよい。 http://mathworld.wolfram.com/CatalanNumber.htmlWikipediaの格子状の経路数え上げの項目が参考になる。Nを1増加して計算したうえで、はじめの経路分を引けばよい。 class FIELDDiagrams { public: ull nCr(ull n, ull r){…
解法 テストケースが書いていないが、3点より特定した一つの円の周上に1点が乗っかるか調べる O(N^4) の解法で正答できるようになっている。3点から一つの円を特定する方法は垂直二等分線の交点である。 2点のペアの中点と、その2点のペアのベクトルを9…
解説 乗数決め打ちして二分探索で解こうとしていたけど、乗数の大きい物から計算していけばその必要はなかった。2^60 = 1.1529215e+18 > 10^18 は覚えておいたほうが良い。 また、桁落ちを考慮してEPSを挟む必要がある(正答コード見てわかりました) class …
解法 計算量が3*10^9くらいになるので嘘解法かもしれないが、いもす法で解いた。 #include <bits/stdc++.h> using namespace std; #define MAX (1000000) int main() { int N, M; while(cin >> N >> M && (N|M)) { int arr[MAX+1] = {}; for(int i=0; i<N; i++) { int s, t; cin >> s >> t; arr[s] ++;</n;></bits/stdc++.h>…
解法 #include <bits/stdc++.h> using namespace std; int main() { int K; while(cin >> K && K) { int N, M; cin >> N >> M; for(int i=0; i<K; i++) { int X, Y; cin >> X >> Y; if(N == X || M == Y) { cout << "divisa" << endl; } else { if(N < X && Y > M) cout << "NE" << endl; if(N > X && </k;></bits/stdc++.h>…
解法 dp[MICROの作業をした日数][GOOの作業をした日数][連続日数][現在取りかかっているプロジェクト 0 or 1] := パターン数 としてメモ化再帰。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int D, G; ll memo[35][35][35][2]; ll solve(int mfi</bits/stdc++.h>…
解法 直径を大きい順にソートして(1)r,b,r,b,... or (2)b,r,b,r,...の順で貪欲でつめる。red or blue の要素で直径が H 以上のものが尽きたら -1 を出力。そうでなければ長方形の残りの幅を越えた時点で最適。(1)と(2)の小さい方が答え。 class ColoringRect…