Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-08-20

[][] Codeforces Beta Round #82 (Div. 2 Only) 12:24 はてなブックマーク -  Codeforces Beta Round #82 (Div. 2 Only) - 練習帳

概要

 問題一覧:no title

 結果:no title

結果

問題ABCDE
提出時刻0:110:24-1:43-
得点/誤答回数478/0904/0-0/-1-
Hack成功/失敗+0/-0
総得点1382

部屋内13位(Room 24),全体302位

Rating:1588 → 1550 (-38)

A. Card Game

問題文

 問題文

分析

 下のコードでは,問題文の書かれている順に判定しているけれど,まず2枚のカードが同じスートかを判定する方が効率的でした.

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

using namespace std;

map<char, int> table;

int main(){
  table['6'] = 6;
  table['7'] = 7;
  table['8'] = 8;
  table['9'] = 9;
  table['T'] = 10;
  table['J'] = 11;
  table['Q'] = 12;
  table['K'] = 13;
  table['A'] = 14;

  string t;
  string f, s;
  while(cin >> t){
    cin >> f >> s;
    if(f[1] == t[0]){
      if(s[1]!= t[0]){
	cout<< "YES" <<endl; 
      }else{
	if(table[f[0]] > table[s[0]]){
	  cout << "YES" << endl;
	}else{
	  cout << "NO" << endl;
	}
      }
    }else{
      if(f[1] == s[1]){
	if(table[f[0]] > table[s[0]]){
	  cout<< "YES" << endl;
	}else{
	  cout<< "NO" << endl;
	}
      }else{
	cout<< "NO" <<endl;
      }
    }
  }
  
  return 0;
}

B. Choosing Laptop

問題文

 問題文

分析
提出コード(c++)
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <fstream>

using namespace std;

int s[111];
int r[111];
int h[111];
int c[111];

int main(){
  int n;
  while(cin >> n){
    for(int i = 0;i < n;i++){
      cin >> s[i] >>r[i] >> h[i] >> c[i];
    }

    vector<int> candidate;

    for(int i = 0;i < n;i++){
      bool isconsider = true;
      for(int j = 0;j < n;j++){
	if(i==j){
	  continue;
	}
	if(s[i] < s[j] && r[i] < r[j] && h[i] < h[j]){
	  isconsider = false;
	  break;
	}
      }
      if(isconsider){
	candidate.push_back(i);
      }
    }

    int ind = -1;
    int cost = 10000;

    for(size_t i = 0;i < candidate.size();i++){
      if(c[candidate[i]] < cost){
	cost = c[candidate[i]];
	ind = candidate[i];
      }
    }
    cout << ind+1 << endl;
  }
  return 0;
}

D. Treasure Island

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

分析

 スタートとなるsightから進めるかを1マスずつ確かめるとTLEを起こします.そこで,それぞれの地点から4方向に最大何歩まで進めるかを前計算しておきます.

提出コード(c++)

ですが,その前計算部分でTLEを起こして残念な結果に.TestCase 38でTLEを起こします.

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <cstring>

using namespace std;

vector<string> table;
vector<char> alph;
vector<int> sightx;
vector<int> sighty;

vector<vector<vector<int> > > step; //step[i] i= 0 :north, 1, south, 2, west, 3east;

string direction;
vector<int> dist;
int k;
int n, m;

bool check(int startx, int starty){
  int nowx = startx;
  int nowy = starty;
  int dx[4] = {-1, 1, 0, 0};
  int dy[4] = {0, 0, -1, 1};
  
  for(int i = 0; i < k; i++){
    int nextdir = -1;

    if(direction[i] == 'N'){
      nextdir = 0;
    }else if(direction[i] == 'S'){
      nextdir = 1;
    }else if(direction[i] == 'W'){
      nextdir = 2;
    }else if(direction[i] == 'E'){
      nextdir = 3;
    }

    if(!(nowx >= 0 && nowx < n && nowy >= 0 && nowy < m)){
	return false;
      }
    
    if(step[nextdir][nowx][nowy] < dist[i]){
      return false;
    }

    nowx += dist[i] * dx[nextdir];
    nowy += dist[i] * dy[nextdir];

    if(!(nowx >= 0 && nowx < n && nowy >= 0 && nowy < m)){
      return false;
    }

  }
  return true;
}

int main(){
  while(cin >> n >> m){
    table.resize(n);
    alph.clear();
    sightx.clear();
    sighty.clear();
    vector<vector<vector<int> > > buf(4, vector<vector<int> > (n, vector<int>(m, 0)));
 //step[i] i= 0 :north, 1, south, 2, west, 3east;
    swap(buf, step);

    for(int i = 0; i < n; i++){
      cin >> table[i];
    }
    for(int i = 0; i <n; i++){
      for(int j = 0; j < m; j++){
	if(table[i][j]- 'A'>= 0 && table[i][j] - 'Z' <= 0){
	  alph.push_back(table[i][j]);
	  sightx.push_back(i);
	  sighty.push_back(j);
	}
      }
    }

    cin >> k;
    direction.clear();
    dist.clear();dist.resize(k);

    for(int i = 0; i < k; i++){
      char dir;
      cin >> dir >> dist[i];		      
      direction += dir;
    }

    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
	int dx[4] = {-1, 1, 0, 0};
	int dy[4] = {0, 0, -1, 1};
	if(table[i][j] == '#'){
	  continue;
	}
	
	for(int dir = 0; dir < 4; dir++){
	  int count = 0;
	  int nextx = i+dx[dir];
	  int nexty = j+dy[dir];
	  while(nextx >= 0 && nextx < n && nexty >= 0 && nexty < m && table[nextx][nexty] != '#'){
	      nextx += dx[dir];
	      nexty += dy[dir];
	      count++;
	  }
	  step[dir][i][j] = count;
	}
      }
    }

    vector<char> ans;
    for(size_t i = 0; i< alph.size(); i++){      
      int x = sightx[i];
      int y = sighty[i];
	
      if(check(x, y)){
	ans.push_back(alph[i]);
      }
    }
    sort(ans.begin(), ans.end());

    if(ans.empty()){
      cout << "no solution" << endl;
    }else{
      for(size_t i = 0;i < ans.size(); i++){
	cout << ans[i];
      }
      cout<< endl;
    }
  }
  return 0;
}

訂正コード

 上記の前計算でそれぞれのマスを独立に計算して部分を修正し,上下左右の1マス離れたマスの値から計算を行うように変えたのが下のコードです.

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <cstring>

using namespace std;

vector<string> table;
vector<char> alph;
vector<int> sightx;
vector<int> sighty;

vector<vector<vector<int> > > step; //step[i] i= 0 :north, 1, south, 2, west, 3east;

string direction;
vector<int> dist;
int k;
int n, m;

bool check(int startx, int starty){
  int nowx = startx;
  int nowy = starty;
  int dx[4] = {-1, 1, 0, 0};
  int dy[4] = {0, 0, -1, 1};

  for(int i = 0; i < k; i++){
    int nextdir = -1;

    if(direction[i] == 'N'){
      nextdir = 0;
    }else if(direction[i] == 'S'){
      nextdir = 1;
    }else if(direction[i] == 'W'){
      nextdir = 2;
    }else if(direction[i] == 'E'){
      nextdir = 3;
    }

    if(!(nowx >= 0 && nowx < n && nowy >= 0 && nowy < m)){
	return false;
      }
    
    if(step[nextdir][nowx][nowy] < dist[i]){
      return false;
    }

    nowx += dist[i] * dx[nextdir];
    nowy += dist[i] * dy[nextdir];

    if(!(nowx >= 0 && nowx < n && nowy >= 0 && nowy < m)){
      return false;
    }

  }
  return true;
}

int main(){
  while(cin >> n >> m){
    table.resize(n);
    alph.clear();
    sightx.clear();
    sighty.clear();
    vector<vector<vector<int> > > buf(4, vector<vector<int> > (n, vector<int>(m, 0)));
    //step[i] i= 0 :north, 1, south, 2, west, 3east;
    swap(buf, step);

    for(int i = 0;i < n;i++){
      cin >> table[i];
    }
    for(int i = 0;i <n;i++){
      for(int j = 0;j < m;j++){
	if(table[i][j]- 'A' >= 0 && table[i][j] - 'Z' <= 0){
	  alph.push_back(table[i][j]);
	  sightx.push_back(i);
	  sighty.push_back(j);
	}
      }
    }

    cin >> k;
    direction.clear();
    dist.clear();dist.resize(k);

    for(int i = 0;i < k;i++){
      char dir;
      cin >> dir >> dist[i];		      
      direction += dir;
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    for(int dir = 0; dir < 4; dir++){
      int initi = dx[dir] != 1 ? 0 : n-1;
      int stepi = dx[dir] != 1 ? 1 : -1;

      int initj = dy[dir] != 1 ? 0 : m-1;
      int stepj = dy[dir] != 1 ? 1 : -1;

      int i = initi;
      while(i >= 0 && i < n){
	int j = initj;
	while(j >=0 && j < m){
	  if(table[i][j] == '#'){
	    step[dir][i][j] = 0;
	  }else{
	    
	    int prevx = i+dx[dir];
	    int prevy = j+dy[dir];
	    
	    if(prevx >= 0 && prevx < n && prevy >= 0 && prevy < m && table[prevx][prevy] != '#'){
	      step[dir][i][j] = step[dir][prevx][prevy] + 1;
	    }else{
	      step[dir][i][j] = 0;
	    }
	  }
	  j += stepj;
	}
	i += stepi;
      }
    }

    vector<char> ans;
    for(size_t i = 0; i < alph.size(); i++){
      int x = sightx[i];
      int y = sighty[i];
	
      if(check(x, y)){
	ans.push_back(alph[i]);
      }
    }
    sort(ans.begin(), ans.end());

    if(ans.empty()){
      cout << "no solution" << endl;
    }else{
      for(size_t i = 0;i < ans.size(); i++){
	cout << ans[i];
      }
      cout<< endl;
    }
  }
  return 0;
}