- 2009-01-22 (木) 2:53
- TopCoder
Place: 288
Score: 113.71(Total)=113.71(250)+Compiled(500)+Unopened(1000)
Rating: 1751 → 1751
うーむ，最近酷い有様なんですがどうにかならないものですかねー．わざわざテスト期間にもかかわらず受けたというのに．
TopCoder SRM 433, DIV I, 250, MagicWords
Overview
文字をローテートさせた時にちょうどK回一致するものをmagic wordと呼ぶことにする．
文字列のリストが与えられるのでそれを並び替えて結合してできる文字列（重複あり）のうち，magic wordな種類数を答えよ．
Comment
問題の読み違いをしてしまい，というか最初は正しく読んでいたのに一瞬例があわない気がしてしまったために気づけば45分ほどもかけてしまっていたために乙．さらに文字列の比較をO(1)と考えてしまい8!*160だから余裕とか言ってコード書いてあぼん．最終的には約数のみを調べる仕様に変えてどうにかパス．
001: #include <vector>
002: #include <string>
003: #include <algorithm>
004: #define rep(i,a) for(int i=0;i<(a);++i)
005: #define all(a) (a).begin(),(a).end()
006: using namespace std;
007:
008: struct MagicWords {
009: int count(vector<string> S, int K) {
010: int sum = 0, len = 0; vector<int> A(S.size());
011: rep(i, S.size()) A[i] = i, len += S[i].size();
012: do {
013: string a = ""; int c = 1; vector<int> k(len);
014: rep(i, S.size()) a += S[A[i]];
015: for (int i = len; 1 < i; i--) {
016: if (len % i != 0 || k[len / i]) continue;
017: int d = len / i;
018: if (a != a.substr(d) + a.substr(0, d)) continue;
019: for (int j = d; j < len; j += d) k[j] = 1;
020: }
021: rep(i, len) c += k[i];
022: if (c == K) sum++;
023: } while (next_permutation(all(A)));
024: return sum;
025: }
026: };
002: #include <string>
003: #include <algorithm>
004: #define rep(i,a) for(int i=0;i<(a);++i)
005: #define all(a) (a).begin(),(a).end()
006: using namespace std;
007:
008: struct MagicWords {
009: int count(vector<string> S, int K) {
010: int sum = 0, len = 0; vector<int> A(S.size());
011: rep(i, S.size()) A[i] = i, len += S[i].size();
012: do {
013: string a = ""; int c = 1; vector<int> k(len);
014: rep(i, S.size()) a += S[A[i]];
015: for (int i = len; 1 < i; i--) {
016: if (len % i != 0 || k[len / i]) continue;
017: int d = len / i;
018: if (a != a.substr(d) + a.substr(0, d)) continue;
019: for (int j = d; j < len; j += d) k[j] = 1;
020: }
021: rep(i, len) c += k[i];
022: if (c == K) sum++;
023: } while (next_permutation(all(A)));
024: return sum;
025: }
026: };
TopCoder SRM 433, DIV I, 500, Setting Tents
Overview
与えられる長方形の格子点を使ってできる菱形の数を答えよ．
Comment
変なバグに苛まされる．あともう少し時間があればと思うのはいつものこと．とりあえず以下のコードは事後書いたもの．
001: #include <algorithm>
002: using namespace std;
003:
004: struct SettingTents {
005: int countSites(int N, int M) {
006: int s = 0;
007: for (int x = 1; x <= N; x++)
008: for (int y = 0; y <= M; y++)
009: for (int yy = 1; yy <= M; yy++) {
010: int xx = yy * y / x;
011: if (N < xx || yy * y % x != 0) continue;
012: if (x % 2 != xx % 2 || y % 2 != yy % 2) continue;
013: s += (M - max(yy, y) + 1) * (N - max(xx, x) + 1);
014: }
015: return s;
016: }
017: };
002: using namespace std;
003:
004: struct SettingTents {
005: int countSites(int N, int M) {
006: int s = 0;
007: for (int x = 1; x <= N; x++)
008: for (int y = 0; y <= M; y++)
009: for (int yy = 1; yy <= M; yy++) {
010: int xx = yy * y / x;
011: if (N < xx || yy * y % x != 0) continue;
012: if (x % 2 != xx % 2 || y % 2 != yy % 2) continue;
013: s += (M - max(yy, y) + 1) * (N - max(xx, x) + 1);
014: }
015: return s;
016: }
017: };
- Newer: GoogleカレンダーとiCalの同期方法
- Older: PECLを作る
Comments:0
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2009/01/topcoder-srm-433/trackback/
- Listed below are links to weblogs that reference
- TopCoder SRM 433 from 超現実いもす(imos)の日記