天下一プログラマーコンテスト2016予選A C - 山田山本問題
解説
a,...,zを頂点としてトポロジカルソート。
頂点数が少ないので、O(N3)のアルゴリズムでOK。
トポロジカルソートの参考サイト。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; bool G[26][26]; // 頂点iがjより前 bool used[26]; int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; FOR(i,0,N) { string s, t; cin >> s >> t; int j; for(j = 0; j < s.length() && j < t.length() && s[j] == t[j]; j++); if(j == t.length()) { cout << -1 << endl; return 0; } if(j == s.length()) continue; G[s[j]-'a'][t[j]-'a'] = true; } // トポロジカルソート // 頂点数が少ないのでO(26^3)でできる // O(E+V)のアルゴリズムもあり string ans = ""; FOR(i,0,26) { int u = 0; // 頂点uに注目 bool ok = true; for(;u < 26;u++) { if(used[u]) continue; ok = true; // v -> uの辺がなければ答えについか FOR(v,0,26) if(G[v][u]) ok = false; if(ok) break; } if(!ok) { cout << -1 << endl; return 0; } used[u] = true; ans += char(u + 'a'); FOR(v,0,26) G[u][v] = false; } cout << ans << endl; return 0; }
ARC067 E - Grouping
解説
dp[i][j] = i人未満のグループのみで、j人を分ける通り数とする。
このようにdpを定義すると、dpの更新式は以下のようになる。
i人のグループを一個も作らないとき、
残りのN-j人のうち、i人のグループをk個作るとき、
で割るのはグループを区別しないため重複があるので。
計算量はO(N3)のように思われるが、
なので、O(N2 logN)らしい...
また1000000007で割った余りを答えるので割り算をするときはフェルマーの小定理を使う必要あり。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> #include <deque> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; const ll MOD = 1000000007; const int SIZE = 1010; ll inv[SIZE],fac[SIZE],finv[SIZE]; void make(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i<SIZE;i++){ inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; fac[i]=fac[i-1]*(ll) i%MOD; finv[i]=finv[i-1]*inv[i]%MOD; } } ll Combination (int a,int b) { if(a<b) return 0; return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD; } ll dp[1010][1010]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,a,b,c,d; cin>>n>>a>>b>>c>>d; make(); FOR(i,0,1010) dp[i][0] = 1; FOR(i,a,b+1) { FOR(j,0,n+1) { if(dp[i][j] == 0) continue; if(j != 0) (dp[i+1][j] += dp[i][j]) %= MOD; ll p = 1; for(int k = 1; k <= d && j + i * k <= n; k++) { p = (((p * Combination(n - j - i * (k - 1), i) % MOD) * inv[k]) % MOD) % MOD; if(k >= c) (dp[i+1][j+i*k] += (dp[i][j] * p) % MOD) %= MOD; } } } cout << dp[b+1][n] << endl; return 0; }
感想
解けなかった。dpの練習しないと。
SRM607 div2 med PalindromicSubstringsDiv2
TopCoder Statistics - Match Overview
問題概要
- 文字列Sの中に回文が何個あるか
制約
- |S| ≦ 5000
解説
文字列Aが回文の時Aの両サイドに同じ文字が連結した文字列も回文となる。
同じ文字でない文字が連結したらその時点で回文では無くなる。
回文の中心がsiとなるような回文が何個あるかはO(|S|)で求められる。
よって中心の候補はO(|S|)なので、全体の計算量はO(|S|^2)で間に合う。
回文の長さが奇数の時と偶数の時で調べる必要がある。
コード
class PalindromicSubstringsDiv2 { public: int count(vector <string> S1, vector <string> S2) { string s = ""; FOR(i,0,S1.size()) s += S1[i]; FOR(i,0,S2.size()) s += S2[i]; int len = s.length(); int ret = 0; // even FOR(i,0,len) { int l = i, r = i + 1; while(l >= 0 && r < len && s[l] == s[r]) { ret++; l--; r++; } } // odd FOR(i,0,len) { int l = i, r = i; while(l >= 0 && r < len && s[l] == s[r]) { ret++; l--; r++; } } return ret; } };
SRM606 div2 med EllysNumberGuessing
TopCoder Statistics - Match Overview
問題概要
- Aさんが1以上1000000000以下の数字を思い浮かべる
- BさんがAさんが思い浮かべた数字がx1,x2,...,xnかどうか聞く
- Aさんは思い浮かべた数字とxとの差の絶対値yを答える
- Aさんが思い浮かべた数字が一意に定まる時はその答えを、複数考えられる場合は-1、矛盾する場合は-2を答えよ
制約
- n ≦ 50
- Aさんが思い浮かべる数字は1以上1000000000以下
解説
思い浮かべた数字の候補はxi±yiである。
map[候補となる数字] := 回答より候補となった回数とする。
候補となる数字は1以上1000000000以下であることに注意。
map == nとなる数字が1つだけならそれが答え、2つあるなら-1、1つもないなら-2。
コード
class EllysNumberGuessing { public: int getNumber(vector <int> guesses, vector <int> answers) { int n = answers.size(); map<int, int> MAP; FOR(i,0,n) { int c = guesses[i] + answers[i]; int d = guesses[i] - answers[i]; MAP[c]++; if(c != d) MAP[d]++; } int cnt = 0; int ret = 0; for(auto m : MAP) { if(m.second == n && m.first > 0 && m.first <= 1e9) { cnt++; ret = m.first; } } if(cnt == 0) return -2; else if(cnt == 1) return ret; else return -1; } };
SRM605 div2 med AlienAndGame
TopCoder Statistics - Match Overview
解説
1 * 1, 2 * 2, ...の正方形が作れるかどうか順に調べた。
左からi右からjのマスが正方形の左上として調べた。
コード
class AlienAndGame { public: int getNumber(vector <string> board) { int H = board.size(); int W = board[0].length(); int ret = 1; FOR(s,1,W+1) { FOR(i,0,H) { FOR(j,0,W) { bool ok = true; FOR(k,0,s) { if(i + k >= H) { ok = false; break; } if(!(board[i+k].substr(j, s) == string(s, 'W') || board[i+k].substr(j, s) == string(s, 'B'))) { ok = false; break; } } if(ok) ret = s; } } } return ret * ret; } };
SRM604 div2 med PowerOfThreeEasy
問題概要
- step k でx方向かy方向に3k進む
- stepは0から始まる
- xとyが与えられるのでその座標にちょうど到達できるか判定せよ
制約
- 0≦x≦109
- 0≦y≦109
解説
319 = 1162261467なので高々19ステップで制約の座標には到達できるかどうかわかる。
各stepでx方向に行くかy方向に行くか全探索O(219)。
コード
class PowerOfThreeEasy { public: string ableToGet(int x, int y) { int th[20]; FOR(i,0,20) th[i] = pow(3,i); FOR(i,0,1<<20) { int X = 0, Y = 0; FOR(j,0,20) { if(X == x && Y == y) return "Possible"; if((i>>j)&1) X += th[j]; else Y += th[j]; } if(X == x && Y == y) return "Possible"; } return "Impossible"; } };
SRM603 div2 Med SplitIntoPairs
TopCoder Statistics - Match Overview
問題概要
- 要素数が偶数の配列Aが与えられる
- Aの要素2つを選んでペアを|A|/2個作る
- ペアの積がX以上となるようなペアの最大数を求めよ
制約
- |A| % 2 = 0
- -109≦A≦109
- -109≦X≦-1
解説
Xが負であることがポイント。
偶数偶数と奇数奇数ペアは絶対に正になる。
できるだけ同じ符号同士でペアにすればいい。
符号が正である要素が偶数個あるなら全てのペアを同じ符号同士にできる(答えは|A|/2個)。
符号が正である要素が奇数個なら偶数*奇数のペアが1つできてしまう。
偶数の要素と奇数の要素の全ての組み合わせの積を計算して最大値がX以上であれば答えは|A|/2、そうでないなら|A|/2-1。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; class SplitIntoPairs { public: int makepairs(vector <int> A, int X) { int plus = 0; FOR(i,0,A.size()) { if(A[i] >= 0) plus++; } if(plus % 2 == 0) return A.size() / 2; else { ll mx = -2e9; sort(A.begin(), A.end()); for(int i = A.size() - 1; A[i] >= 0; i--) { for(int j = 0; A[j] < 0; j++) { mx = max(mx, (ll)A[i]*(ll)A[j]); } } if(mx >= X) return A.size() / 2; else return A.size() / 2 - 1; } } };
