読者です 読者をやめる 読者になる 読者になる

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. 読んでない