- 2009-02-24 (火) 22:55
- TopCoder
Place: 163
Score: 1052.03(Total)=238.18(250)+333.84(500)+480.01(1000)
Rating: 1884 → 1909
今回はコーディングゲー．相変わらず思いついても実装するまでが長いのであまりのびず．でもとりあえず満足．
TopCoder Open Qualification Round 1, 250, Sorting With Permutation
Overview
順序を入れ替えて昇順に変える置換の内，最小の物を求めよ．
Comment
アルゴリズムはすぐ思いつくもののコードに直すのが面倒なタイプの問題（だと個人的には思った）．
Solution
O(N2)が許されるので非効率な方法で解くのも手．以下のコードはO(NlogN)にしてみたもの．
001: #include <vector>
002: #include <map>
003: #include <algorithm>
004: #define rep(i,a) for(int i=0;i<(a);++i)
005: #define vec vector
006: #define pb push_back
007: using namespace std;
008:
009: struct SortingWithPermutation {
010: vec<int> getPermutation(vec<int> a) {
011: vec< pair<int, int> > b; vec<int> r;
012: rep(i, a.size()) b.pb(make_pair(a[i], i);
013: sort(b.begin(), b.end());
014: rep(i, a.size()) b[i].first = i, swap(b[i].first, b[i].second);
015: sort(b.begin(), b.end());
016: rep(i, a.size()) r.pb(b[i].second);
017: return r;
018: }
019: };
002: #include <map>
003: #include <algorithm>
004: #define rep(i,a) for(int i=0;i<(a);++i)
005: #define vec vector
006: #define pb push_back
007: using namespace std;
008:
009: struct SortingWithPermutation {
010: vec<int> getPermutation(vec<int> a) {
011: vec< pair<int, int> > b; vec<int> r;
012: rep(i, a.size()) b.pb(make_pair(a[i], i);
013: sort(b.begin(), b.end());
014: rep(i, a.size()) b[i].first = i, swap(b[i].first, b[i].second);
015: sort(b.begin(), b.end());
016: rep(i, a.size()) r.pb(b[i].second);
017: return r;
018: }
019: };
TopCoder Open Qualification Round 1, 500, Square Free Numbers
Overview
Square Freeを約数に平方数がない数と定義した時，min以上max以下の整数でSquare Freeな数の個数を求めよ．
Comment
純粋に数えると負けそうだなと思って敬遠していたら結局それだったという．もう少し早く踏みきれよというお話ですね．
Solution
篩っぽい感じで解くと解ける．
001: #include <vector>
002: using namespace std;
003: typedef long long ll;
004:
005: struct SquareFreeNumbers {
006: int getCount(ll a, ll b) {
007: vector<int> v(b - a + 1, 1); ll c = v.size();
008: for (ll i = 2; i * i <= b; i++)
009: for (ll j = a / i / i * i * i; j <= b; j += i * i)
010: if (a <= j) c -= v[j - a], v[j - a] = 0;
011: return c;
012: }
013: };
002: using namespace std;
003: typedef long long ll;
004:
005: struct SquareFreeNumbers {
006: int getCount(ll a, ll b) {
007: vector<int> v(b - a + 1, 1); ll c = v.size();
008: for (ll i = 2; i * i <= b; i++)
009: for (ll j = a / i / i * i * i; j <= b; j += i * i)
010: if (a <= j) c -= v[j - a], v[j - a] = 0;
011: return c;
012: }
013: };
TopCoder Open Qualification Round 1, 1000, Prime Pairs
Overview
2つ目以降でどれを除けば全てを素数になるペアに分けることができるか．
Comment
二部マッチング(笑)と思ったが，問題は二部マッチングのコードを持っていなかったという＼(^o^)／
Solution
スパゲッティー様々なのでソースはなし．
TopCoder Open Qualification Round 1関連リンク
個人ブログ
- Newer: Cell Challenge 2009 予選ラウンド
- Older: TopCoder SRM 435
Comments:0
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2009/02/topcoder-open-qualification-round-1/trackback/
- Listed below are links to weblogs that reference
- TopCoder Open Qualification Round 1 from 超現実いもす(imos)の日記