Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-08-30

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

概要

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

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

結果

問題ABCDE
提出時刻0:050:110:16-1:57
得点/誤答回数490/0956/01404/0-0/4
Hack成功/失敗+0/-0
総得点2850

部屋内3位(Room 13),全体67位

Rating:1550 → 1633 (+88)

 問題文がわかりやすく,すんなり理解できました.

A. Nearly Lucky Number

問題文

 問題文

分析

lucky numberかを判定する部分が0を例外ケースになるような書き方になっていました.気づいてよかったです.

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

using namespace std;

int main(){
  string s;
  while(cin >> s){
    int c = 0;
    for(size_t i = 0;i < s.size();i ++){
      if(s[i] == '4' || s[i] == '7'){
	c++;
      }
    }
    bool islucky = true;
    if(c == 0){
      islucky = false;
    }else{
      while(c > 0){
        if(c%10 != 4 && c%10 != 7){
  	  islucky = false;
        }
        c /= 10;
      }
    }
    if(islucky){
      cout << "YES" << endl;
    }else{
      cout << "NO" << endl;
    }
  }
  
  return 0;
}

B. Choosing Laptop

問題文

 問題文

分析

 前から順番に埋めていくと結局abcdabcda・・・という並び方が最小になります.

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

using namespace std;

int main(){
  int n;
  while(cin >> n){
    for(int i = 0;i < n;i++){
      if(i%4 == 0){
	cout << 'a';
      }else if(i%4 == 1){
	cout << 'b';
      }else if(i%4 == 2){
	cout << 'c';
      }else if(i%4 == 3){
	cout << 'd';
      }
    }
    cout << endl;
  }
  
  return 0;
}

C. Lucky Sum of Digits

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

分析

 まず,4の数と7の数としてあり得るものを全て列挙して,4の数が最大になる組み合わせを選びます.それらを44...4477...77の順番で並べたものが答えです.

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

using namespace std;

int main(){
  int n;
  while(cin >> n){
    int c4 = -1;
    int c7 = -1;
    for(int i = 0;i*7 <=n ;i++){
      if((n - i*7)%4 == 0){
	c4 = (n - i*7)/4;
	c7 = i;
      }
    }
    if(c7 == -1){
      cout << -1 << endl;
    }else{
      for(int i = 0;i < c4;i++){
	cout << 4;
      }
      for(int i = 0;i < c7;i++){
	cout << 7;
      }
      cout << endl;
    }
  }
  
  return 0;
}

E. Lucky Tree

 問題文:http://www.codeforces.com/contest/110/problem/E

分析

 luckyではない枝でつながっている節同士をまとめて一つの大きな節として,大きな節とluckyな枝からなるグラフに変換します.すると,2つの(小さな)節がluckyな枝を含む道でつながる必要十分条件は異なる節に属する事です.

提出コード(c++)

 luckyでない枝でつながっている節同士を繋げるところで苦戦しました.nodeという配列を用意し,nodeの値が同じ節はまとめられるとするのですが,その番号の振り方を間違えてしまいました.まず最初に考えたのがluckyな枝につながっている節uについてはnode[u] = uとし,その番号を大きな節のidにしようとしましたが,例えば次のケースの場合うまく節同士をまとめられません.

6
1 2 100
2 3 7
3 4 100
4 5 7
5 6 100

 この例では6個の節が1直線上に並んでいて,2個ずつにまとめなければなりません.3, 4は同じ大きな節に属さなければならないですが,これらはluckyな枝につながっているので,nodeの値はそれぞれ3, 4となり,異なった値が振られてしまいます.

 そこで,提出コードではまとめられる節のなかで,lucky nodeにつながっているもののうち,最も番号をnodeの値として振るようにしました.これでPretestは通ったのですが,TestCase14でWAでした.

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

using namespace std;

typedef long long ll;

bool islucky(int w){
  if(w == 0){
    return false;
  }
  while(w > 0){
    if(w % 10 != 4 && w % 10 != 7){
      return false;
    }
    w/=10;
  }
  return true;
}

vector<vector<int> > adjucent;
int node[11111];

int calc_to_belong(int prev, int pos){
  for(int i = 0; i < adjucent[pos].size();i++){
    int next = adjucent[pos][i];
    if(node[next] != -1){
      if(node[pos] == -1){
	node[pos] = node[next];
      }else if(node[pos] != -1 && node[pos] > node[next]){
	node[pos] = node[next];
      }
    }
  }

  if(node[pos] != -1){
    return node[pos];
  }

  for(int i = 0; i < adjucent[pos].size();i++){
    int next = adjucent[pos][i];
    if(next == prev){
      continue;
    }
    int to_belong = calc_to_belong(pos, next);
    if(to_belong != -1){
      if(node[pos] == -1){
	node[pos] = to_belong;
      }else if(node[pos] != -1 && node[pos] > node[next]){
	node[pos] = node[next];
      }
    }
  }
  return node[pos];
}

int main(){
  ll n;
  while(cin >> n){
    adjucent.clear();adjucent.resize(n);
    memset(node, -1, sizeof(node));
    for(int i = 0; i < n-1; i++){
      int u, v, w;
      cin >> u >> v >> w;
      u--;v--;
      if(islucky(w)){
	node[u] = u;
	node[v] = v;
      }else{
	adjucent[u].push_back(v);
	adjucent[v].push_back(u);
      }
    }  

    for(int i = 0;i < n;i++){
      int to_belong = calc_to_belong(-1, i);
      node[i] = to_belong;
    }
    
    vector<ll> stat(n);
    for(int i = 0;i < n;i++){
      stat[node[i]]++;
    }

    ll ans = 0;
    for(int i = 0;i <n;i++){
      if(stat[i] > 0){
	ans += (stat[i] * (n-stat[i]) * (n-stat[i]-1));
      }
    }
    cout << ans << endl;
  }
  return 0;
}

分析2

 ここまで気づいていてなんでUnion Findを思いつかなかったのだろう...次回その修正を行います.