Hatena::Grouptopcoder

blu_rayの日記

2011-10-19

RUPC2011

| 02:40

当日バイトで参加しなかったのでまったり解いた。

A. Swap Cipher

かなりあほっぽいけど計算量は大丈夫。

int n, a[102], b[102];

int main() {
  int i, j;
  while (cin >> n, n) {
    string in;
    cin >> in;
    rep (i,n) cin >> a[i] >> b[i];
    rep (i,n) {
      a[i]--; b[i]--;
    }
    
    for (i = n - 1; i >= 0; i--) {
      int ai = a[i], bi = b[i];
      int d = abs(ai - bi);
      for (j = 0; j < d; j++) {
        in[ai]++;
        in[bi]++;
        if (in[ai] > 'z') in[ai] = 'a';
        if (in[bi] > 'z') in[bi] = 'a';
      }
      swap(in[ai], in[bi]);
    }
    
    cout << in << endl;
  }
  return 0;
}

B. Problem B

作業時間が難易度の整数倍になるけど、難易度がmより大きい場合は

作業時間の申請を0としたら通った。0倍も整数倍なんですね。。

int n, m, a[1002];

int main() {
  int i;
  while (cin >> n >> m, n|m) {
    rep (i,n) cin >> a[i];
    
    int cur_time = 0, cur = -1, cur_lv = 1002;
    bool multi = false;
    rep (i,n) {
      if (i == 0) {
        cur_time = m - (m % a[i]);
        cur = 0;
        cur_lv = a[i];
        continue;
      }
      int tmp_time = m - (m % a[i]);
      if (a[i] > m) tmp_time = 0;
      if (tmp_time > cur_time) continue;
      else if (tmp_time == cur_time) {
        if (cur_lv == a[i]) {
          multi = true;
          continue;
        }
        if (cur_lv < a[i]) continue;
        if (cur_lv > a[i]) {
          cur_lv = a[i];
          cur = i;
          continue;
        }
        multi = true; continue;
      }
      else if (tmp_time < cur_time) {
        multi = false;
        cur_time = tmp_time;
        cur = i;
        cur_lv = a[i];
      }
    }
    cout << ((multi) ? n : cur+1) << endl;
  }
  return 0;
}

C. Seishun 18 Kippu

sirokurostoneが乗る駅から2D好きな人が乗る駅までの経路 の最短コストと

2D好きな人物が乗る駅からA津大学がある駅の場所まで の最短コストを出す

typedef pair<int,int> P;

int n, m, d, t;
vector<P> V[502];
const int inf = 1<<28;
int dp[502];

int dijkstra(int s, int g) {
  priority_queue<P,vector<P>,greater<P> > q;
  fill(dp, dp + n, inf);
  dp[s] = 0;
  q.push(P(0,s));
  
  while (!q.empty()) {
    P p = q.top(); q.pop();
    int v = p.second;
    if (dp[v] < p.first) continue;
    for (int i = 0; i < V[v].size(); i++) {
      P p2 = V[v][i];
      if (dp[p2.first] > dp[v] + p2.second) {
        dp[p2.first] = dp[v] + p2.second;
        q.push(P(dp[p2.first], p2.first));
      }
    }
  }
  
  return dp[g];
}

int main() {
  int i, j;
  while (cin >> n >> m, n|m) {
    rep (i,n) V[i].clear();
    
    map<string,int> hash;
    string spg[3], a[2];
    int station_count = 0;

    rep (i,3) cin >> spg[i];
    rep (i,3) {
      if (!hash.count(spg[i])) {
        hash.insert(make_pair(spg[i], station_count));
        station_count++;
      }
    }
        
    rep (i,m) {
      cin >> a[0] >> a[1] >> d >> t;
      rep (j,2) if (!hash.count(a[j])) {
        hash.insert(make_pair(a[j], station_count));
        station_count++;
      }
      int u = hash[a[0]], v = hash[a[1]];
      int cost = d / 40 + t;
      V[u].push_back(P(v, cost));
      V[v].push_back(P(u, cost));
    }
    
    int ans = dijkstra(hash[spg[0]], hash[spg[1]]) 
      + dijkstra(hash[spg[1]], hash[spg[2]]);
    cout << ans << endl;
  }
  return 0;
}

D. The Legendary Sword

魔王が伝説の剣を壊すというのは合理的で納得した。

適当に全探索+枝狩りで解けると思ったけどTLE余裕だったので

これもグラフにしてダイクストラで通った。SとGしかない場合の処理でつまづいた。

ement

F. Farey Sequence

dp出来ないけど、なんとなく一つ前の計算結果を使うことは分かったので

あとは適当にF0からF8くらいの場合まで紙に書いて、適当に法則を見つけて実装したら通った。

typedef long long ll;

const int MAX_N = 1000002;

ll dp[MAX_N], subs[MAX_N];

bool sieve[MAX_N];

int main() {
  int T, i, j, temp;

  fill(dp, dp + MAX_N, -1);
  fill(subs, subs + MAX_N, 0);
  fill(sieve, sieve + MAX_N, true);

  sieve[0] = sieve[1] = false;
  for (i = 4; i < MAX_N; i+=2) sieve[i] = false;
  for (i = 3; i < MAX_N; i+=2) if (sieve[i]) {
    for (j = i+i; j < MAX_N; j+=i) sieve[j] = false;
  }
  
  dp[1] = 2;
  for (i = 2; i < MAX_N; i++) {
    if (sieve[i]) {
      dp[i] = dp[i-1] + i-1;
      for (j = i+i; j < MAX_N; j+=i) subs[j] += i-1;
      continue;
    }
    int add = i-1 - subs[i];
    dp[i] = dp[i-1] + add;
    for (j = i+i; j < MAX_N; j+=i) subs[j] += add;
  }
  
  cin >> T;
  rep (i,T) {
    cin >> temp;
    cout << dp[temp] << endl;
  }
  return 0;
}