- 2008-11-26 (水) 18:59
- TopCoder
Rating: 1915 → 1895
またもや落ちてしまいました．残念．600は事後に書いたコードがシンプルになりました．うーむ，これを時間中に作れればなぁ．
TopCoder SRM 427, DIV I, 250, DesignCalendar
Overview
1日の長さと1年の長さが与えられるので何年で周期がもとに戻るのかという問題．
Comment
問題文が読めないよ！とかいいつつa/gcd(a,b)っぽいなーと思って提出したら大丈夫だったというお話．
001: struct DesignCalendar {
002: int shortestPeriod(int d, int y) {
003: return d / gcd(d, y);
004: }
005: };
002: int shortestPeriod(int d, int y) {
003: return d / gcd(d, y);
004: }
005: };
TopCoder SRM 427, DIV I, 600, LocateTreasure
Overview
dig(x)=dig(xの各桁の総和)という関数が与えられ，Σ(k=0..K)(-(-i)^k)*dig(m^k)を求めるという問題(iは虚数のiでKとmは与えられる)．
Comment
そういやdigって再帰して1〜9になるんだね，なんか一段階しか考えてなくて忘れてたわ．それもdig(x)=x%9とかどんなオチだよっていう．とりあえず事後に通したものを貼っておきます．一種の等比数列を求める感じなんだけど最初の方が違うのと，あとdigの部分の繰り返し周期がφ(9)=6になるのでその辺をつらつらと．
001: #include <string>
002: #include <complex>
003: #include <sstream>
004: #define rep(i,a) for(int i=0;i<(a);i++)
005: using namespace std;
006:
007: int powmod(int x, int k, int m) {
008: if (!k) return 1;
009: if (k % 2) return x * powmod(x, k - 1, m) % m;
010: return powmod(x * x % m, k / 2, m);
011: }
012:
013: typedef complex<int> pt;
014: pt dir[4];
015:
016: pt f(int x, int m) {
017: return dir[x % 4] * ((powmod(m, x, 9) + 8) % 9 + 1);
018: }
019:
020: struct LocateTreasure {
021: string location(int K, int m) {
022: pt p(0, 0);
023: rep(i, 4) dir[i] = i ? dir[i - 1] * pt(0, -1): pt(0, 1);
024: if (K < 6) for (int i = 0; i < K; i++) p += f(i, m);
025: else {
026: rep(i, 6) p += f(i + 6, m) - f(K - i + 5, m); p /= 2;
027: rep(i, 6) p += f(i, m);
028: }
029: ostringstream os; os << p.real() << " " << p.imag();
030: return os.str();
031: }
032: };
002: #include <complex>
003: #include <sstream>
004: #define rep(i,a) for(int i=0;i<(a);i++)
005: using namespace std;
006:
007: int powmod(int x, int k, int m) {
008: if (!k) return 1;
009: if (k % 2) return x * powmod(x, k - 1, m) % m;
010: return powmod(x * x % m, k / 2, m);
011: }
012:
013: typedef complex<int> pt;
014: pt dir[4];
015:
016: pt f(int x, int m) {
017: return dir[x % 4] * ((powmod(m, x, 9) + 8) % 9 + 1);
018: }
019:
020: struct LocateTreasure {
021: string location(int K, int m) {
022: pt p(0, 0);
023: rep(i, 4) dir[i] = i ? dir[i - 1] * pt(0, -1): pt(0, 1);
024: if (K < 6) for (int i = 0; i < K; i++) p += f(i, m);
025: else {
026: rep(i, 6) p += f(i + 6, m) - f(K - i + 5, m); p /= 2;
027: rep(i, 6) p += f(i, m);
028: }
029: ostringstream os; os << p.real() << " " << p.imag();
030: return os.str();
031: }
032: };
他のSRM 427に関するページ
- Newer: The 1st Imos Contest 告知
- Older: ツールバー作成奮闘記 第二話
Comments:0
Trackbacks:0
- Trackback URL for this entry
- http://imoz.jp/2008/11/topcoder-srm-427/trackback/
- Listed below are links to weblogs that reference
- TopCoder SRM 427 from 超現実いもす(imos)の日記