Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-08-05

Codeforces Beta Round #79 (Div. 2 Only) 01:31 はてなブックマーク - Codeforces Beta Round #79 (Div. 2 Only) - 練習帳

概要

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

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

結果

問題ABCDE
提出時刻0:080:200:44--
得点/誤答回数484/0920/01236/0--
Hack成功/失敗+1/-0
総得点2740

部屋内3位(Room 10),全体68位

Rating:1478 → 1566 (+88)

A. Clothes

問題文

 問題文

分析

 i番目のj番目の洋服がマッチしている時に限りtable[i][j] = 1となる行列を用意して,i, j, k番目の洋服がお互いにマッチしているかを全探索しています.

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

using namespace std;

int table[111][111];
typedef long long ll;

int main(){
  int n, m;
  while(cin >> n >> m){
    vector<int> p(n);
    for(int i = 0; i < n; i++){
      cin >> p[i];
    }
    memset(table, 0, sizeof(table));
    for(int i = 0; i < m; i++){
      int u, v;
      cin >> u >> v;
      u--;v--;
      table[u][v] = table[v][u] = 1;
    }

    ll mn = 1e10;

    for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
    for(int k = 0; k < n; k++){
      if(i == j || j == k){
	continue;
      }
      ll buf = p[i] + p[j] + p[k];

      if(table[i][j] == 1){
	if(table[j][k] == 1){
	  if(table[k][i] == 1){
	    mn = min(buf, mn);
	  }
	}
      }
    }
    } 
    }
    if(mn == 1e10){
      cout << -1 <<endl;
    }else{
      cout << mn <<endl;
    }
  }  
}

B. Sum of Digits

問題文

 問題文

分析

 最初に受け取る整数は100000桁程度で,整数ではなく文字列として受け取らなければならないですが,1回和を取る操作を行うと最大900000程度になるので,整数として値を格納できます.cntを数え間違えるのが怖かったですが,それに応じて処理を行う関数も2種類用意しています.

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

using namespace std;

typedef long long ll;

ll doit(string s){
  ll ret = 0;
  for(int i = 0; i <s.size(); i++){
    ret += s[i] - '0';
  }
  return ret;
}

ll doit(ll s){
  ll ret = 0;
  while(s > 0){
    ret += s %10;
    s /= 10;
  }
  return ret;
}

int main(){
  string s;
  while(cin >> s){
    int cnt = 0;
    if(s.size() ==1){
      cnt = 0;
    }else{
      int next;
      next = doit(s);
      if(next >= 0 && next <= 9){
	cnt = 1;
      }else{
	cnt = 1;
	while(true){
	  next = doit(next);
	  cnt++;
	  if(next >= 0 && next <= 9){
	    break;
	  }else{
	  }
	}
      }
    }
    cout << cnt << endl;
  }
}

C. Homework

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

分析

 文字の種類ごとに出現数をカウントし,個数の少ないアルファベットから削除マークをつけています.

 答えの文字列に現れる文字の種類だけを最小化すればよく,文字数を最小にする必要はありません.従って,

2番目のサンプルケース(下)では,aaaaもaaaも答えになると思います,

abacaba
4

 本番では安全のためサンプルケースにあわせました,下のコードでコメントアウトしている部分を加えれば文字数も最小の答えを返します.

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

using namespace std;

vector<int> stat;
vector<int> ind;
vector<vector<int> > pos;

bool comp(int i, int j){
  return stat[i] < stat[j];
}

int main(){
  string s;
  while(cin >> s){
    int n;
    cin >> n;
    stat.clear();
    stat.resize(26);
    ind.clear();
    ind.resize(26);
    for(int i = 0; i < 26; i++){
      ind[i] = i;
    }
    pos.clear();
    pos.resize(26);
    for(int i = 0; i < s.size(); i++){
      pos[s[i] - 'a'].push_back(i);
      stat[s[i] - 'a']++;
    }
    sort(ind.begin(), ind.end(), comp);
    vector<int > deleted(s.size(), 0);

    int kind = 0;
    for(int i = 0; i < 26; i++){
      if(stat[i] != 0){
	kind ++;
      }
    }

    for(int i = 0; i < 26; i++){
      if(pos[ind[i]].empty()){
	continue;
      }

      if(pos[ind[i]].size() <= n){
	for(int j = 0;j < pos[ind[i]].size(); j++){
	  deleted[pos[ind[i]][j]] = 1;
	}
	kind--;
	n-=pos[ind[i]].size();
      }else if(pos[ind[i]].size() > n){
	/*
	for(int j = 0; j < n; j++){
	  deleted[pos[ind[i]][j]] = 1;
	}
	*/
	n = 0;
      }
      if(n == 0){
	break;
      }
    }

    string ans;
    for(int i = 0; i < s.size(); i++){
      if(deleted[i] == 0){
	ans += s[i];
      }
    }
    cout << kind << endl;
    cout << ans  <<endl;
  }
}