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しかない場合の処理でつまづいた。

typedef long long ll;
typedef pair<ll,int> P;

struct Point {
  int x, y, id;
  Point(){}
  Point(int a, int b, int c) : x(a), y(b), id(c) {}
};

struct Edge {
  int to, cost;
  Edge(int a, int b) : to(a), cost(b) {}
};

int w, h, max_num;
vector<Point> V[2500];
vector<Edge> es[2500];
Point s, g;

const int inf = 1<<28;
ll dp[2500];

int dijkstra(int s, int g) {
  priority_queue<P,vector<P>,greater<P> > q;
  fill(dp, dp + 2500, inf);
  dp[s] = 0;
  q.push(P(0, s));
  
  while (!q.empty()) {
    P p = q.top(); q.pop();
    int v = p.second, i;
    if (dp[v] < p.first) continue;
    //cout << v << "|" << dp[v] << endl;
    rep (i,es[v].size()) {
      Edge te = es[v][i];
      if (dp[te.to] > dp[v] + te.cost) {
        dp[te.to] = dp[v] + te.cost;
        q.push(P(dp[te.to], te.to));
      }
    }
  }
  
  return dp[g];
}

void solve() {
  int i, j, k, id = 1;
  int s_id = 0, g_id;
  max_num = 0;
  string in;
  
  rep (i,h) rep (j,w) {
    cin >> in;
    if (in == ".") continue;
    if (in == "S") {
      s.x = j, s.y = i; continue;
    }
    if (in == "G") {
      g.x = j, g.y = i; continue;
    }
    int num = atoi(in.c_str());
    max_num = max(max_num, num);
    V[num].push_back(Point(j,i,id));
    id++;
  }
  if (max_num != 0) {
    g_id = id;
    // id of S is 0, id of G is @id.
    // connect S & 1
    rep (i,V[1].size()) {
      int dist = abs(s.x - V[1][i].x) + abs(s.y - V[1][i].y);
      es[0].push_back(Edge(V[1][i].id, dist));
    }
    // connect
    for (i = 1; i < max_num; i++) {
      rep (j,V[i].size()) rep (k,V[i+1].size()) {
        int dist = abs(V[i][j].x - V[i+1][k].x) + abs(V[i][j].y - V[i+1][k].y);
        int a_id = V[i][j].id, b_id = V[i+1][k].id;
        es[a_id].push_back(Edge(b_id, dist));
      }
    }
    // connect max_num & G
    rep (i,V[max_num].size()) {
      int dist = abs(g.x - V[max_num][i].x) + abs(g.y - V[max_num][i].y);
      int t_id = V[max_num][i].id;
      es[t_id].push_back(Edge(g_id, dist));
    }
  } else {
    cout << abs(s.x - g.x) + abs(s.y - g.y) << endl;
    return;
  }
    
  
  // dijkstra
  cout << dijkstra(s_id, g_id) << endl;
  
  // clear
  rep (i,max_num+1) V[i].clear();
  rep (i,g_id+1) es[i].clear();
}

int main() {
  while (cin >> w >> h, w|h) {
    solve();
  }
  return 0;
}

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;
}