- 2009-02-13 (金) 12:53
- TopCoder
Place: 109
Score: 405.99(Total)=202.25(250)+203.74(500)+Opened(1000)
Rating: 1818 → 1884
最近思うのですが，自分の250が遅すぎです．というか読み間違いを度々するのどうにかなりませんかね．
TopCoder SRM 435, DIV I, 250, Cell Removal
Overview
二分木(各ノードは親の番号がわかっている)が与えられる．あるノードを削除した時の残りの葉の個数を答えよ．
Comment
なにやら最初はトポロジカルソート済みの物が与えられると勘違いして組んでしまいタイムロス．まぁそもそも組むのも遅かったけど．
Solution
O(N2)が許されるので再帰で書くと楽．自分が葉であれば1を，削除対象であれば0を，木であれば子の合計を返せばおのずと葉の数が出るのでそのコードが以下の通り．
001: #include <vector>
002: #define vec vector
003: using namespace std;
004:
005: struct CellRemoval {
006: int cnt(vec<int> &p, int d, int a) {
007: if (a == d) return 0;
008: int s = 0, f = 0;
009: for (int i = 0; i < p.size(); i++)
010: if (p[i] == a) f = 1, s += cnt(p, d, i);
011: return f ? s : 1;
012: }
013: int cellsLeft(vec<int> p, int d) { return cnt(p, d, -1); }
014: };
002: #define vec vector
003: using namespace std;
004:
005: struct CellRemoval {
006: int cnt(vec<int> &p, int d, int a) {
007: if (a == d) return 0;
008: int s = 0, f = 0;
009: for (int i = 0; i < p.size(); i++)
010: if (p[i] == a) f = 1, s += cnt(p, d, i);
011: return f ? s : 1;
012: }
013: int cellsLeft(vec<int> p, int d) { return cnt(p, d, -1); }
014: };
TopCoder SRM 435, DIV I, 500, DNA Deletion
Overview
テキストが与えられ，パターン(key=>val)が与えられる．テキストから文字を好きなだけ除去してパターン(key)の組み合わせを作った時のパターン(val)の組み合わせ数．テキスト(ACGTACT)にパターン(ACT => gua)を与えると，"gua"または"gua gua"ができるので2種類という感じ．
Comment
DPであることはすぐわかるけどどうするんだと悩んだ．まぁ近い所を取れば良いというのも割と定石なのでその方向で．
Solution
あるアミノ酸がa〜b文字目，a〜c文字目(b<c)で作ることができるならばa〜cは考えなくて良いことがわかる（なぜならばb〜で作れるものはc〜で作れるものを含むから）．なので，任意のa,bについてa文字目以降で作れるアミノ酸とその最短距離のリストを持てば，動的計画法(DP)で解くことができる．
001: #include <vector>
002: #include <string>
003: #include <map>
004: #include <algorithm>
005: #include <cstdio>
006: #define vec vector
007: #define str string
008: #define MOD 1000000007
009: #define each(i,a) (__typeof((a).end())it=(a).begin();it!=(a).end();++it)
010: using namespace std;
011:
012: #define dn(a) ((a) >> 1 & 0x7L)
013:
014: struct DNADeletion {
015: int differentProteins(vec<str> vd, vec<str> c) {
016: // 文字列の結合
017: str d = ""; for (int i = 0; i < vd.size(); i++) d += vd[i];
018: // next表の作成
019: vec<int> nn(4, -2); vec< vec<int> > n((int)d.size() + 1, nn);
020: for (int i = d.size() - 1; 0 <= i; i--) nn[dn(d[i])] = i, n[i] = nn;
021: // GoTo表の作成
022: vec< map<str, int> > m(d.size() + 1);
023: // コドンに対して処理をする
024: for (int i = 0; i < c.size(); i++) {
025: // コドンの形とアミノ酸の名称に分ける
026: str key = c[i].substr(0, 3), val = c[i].substr(4);
027: for (int j = 0; j < d.size(); j++) {
028: int p = j;
029: // j文字目以降を用いてアミノ酸を最短で生成するとp文字目になる
030: for (int k = 0; 0 <= p && k < 3; k++) p = n[p][dn(key[k])] + 1;
031: // アミノ酸が生成できれば最短路を設定
032: if (0 <= p) {
033: if (m[j].find(val) == m[j].end()) m[j][val] = p;
034: else m[j][val] = min(m[j][val], p);
035: }
036: }
037: }
038: // 動的計画法
039: vec<long long int> q(d.size() + 1, 0); q[0] = 1;
040: long long int sum = 0;
041: for (int i = 0; i < d.size() + 1; i++) {
042: if (i) sum = (sum + q[i]) % MOD;
043: for each(it, m[i]) q[it->second] = (q[it->second] + q[i]) % MOD;
044: }
045: return sum;
046: }
047: };
002: #include <string>
003: #include <map>
004: #include <algorithm>
005: #include <cstdio>
006: #define vec vector
007: #define str string
008: #define MOD 1000000007
009: #define each(i,a) (__typeof((a).end())it=(a).begin();it!=(a).end();++it)
010: using namespace std;
011:
012: #define dn(a) ((a) >> 1 & 0x7L)
013:
014: struct DNADeletion {
015: int differentProteins(vec<str> vd, vec<str> c) {
016: // 文字列の結合
017: str d = ""; for (int i = 0; i < vd.size(); i++) d += vd[i];
018: // next表の作成
019: vec<int> nn(4, -2); vec< vec<int> > n((int)d.size() + 1, nn);
020: for (int i = d.size() - 1; 0 <= i; i--) nn[dn(d[i])] = i, n[i] = nn;
021: // GoTo表の作成
022: vec< map<str, int> > m(d.size() + 1);
023: // コドンに対して処理をする
024: for (int i = 0; i < c.size(); i++) {
025: // コドンの形とアミノ酸の名称に分ける
026: str key = c[i].substr(0, 3), val = c[i].substr(4);
027: for (int j = 0; j < d.size(); j++) {
028: int p = j;
029: // j文字目以降を用いてアミノ酸を最短で生成するとp文字目になる
030: for (int k = 0; 0 <= p && k < 3; k++) p = n[p][dn(key[k])] + 1;
031: // アミノ酸が生成できれば最短路を設定
032: if (0 <= p) {
033: if (m[j].find(val) == m[j].end()) m[j][val] = p;
034: else m[j][val] = min(m[j][val], p);
035: }
036: }
037: }
038: // 動的計画法
039: vec<long long int> q(d.size() + 1, 0); q[0] = 1;
040: long long int sum = 0;
041: for (int i = 0; i < d.size() + 1; i++) {
042: if (i) sum = (sum + q[i]) % MOD;
043: for each(it, m[i]) q[it->second] = (q[it->second] + q[i]) % MOD;
044: }
045: return sum;
046: }
047: };
SRM 435関連リンク
公式サイト
個人ブログ
- SRM435 DIV1 - TopCoder煮ブログ - TopCoder部
- 2009-02-13 - naoya_t@topcoder - TopCoder部
- 2009-02-13 - なんとなくな日々のコメント
- SRM435 Div1 - cafelier@SRM - TopCoder部
- SRM435 Div2 - ゆる系エンジニアのTopCoder日記 - TopCoder部
- Single Round Match 435 @ TopCoder - nodchipの日記 - TopCoder部
- SRM435 - Unknown Unit
- 2009-02-14 - てきとーな日記
- 恐怖の金曜日 - tetsumaの日記
- Newer: TopCoder Open Qualification Round 1
- Older: GoogleカレンダーとiCalの同期方法
Comments:0
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2009/02/topcoder-srm-435/trackback/
- Listed below are links to weblogs that reference
- TopCoder SRM 435 from 超現実いもす(imos)の日記