Hatena::Grouptopcoder

blu_rayの日記

2011-11-05

Codeforces Beta Round #92 Div2

| 00:22

ooo--

A. The number of positions / Accepted / 474

O(1)で出来ると思ったけど、N=100なのでO(N)で。

こういう0と1でうわーってなる問題が苦手…。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int n, a, b;

int main() {
  while (cin >> n >> a >> b) {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (i < a) continue;
      int behind = n - 1 - i;
      if (behind <= b) ans++;
    }
    cout << ans << endl;
  }
  return 0;
}

B. Permutations / Accepted / 852

英語が意味不明。Noteのrearrangeで(3,1,2,4)に並び替えを見るまで意味不明だった。

next_permuitation問題。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int n, k;

int main() {
  while (cin >> n >> k) {
    int ans = 1 << 30;
    string in[8], to[8];
    rep (i,n) cin >> in[i];
    int l[8] = { 0, 1, 2, 3, 4, 5, 6, 7 };
    
    do {
      rep (i,n) to[i] = "         ";
      rep (i,n) rep (j,k) {
        to[i][j] = in[i][ l[j] ];
      }
      int _min = 1 << 30, _max = -1;
      rep (i,n) {
        int _sum = atoi(to[i].c_str());
        _min = min(_min, _sum);
        _max = max(_max, _sum);
      }
      ans = min(ans, _max - _min);
    } while (next_permutation(l, l + k));
    cout << ans << endl;
  }
  return 0;
}

C. Prime Permutation / Accepted / 1328

|S|以下の任意の素数pに対して、Sp = Sp x iが成立するのは、

p*2 > |S|となるpについては、Sp = Sp x 1のみ考えればよいので何にも考えない。

p*2 <= |S|となるpについては、複数回Sの中に出現するため、同じ文字が必要になる。

複数回出現する際に、必ず2*pの位置で出現するため、p=2の場合の文字と同じ文字じゃないといけない。

なので、複数回出現する場合は、結局すべて同じ文字じゃないといけない。

あとは、どのくらい同じ文字が必要か考えて判定するだけ。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

string in;
const int MAX_N = 1002;
bool sieve[MAX_N];
vector<int> primes(1,2);

int main() {
  fill(sieve, sieve + MAX_N, true);
  for (int i = 4; i < MAX_N; i+=2) sieve[i] = false;
  for (int i = 3; i < MAX_N; i+=2) if (sieve[i]) {
    primes.push_back(i);
    for (int j = i + i; j < MAX_N; j+=i) sieve[j] = false;
  }
  while (cin >> in) {
    int sz = in.size();
    bool check[MAX_N];

    fill(check, check + MAX_N, false);
    rep (i,primes.size()) {
      if (primes[i] > sz/2) break;
      for (int j = primes[i]; j < MAX_N; j+=primes[i]) check[j] = true;
    }

    int cnt = 0;
    for (int i = 1; i <= sz; ++i) if (check[i]) cnt++;

    map<char,int> m;
    rep (i,sz) {
      if (m.count(in[i])) m[ in[i] ]++;
      else m.insert(make_pair(in[i], 1));
    }
    
    int maxs = 0;
    char ch = 0;
    foreach (m,i) {
      if (maxs < i->second) {
        maxs = i->second;
        ch = i->first;
      }
    }
    
    if (maxs < cnt) { cout << "NO" << endl; continue; }
        
    queue<char> q;
    rep (i,sz) if (in[i] != ch) {
      q.push(in[i]);
    }
    
    cout << "YES" << endl;
    string res(in);
    for (int i = 1; i <= sz; ++i) {
      char c;
      if (check[i]) {
        c = ch;
      } else {
        if (!q.empty()) {
          c = q.front(); q.pop();
        } else {
          c = ch;
        }
      }
      res[i-1] = c;
    }
    cout << res << endl;
  }
  return 0;
}

D. Squares

問題は読めました。

他の人のを参考にする。

rate := 1585(+140)

あお!