Codeforces Round #166 (Div. 2)
こどふぉってこんな人数多かったっけ・・・
○○○×- 203位 (アカン)
a. 実装
int y; bool check(int c){ bool f = true; set<int> u; while(c > 0){ int d = c % 10; if(u.find(d) != u.end()) return false; u.insert(d); c /= 10; } return true; } int main(){ cin >> y; while(true){ y++; if(check(y)){ cout << y << endl; return 0; } } return 0; }
b. 篩する
int n, m, ans = INT_MAX; int mat[510][510], ne[510][510]; vector<int> prime; bool pr[200010]; int col[510], row[510]; void sieve(){ pr[0] = pr[1] = true; for(int i = 2; i < 200010; ++i){ if(!pr[i]){ prime.pb(i); for(int j = i * 2; j < 200010; j += i){ pr[j] = true; } } } } int main(){ cin >> n >> m; rep(i, n){ rep(j, m){ cin >> mat[i][j]; } } sieve(); rep(i, n){ rep(j, m){ ne[i][j] = *lower_bound(prime.begin(), prime.end(), mat[i][j]) - mat[i][j]; col[i] += ne[i][j]; row[j] += ne[i][j]; } } rep(i, n) ans = min(ans, col[i]); rep(i, m) ans = min(ans, row[i]); cout << ans << endl; return 0; }
c. 適当なgreedy. ランダムジャップルとかこわい
int n, k, now; int ans[1000010]; int main(){ cin >> n >> k; if(k * 3 > n){ printf("-1\n"); return 0; } rep(i, k){ ans[++now] = i; ans[++now] = i; } rep(i, k) ans[++now] = i; for(int i = 1; i <= n; i++) printf("%d%c", ans[i] + 1, i == n ? '\n' : ' '); return 0; }
D. ローリングハッシュらしい。そうかなと思ったけど書いたこと無くてかけない。
int k; string s, za; bool ok[30]; ll ans; int rui[2010]; set<string> e; vector<ll> roll[1510]; const ll mul = 100000007LL; int main(){ cin >> s; cin >> za; cin >> k; rep(i, 26) ok[i] = (za[i] == '1'); rep(i, s.size()) rui[i + 1] = rui[i] + (!ok[s[i] - 'a']); rep(i, s.size()){ string tmp = ""; ll hash = 0; for(int j = i; j < s.size(); ++j){ if(rui[j + 1] - rui[i] > k) break; hash = hash * mul + (ll)s[j]; roll[j - i + 1].pb(hash); } } rep(i, 1510){ sort(roll[i].begin(), roll[i].end()); roll[i].erase(unique(roll[i].begin(), roll[i].end()), roll[i].end()); ans += roll[i].size(); } cout << ans << endl; return 0; }
E. 読んでない