国内予選のぷろぐらむ

ICPC

貼ってみたりする．Eはもはや説明不要（能）．

  • A

これは素直に．

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define MAX 1000000

using namespace std;

vector<bool> prime(MAX + 1, true);
int a, d, n;

void sieve() {
  int i, j, limit;
  fill(prime.begin(), prime.end(), true);
  limit = (int)sqrt((double)(MAX));

  prime[1] = false;

  for(int i = 4;  i  <= MAX ; i+=2) {
    prime[i] = false;
  }

  for(int i = 3 ; i <= limit ; i += 2) {
    if(prime[i]) {
      for(int j = i ; i * j <= MAX ; j+=2) {
        prime[i * j] = false;
      }
    }
  }
}

int main() {
  sieve();

  while(cin >> a >> d >> n, a || d || n) {
    int counter = 0;

    for(int i = a ; true ; i += d) {
      if(prime[i]) {
        counter++;

        if(counter == n) {
          cout << i << endl;
          break;
        }
      }
    }
  }
}
  • B

C-kとC-yで．これはもっと綺麗に書けると思うけど，まあオレはこんなもんです．

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>

using namespace std;

int tc, counter;
string in;
vector< vector<char> > tbl;

void func(vector<char> &a, vector<char> &b) {
  vector<char> k;

  // normal
  for(int i = 0 ; i < a.size() ; i++) k.push_back(a[i]);
  for(int i = 0 ; i < b.size() ; i++) k.push_back(b[i]);
  if(find(tbl.begin(), tbl.end(), k) == tbl.end()) {
    counter++;
    tbl.push_back(k);
  }

  // a reverse
  k.clear();
  reverse(a.begin(), a.end());
  for(int i = 0 ; i < a.size() ; i++) k.push_back(a[i]);
  for(int i = 0 ; i < b.size() ; i++) k.push_back(b[i]);
  if(find(tbl.begin(), tbl.end(), k) == tbl.end()) {
    counter++;
    tbl.push_back(k);
  }

  // ab reverse
  k.clear();
  reverse(b.begin(), b.end());
  for(int i = 0 ; i < a.size() ; i++) k.push_back(a[i]);
  for(int i = 0 ; i < b.size() ; i++) k.push_back(b[i]);
  if(find(tbl.begin(), tbl.end(), k) == tbl.end()) {
    counter++;
    tbl.push_back(k);
  }

  // b reverse
  k.clear();
  reverse(a.begin(), a.end());
  for(int i = 0 ; i < a.size() ; i++) k.push_back(a[i]);
  for(int i = 0 ; i < b.size() ; i++) k.push_back(b[i]);
  if(find(tbl.begin(), tbl.end(), k) == tbl.end()) {
    counter++;
    tbl.push_back(k);
  }
}

void solve() {
  counter = 0;
  tbl.clear();

  for(int k = 1 ; k < in.size() ; k++) {
    vector<char> a, b;

    for(int i = 0 ; i < k ; i++) a.push_back(in[i]);
    for(int i = k ; i < in.size() ; i++) b.push_back(in[i]);

    func(a, b);
    func(b, a);
  }

  cout << counter << endl;
}

int main() {
  cin >> tc;

  while(tc--) {
    cin >> in;

    if(in.size() == 1) {
      cout << 1 << endl;
    } else {
      solve();
    }
  }
}
  • D

バックトラック．氷で滑ったりブロック消したりがちょっと複雑かな？

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define MAX 20

using namespace std;

int w, h;
int tbl[MAX][MAX];
int p, q, a, b;
int move[] = {-1,0,1,0,0,-1,0,1};
int result;

void solve(int index, int aa, int bb) {
  if(index == 11) {
    return;
  }

  for(int i = 0 ; i < 4 ; i++) {
    int ii = aa, jj = bb;

    if(tbl[ii + move[i * 2]][jj + move[i * 2 + 1]] == 1) continue;

    while(true) {
      if(ii < 0 || ii >= h  || jj < 0 || jj >= w) {
        break;
      } else if(tbl[ii][jj] == 3) {
        result = min(result, index);
        break;
      } else if(tbl[ii][jj] == 1) {
        tbl[ii][jj] = 0;

        ii -= move[i * 2];
        jj -= move[i * 2 + 1];
        
        solve(index + 1, ii, jj);

        tbl[ii + move[i * 2]][jj + move[i * 2 + 1]] = 1;

        break;
      }

      ii = ii + move[i * 2];
      jj = jj + move[i * 2 + 1];
    }

  }
}

int main() {
  while(cin >> w >> h, w || h) {
    for(int i = 0 ; i < h ; i++) {
      for(int j = 0 ; j < w ; j++) {
        cin >> tbl[i][j];

        if(tbl[i][j] == 2) {
          p = i;
          q = j;
        } else if(tbl[i][j] == 3) {
          a = i;
          b = j;
        }
      }
    }

    solve(1, p, q);

    if(result == 20) cout << -1 << endl;
    else cout << result << endl;
  }
}
  • E

出ました．何だこれは・・・．一晩経って見てみると，自分でもよく分からないコードになっちょる．

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <cctype>

#define MAX 1000000

using namespace std;

int n, ii;
int ss;

vector<char> solve(string &in, int p, bool flag) {
  vector<char> r;
  
  while(ii < in.size() - 1 && (flag || (p && flag == false))) {
    int a = 0;
    
    if(isdigit(in[ii])) {
      while(isdigit(in[ii++])) {
        a *= 10;
        a += (in[ii - 1] - '0');
      }
      
      ii--;
      
      if(in[ii] == '(') {
        ii++;
        vector<char> tmp = solve(in, 1, false);
        
        ii++;

        for(int i = 0 ; i < a ; i++) {
          for(int j = 0 ; j < tmp.size() ; j++) {
            r.push_back(tmp[j]);

            if(r.size() >= n + 100) return r;
          }
        }

      } else {
        for(int i = 0 ; i < a ; i++) r.push_back(in[ii]);

        ii++;
      }
    } else {
      while(ii < in.size() && in[ii] != ')' && !isdigit(in[ii])) r.push_back(in[ii++]);
      
      if(in[ii] == ')') p--;

      if(isdigit(in[ii])) {
        vector<char> tmp = solve(in, 0, false);

        for(int i = 0 ; i < a ; i++) {
          for(int j = 0 ; j < tmp.size() ; j++) {
            r.push_back(tmp[j]);
            ss++;

            if(r.size() >= n + 100) return r;
          }
        }
      }

      if(p == 0 && flag == false) return r;
    }
    
    if(in[ii] == ')') p--;
  }

  return r;
}

int main() {
  string in;
 
  while(cin >> in >> n, in != "0" || n) {
    ii = 0;
    ss = 0;
    in.push_back(')');
    vector<char> rr = solve(in, 1, true);

    if(ss < n + 100 && n >= rr.size()) cout << 0 << endl;
    else cout << rr[n] << endl;
  }
}