Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-07-10

[][] Codeforces Beta Round 77 (Div. 2) 15:49 はてなブックマーク -  Codeforces Beta Round 77 (Div. 2) - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #77 (Div. 2 Only) - Codeforces

結果:Standings - Codeforces Beta Round #77 (Div. 2 Only) - Codeforces

=.ABCDE
--0:091:400:411:23-
1032+0/-0482/0550/-10/-10/-1-

部屋内16位(Room 11),全体390位

Rating:1510 → 1478 (-32)

 C, D解けたと思ったのですが残念です.しかもBを解くのを後回しにした為に余計順位が下がってしまいました.

A. Football

 問題文:http://www.codeforces.com/contest/96/problem/A

提出コード(c++)
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main(){
  string s;
  while(cin >> s){
    cin >> s;
    int cnt = 1;
    for(int i = 1; i < s.size();i++){
      if(s[i-1] != s[i]){
	cnt = 1;
      }else{
	cnt++;
      }
      if(cnt == 7){
	cout << "YES" << endl;
	goto next;
      }
    }
    cout << "NO" <<endl;
  next:;
  }  
}

B. Lucky Numbers (easy)

 問題文:http://www.codeforces.com/contest/96/problem/B

提出コード(c++)
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;

ll to_i(vector<int>& v){
  ll ret = 0;
  for(int i = 0;i < v.size();i++){
    ret *= 10;
    ret += v[i];
  }
  return ret;
}

ll inf = 1;

int main(){
  ll n;
  while(cin >> n){
    int m = n;
    vector<int> digits;
    while(m > 0){
      digits.push_back(m%10);
      m = m/10;
    }
    int len = digits.size();
    if(len%2 == 1){
      len++;
    }
    
    vector<int>shuffle(len);
    for(int i = 0;i < len/2;i++){
      shuffle[i] = 4;
    }
    for(int i = len/2;i < len;i++){
      shuffle[i] = 7;
    }

    inf = 1;
    for(int i = 0;i < 10;i++){
      inf *= 10;
    }
    ll ans = inf;

    do{
      ll buf = to_i(shuffle);
      if(buf < ans && buf >= n){
	ans = buf;
      }
    }while(next_permutation(shuffle.begin(), shuffle.end()));
      
    if(ans == inf){
      for(int i = 0;i < len/2 + 1;i++){
	cout << 4;
      }
      for(int i = len/2+1;i < len+ 2;i++){
	cout << 7;
      }
      cout <<endl;
    }else{
      cout << ans <<endl;
    }
  }
}

C. Hockey

 問題文:http://www.codeforces.com/contest/96/problem/C

修正済コード(c++)
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main(){
  int n;
  while(cin >> n){
    vector<string> cforbidden(n);
    vector<string> forbidden(n);
    for(int i = 0;i < n;i++){
      cin >> cforbidden[i];
      forbidden[i]= cforbidden[i];
    }

    for(int i = 0;i < n;i++){
      for(int j = 0;j < cforbidden[i].size();j++){
	if(forbidden[i][j] >= 'A' && forbidden[i][j] <= 'Z'){
	  forbidden[i][j] = forbidden[i][j] - 'A' + 'a';
	}
      }
    }

    string s; cin >> s;
    char l;cin >> l;

    string toLower = s;
    for(int i = 0;i < s.size();i++){
      if(s[i] >= 'A' && s[i] <= 'Z'){
	toLower[i] = toLower[i] - 'A' + 'a';
      }
    }
    vector<int> ismarked(s.size());

    for(int i = 0;i < n;i++){
      for(int j = 0;j < toLower.size();j++){
	if(toLower.find(forbidden[i], j) == j){
	  for(int k = 0;k < forbidden[i].size();k++){
	    ismarked[j+k] = 1;
	  }
	}
      }
    }

    for(int i = 0;i < s.size();i++){
      if(ismarked[i] == 1){
	if(s[i] == l){
	  if(s[i] == 'a'){
	    s[i] = 'b';
	  }else if(s[i] >= 'b' && s[i] <= 'z'){
	    s[i] = 'a';
	  }
	}else if(s[i] == l - 'a'+ 'A'){
	  if(s[i] == 'A'){
	    s[i] = 'B';
	  }else if(s[i] >= 'B' && s[i] <= 'Z'){
	    s[i] = 'A';
	  }
	}else{
	  if(s[i] >= 'A' && s[i] <= 'Z'){
	    s[i] = l - 'a'+ 'A';
	  }else{
	    s[i] = l;
	  }
	}
      }
    }
    cout << s <<endl;
  }
}

最後の書き換えの部分で,次のように条件分岐を間違えたために誤答となりました.

    for(int i = 0;i < s.size();i++){
      if(ismarked[i] == 1){
	if(s[i] == l){
	  if(s[i] == 'a'){
	    s[i] = 'b';
	  }else if(s[i] >= 'b' && s[i] <= 'z'){
	    s[i] = 'a';
	  }else if(s[i] == 'A'){
	    s[i] = 'B';
	  }else{
	    s[i] = 'A';
	  }
	}else{
	  if(s[i] >= 'A' && s[i] <= 'Z'){
	    s[i] = l - 'a'+ 'A';
	  }else{
	    s[i] = l;
	  }
	}
      }
    }

D. Volleyball

 問題文:http://www.codeforces.com/contest/96/problem/D

提出コード(c++)

 n=1000でワーシャルフロイドを用いて,TLEにならない事を願ったのですが,だめでした.Dの修正が何回か後のエントリになる予定です.

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long ll;

int x, y;
vector<int> t;
vector<int> c;

ll table[1111][1111];

int main(){
  int n, m;
  
  while(cin >> n >> m){
    int x, y;cin >> x >> y;
    x --;y--;

    for(int i = 0;i < m;i++){
      int u, v, w;cin >> u >> v >> w;
      u --;v--;
      table[u][v]
      table[u][v] = w;
      table[v][u] = w;
    }

    for(int k = 0;k < n;k++){
      for(int i = 0;i < n;i++){
	for(int j = 0;j < n;j++){
	  if(table[i][k] == -1 || table[k][j] == -1){
	    continue;
	  }
	  if(table[i][j] == -1){
	    table[i][j] = table[i][k] + table[k][j];
	  }else{
	    table[i][j] = min(table[i][j], table[i][k] + table[k][j]);
	  }
	}
      }
    }

    t.clear();t.resize(n);
    c.clear();c.resize(n);
    for(int i = 0;i < n;i++){
      cin >> t[i] >> c[i];
    }

    vector<int> used(n);
    vector<ll> cost(n, -1);
    cost[x] = 0;

    queue<int> q;
    q.push(x);
    while(!q.empty()){
      int now = q.front();
      used[now] = 1;
      q.pop();
      for(int i = 0;i < n;i++){
	if(table[i][now] != -1 && t[now] >= table[i][now] && (cost[i] == -1 || cost[i] >= cost[now] + c[now]) ) {
	  cost[i] = cost[now] + c[now];
	}
      }

      for(int i = 0;i < n;i++){
	if(table[i][now] != -1 && t[now] >= table[i][now] && used[i] != 1 ){
	  q.push(i);
	}
      }
    }
    cout << cost[y] <<endl;
  }
}