SRM 729 div1 easy MagicNumberThree - 久々の競技プログラミング
久々にTopcoderに参加しようと直近の問題を練習がてら解いてみました。 まずはeasyから。 ちなみにGreedというプラグインをいれてみましたがかなり使いやすくておすすめです。
さて問題は、"303049"みたいな文字列が渡されるので、3で割れる部分文字列の数を数えるというものでした。 何文字目まで使ったとき、1余る、2余る、3で割れる文字列がいくつあるかを保持するという感じで、動的計画法で解きました。
class MagicNumberThree { public: int countSubsequences(string s) { int a[55][4]; for (int i = 0; i < 55; i++) for (int j = 0; j < 4; j++) a[i][j] = 0; long long res = 0; for (int i = 0; i < s.length(); i++) { int si = s[i] - '0'; if (si % 3 == 0) { a[i + 1][0] = a[i][0] + a[i][0] + 1; a[i + 1][1] = a[i][1] + a[i][1]; a[i + 1][2] = a[i][2] + a[i][2]; } else if (si % 3 == 1) { a[i + 1][0] = a[i][2] + a[i][0]; a[i + 1][1] = a[i][0] + a[i][1] + 1; a[i + 1][2] = a[i][1] + a[i][2]; } else { a[i + 1][0] = a[i][1] + a[i][0]; a[i + 1][1] = a[i][2] + a[i][1]; a[i + 1][2] = a[i][0] + a[i][2] + 1; } a[i + 1][0] %= 1000000007; a[i + 1][1] %= 1000000007; a[i + 1][2] %= 1000000007; res = a[i + 1][0]; res %= 1000000007; } return res; } };