Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-09-12

[][] TopCoder Single Round Match 517 Div.1 22:56 はてなブックマーク -  TopCoder Single Round Match 517 Div.1 - 練習帳

結果

 コンテスト結果概要

 個人結果(要ログイン)

2500:21:35.186Challenge Succeeded170.71->0.00
6000:52:37.760Opented0.00
9000:51:19.312Opented0.00
Challenge..0.00

部屋(Room 1) 13位,全体 594位

Rating : 1504 → 1413 (-91)

 500どころか250も解けなかったという.

250 CompositeSmash

問題文

 問題文

要約

 整数nを適当に2つの数の積に分解する(分解の仕方は何通りかあるがそのうちの1つを適当に選ぶ),できた2つの数をそれぞれ同じ用に2つに分解する.以降これを可能な限り繰り返す.別の数targetが与えられているので,nをどのように分解しても,その分解途中にtargetが現れるかを判定せよ.n, targetは2以上100000以下の数.

方針

 nを1通りに分解できるなら"Yes"...とは限らず,さらにn%target==0の条件がつかないとならない.一方,分解できなかったら"No"...とも限らず,もしn==targetなら実際には"Yes"となる.などのように場合分けが煩雑になってしまいコーナーケースを潰しきれませんでした.

 今回の提出コードも(n, t)=(1024, 4)のケースで落とされてしまいました.

提出コード

(このコードは正しくありません)

class CompositeSmash {
public:
  string thePossible(int n, int target) {
    if(n % target != 0){
      return "No";
    }
 
    int cnt = 0;
    for(int i = 2; i*i <= n; i++){
      if(n%i==0){
        cnt++;
      }
    }

    if(cnt == 1){
      return "Yes";
    }else if(cnt == 0){
      if(n == target){
        return "Yes";
      }else{
        return "No";
      }
    }
 
    if(n == target){
      return "Yes";
    }
 
    int cntt = 0;
    for(int i = 2;i * i<=target;i++){
      if(target%i==0){
        cntt++;
      }
    }
    if(cntt == 0){
      return "Yes";
    }else{
      return "No";
    }
  }
};

 Sigmarさんの「KISSの原則」*1の話にもありましたが,コンピュータに探索を任せるように思考を変えられると,このような問題を解けるようになるのかな,と忸怩たる思いをしながら感じました.

修正コード
(#include 省略)
using namespace std;

int memo[111111];
bool solve(int n, int t){
  if(n == t){
    return memo[n] = true;
  }
  if(memo[n] != -1){
    return memo[n];
  }

  bool dividable = false;
  bool ok = true;
  for(int i = 2; i*i<=n; i++){
    if(n%i != 0){
      continue;
    }
    dividable = true;
    ok &= (solve(n/i, t)|solve(i, t));
  }

  return memo[n] = (ok&dividable);
}

class CompositeSmash {
public:
  string thePossible(int n, int t) {
    memset(memo, -1, sizeof(memo));
    bool ok = solve(n, t);
    return ok ? "Yes" : "No";
  }
};

2011-09-10

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

概要

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

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

結果

問題ABCDE
提出時刻0:060:371:171:58-
得点/誤答回数482/0852/0888/-30/-2-
Hack成功/失敗+0/-0
総得点2228

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

Rating:1631 → 1671 (+40)

 紫色に復帰しました.D問題をHackするために誤答覚悟で提出したのですが,回答キューが混んでいて終了までに判定が終わりませんでした,残念.

A. Cifera

問題文

 問題文

提出コード(c++)
(include 省略)

using namespace std;

typedef long long ll;

int main(){
  ll k;
  while(cin >> k){
    ll l;cin >> l;
    bool ok = true;
    int cnt = 0;
    while(l > 0){
      if(l == 1){
	break;
      }
      if(l%k != 0){
	ok = false;
	break;
      }
      l /= k;
      cnt++;
    }

    if(ok){
      cout << "YES" << endl;
      cout << cnt-1 << endl;
    }else{
      cout << "NO" << endl;
    }
  }
  return 0;
}

B. PFAST Inc.

問題文

 問題文

分析

 B問題をdfsで解く決心をするところで一番時間がかかりました.なぜ2**16通り試す方法を思いつかなかったのか,自分でも分かりません.

提出コード(c++)
(#incude 省略)

using namespace std;

vector<string> s;
map<string, int> table;
int bad[20][20] = {};

int n;

void dfs(vector<int> now, int pos, vector<int>& ans){
  if(pos == n){
    ans = now;
    return;
  }

  vector<int> ans1;
  dfs(now, pos+1, ans1);

  vector<int> ans2;
  bool ok = true;
  for(int i = 0; i < now.size(); i++){
    if(bad[now[i]][pos] == 1){
      ok = false;
      break;
    }
  }
  if(ok){
    now.push_back(pos);
    dfs(now,pos+1, ans2);
  }

  if(ans1.size() > ans2.size()){
    ans = ans1;
  }else{
    ans = ans2;
  }
}

int main(){
  int  m;
  while(cin >> n >> m){
    s.clear();s.resize(n);
    table.clear();
    memset(bad, 0, sizeof(bad));
    for(int i = 0; i < n; i++){
      string name;
      cin >> name;
      s[i] = name;
      table[name] = i;
    }

    for(int j = 0; j < m; j++){
      string a, b;
      cin  >> a >> b;
      bad[table[a]][table[b]] = 1;
      bad[table[b]][table[a]] = 1;
    }

    vector<int> start;
    vector<int> ans;
    dfs(start, 0, ans);

    vector<string> name;
    for(int i = 0;i< ans.size();i++){
      name.push_back(s[ans[i]]);
    }

    sort(name.begin(), name.end());
    cout << ans.size() << endl;
    for(size_t i =0;i < ans.size();i++){
      cout << name[i] << endl;
    }
  }
  return 0;
}

C. Grammar Lessons

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

分析

 問題文の条件の読み方が疎かでした.

・全ての単語の性別が一致している -> WA

・文(2単語以上)の条件だけ実装,語(1単語のみ)の実装を忘れる -> WA

・語でvalidaになる条件を間違える -> WA

 つぎはぎでの修正なので提出コードは目を覆いたくなるような代物です.

提出コード(c++)
(#include 省略)

using namespace std;

bool checkone(const string& s, const string& suf){
  if(s.size() < suf.size()){
    return false;
  }
  for(int i = 0;i < suf.size();i++){
    if(s[s.size() - 1-i] != suf[suf.size()-1-i]){
      return false;
    }
  }
  return true;
}


pair<int, int> check(const string& s){
  if(checkone(s, "lios")){
    return make_pair(0, 0);
  }
  if(checkone(s, "etr")){
    return make_pair(0, 1);
  }
  if(checkone(s, "initis")){
    return make_pair(0, 2);
  }
  if(checkone(s, "liala")){
    return make_pair(1, 0);
  }
  if(checkone(s, "etra")){
    return make_pair(1, 1);
  }
  if(checkone(s, "inites")){
    return make_pair(1, 2);
  }
  return make_pair(-1, -1);

}


int main(){
  string s;
  cin >> s;
  pair<int, int > type = check(s);
  pair<int, int > firsttype = check(s);

  int count = 0;
  int gender = type.first;
  int prev = type.second;
  bool one = (prev == 1);

  while(cin >> s){
    count++;
    pair<int, int> checked = check(s);

    if(checked.first != gender){
      cout << "NO" <<endl;
      return 0 ;
    }

    if(prev > checked.second ){
      cout << "NO" <<endl;
      return 0;
    }

    if(prev == 1 && checked.second != 2){
      cout << "NO" <<endl;
      return 0;
    }
    
    prev = checked.second;
    if(prev == 1){
      one = true;
    }

  }

  if(count == 0){
    if(firsttype.first == -1){
      cout << "NO" <<endl;
      return 0;
    }else{
      cout << "YES" << endl;
      return 0;
    }
  }

  if(one){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }

  return 0;
}

2011-09-04

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

概要

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

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

結果

問題ABCDE
提出時刻0:040:110:45--
得点/誤答回数492/0956/01180/-1--
Hack成功/失敗+1/-0
総得点2728

部屋内8位(Room 4),全体142位

Rating:1633 → 1631 (-2)

 4問解答できず.

A. Petya and Strings

問題文

 問題文

分析

 すべての文字を小文字に変換して,std::string::operator<で比較します.

提出コード(c++)
(#incude 省略)

using namespace std;

char convert (char c){
  if(c >= 'A' && c <= 'Z'){
    return c - 'A' + 'a';
  }
  return c;
}

int main(){
  string s;
  while(cin >> s){
    string t;
    cin >> t;
    for(size_t i = 0;i < s.size();i++){
      s[i] = convert(s[i]); 
      t[i ] = convert(t[i]);
    }
    if(s == t){
      cout << 0 << endl;
    }else if(s< t){
      cout << -1 << endl;
    }else{
      cout << 1 << endl;
    }
    
  }
  return 0;
}

B. Petya and Square

問題文

 問題文

分析

 分割する折れ線は正方形の中心を通らなければならないので,その中心を頂点として含む正方形達(真ん中にある4つ)が指定されている場合は分割できません.逆にそれ以外の場合,縦か横少なくとも一方では分割できます.

提出コード(c++)
(#incude 省略)

using namespace std;

int main(){
  int N, x, y;
  while(cin >> N >> x >> y){
    int n = N / 2;
    if(x == n || x == n + 1){
      if(y == n || y == n + 1){
	cout << "NO" <<endl;
      }else{
	cout << "YES" << endl;
      }
    }else{
      cout << "YES" << endl;
    }
  }
  return 0;
}

C. Petya and Inequiations

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

分析

 ベクトルa=(a[1], ..., a[n])を考える.ベクトルの2-ノルムはできるだけ大きくしたいのですが,どれかの成分を増やせばそれだけ2-ノルムは大きくなるので,答えの候補となるaの1-ノルムは初めからyであると仮定してよいです.

 直接の計算から,p>q>=1の時,

p**2 + q**2 < (p+1)**2 + (q-1)**2

が成立します.標語的に言えば,「大きい数をより大きくした方が2-ノルムは大きくなる」となります.

これを繰り返すと,結局1つを除いて1とするのと2-ノルムが最大となります.これをxより大きいかを判定します.

 ただ,n>yのときには,そもそも1-ノルムがyより小さいベクトルが一つもないので,最初に除外しなければなりません(WAはこれが原因でした.大反省点です).

提出コード(c++)
(#incude 省略)

using namespace std;
typedef long long ll;

int main(){
  ll n, x, y;
  while(cin >> n >> x >> y){
    ll a1 = y - (n-1);
    if(a1*a1 + (n-1) >= x){
      cout << a1 << endl;
      for(int i = 1;i < n;i++){
	cout << 1 << endl;
      }
    }else{
      cout << -1 <<endl;
    }
  }
  return 0;
}

D. Petya and Divisors

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

分析

 終了直後にこのように考え,これさえ実装できれば...と思っていたのですが,全く違いました.

 http://twitter.com/#!/delta2323_/status/109993109466787840

 これのアイデアは次のようなものです.

 i番目のクエリが来る前に,各素因数pごとにi-y[i]<= j < iの範囲でのpベキの最大値を求めておき,それをa[p]とする.i番目のクエリが来たら,x[i]を素因数分解し,素因数pのベキの数をb[p]と置く.すると,求める数はΠ(b[p]+1) - Π(a[p]+1)となる.しかし,例えば次の2つのテストケースに対して,この式では3番目の答えが同じになってしまい,正しくありません(実際には前者は解に10を含むのに対し,後者は含みません).

3
2 0
5 0
100 2
3
10 0
1 0
100 2

 この解法の根本的な間違いは,解を全探索することはできないと考えた点だと思います,なので,約数の数を求める公式Π(e[p]+1)を使おうとして,各素因数を独立に考えれば十分だとなりました.しかしx以下の約数はsqrt(x)で数えあげるので,全部数え上げてもO(n**(3/2))で間に合います.

修正コード

以下はwuzhengkaiさんの解答を参考にしています.

(#include 省略)

using namespace std;

int last_appearance[111111];

int main(){
  int n;
  while(cin >> n){
    vector<int> x(n);
    vector<int> y(n);
    for(size_t i = 0;i < n;i++){
      cin >> x[i] >> y[i];
    }

    memset(last_appearance, -1, sizeof(last_appearance));

    for(int i = 0; i< n; i++){
      int cnt = 0;
      for(int j = 1; j *j<=x[i]; j++){
	if(x[i] % j == 0){
	  int p = j; int q = x[i]/j;
	  if(last_appearance[p] < i - y[i]){
	    cnt++;
	  }
	  last_appearance[p] = i;
	  if(last_appearance[q] < i - y[i]){
	    cnt++;
	  }
	  last_appearance[q] = i;
	}
      }
      cout << cnt  << endl;
    }
  }
  return 0;
}

2011-09-01

[][] TopCoder Single Round Match 516 Div.1 08:50 はてなブックマーク -  TopCoder Single Round Match 516 Div.1 - 練習帳

 コンテスト結果概要

 個人結果(要ログイン)

2500:14:58.653Passed System Test200.11
5000:55:18.277Challenge Succeeded204.37->0
10000:04:24.523Opented0.00
Challenge..0.00

部屋(Room 37) 8位,全体 284位

Rating : 1450 → 1504 (+54)

 黄色復帰しましたが,500が恒常的に解けないと頭打ちなので,どうにかしないとならないです.

250 NetworkXOneTimePad

問題文

 問題文

方針

 aを鍵bで暗号化してcになるならば,aを鍵としてcに同じ処理を行えば鍵bが得られます(a xor b = c => c xor a = b).従って,cipher textの0番目がどのplain textを暗号化したものかを決めてしまえば,鍵の候補が得られます.その鍵を用いて他のcipher textを複合化して,もともとのplain textのうちのどれかが得られるかを調べます.

提出コード

 せっかく配列をソートしたのに,線型探索をしたのが残念です.

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
 
using namespace std;
 
string gen(string& s, string t){
  string ans = "";
  for(int i = 0; i < s.size(); i++){
    char c;
    if(s[i] == t[i]){
      c = '0';
    }else{
      c = '1';
    }
    ans+=c;
  }
  return ans;
}
 
 
class NetworkXOneTimePad {
public:
  int crack(vector <string> p, vector <string> q) {
    int n = p.size();
    int m = q.size();
    sort(p.begin(), p.end());
    sort(q.begin(), q.end());
    int ans = 0;
 
    for(int i = 0; i < n; i++){
      string key = gen(q[0], p[i]);
      bool isans = true;
      for(int j = 1; j < m; j++){
        string input = gen(q[j], key);
        if(find(p.begin(), p.end(), input) == p.end()){
          isans = false;
        }
      }
      if(isans){
        ans++;
      }
    }
    return ans;
  }
};

500 RowsOrdering

問題文

 問題文

方針

 各columnに割り当てるpermutation(1~50)がそれぞれのcolumnに属する文字達だけから決められ,他のcolumnや,column同士の優先順序を決めるpermutation(1~M)に依存しないという点が,計算量を落とす時に重要なポイントだと思います.この事を説明する為に,columnの優先順序(1~Mのpermutation)と,各columnでの文字の優先順序(1~50のpermutation)が決まっていたとして,あるrowの順位がどのように決まるかを考えます.

 例えば各々のpermutationは1, 2, 3, ...という自明のものとして,rows ={"cbd", "dac", "bbb"}とします,例えばcbdの順位は

2(cの順位) * 50**2(倍率) + 1(bの順位) * 50**1(倍率) + 3(dの順位) * 50**0(倍率)

と計算できます.別の文字列も同じように足し算の形に直すと,

2(cの順位) * 50**2(倍率) + 1(bの順位) * 50**1(倍率) + 3(dの順位) * 50**0(倍率)
3(dの順位) * 50**2(倍率) + 0(aの順位) * 50**1(倍率) + 2(cの順位) * 50**0(倍率)
1(bの順位) * 50**2(倍率) + 1(bの順位) * 50**1(倍率) + 1(bの順位) * 50**0(倍率)

倍率をまとめあげます.

2(cの順位)                         1(bの順位)                          3(dの順位)
3(dの順位) * 50**2(倍率) + 0(aの順位) * 50**1(倍率) + 2(cの順位) * 50**0(倍率)
1(bの順位)                         1(bの順位)                          1(bの順位) 

 各columnに割り振るpermutation(1~50)は自由に決められます.従って,自分に割り振られる倍率がいくらだったとしても,それぞれのcolumnは倍率抜きでの合計(上図で縦に並んでいる値の合計)を最小化するようにpermutation(1~50)を決めれば良いです.そして,そのようなpermutation(1~50)はそれぞれの列での出現頻度が多い文字から高い順位を与えるものです.

 次にcolumnの優先順序の決め方を考えます(ただ,自分のコードは間違っていてそれを直せていないので,アイデアのみ紹介します)

 下のコードでは次のようにして優先順序を計算しています:まず,それぞれのcolumnについて,上と同じように文字の出現頻度を多い順に並び替え,次にそれぞれの列で求めた配列を辞書式順序(e.g [5, 4, 3, 2] > [5, 4, 3, 1])で大きい順に並び替えています.

提出コード

 同じ部屋の対戦者が自分の提出コードのバグを見つけて行った一斉攻撃に巻き込まれてChallengeされました.

(間違っています)

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
int getnum(char c){
  if(c >= 'a' && c<='z'){
    return c - 'a' + 1;
  }else{
    return c - 'A' + 27;
  }
}
 
vector<ll> stat;
vector<vector<int> > prestat;
 
bool comp(int i, int j){
  return stat[i] < stat[j];
}
 
bool comppre(int i, int j){
  return prestat[i] < prestat[j];
}
 
ll mod =  1000000007;
 
class RowsOrdering {
public:
  int order(vector <string> rows) {
    int m = rows[0].size();

    prestat.clear();prestat.resize(m, vector<int>(50, 0));
    vector<int> preind(m);
    for(int i = 0;i < m;i++){
      for(int j = 0;j < rows.size();j++){
        prestat[i][getnum(rows[j][i])]++;
      }
      preind[i] = i;
      sort(prestat[i].rbegin(), prestat[i].rend());
    }
    sort(preind.rbegin(), preind.rend(), comppre);    
 
    ll ans = 0;
    ll multiplier = 1;
    for(int i = m-1; i >= 0; i--){
      int ii = preind[i];
      stat.clear();stat.resize(50);
      vector<int> ind(50);

      for(int j = 0;j < 50;j++){
        ind[j] = j;
      }

      for(int j = 0;j < rows.size();j++){
        stat[getnum(rows[j][ii])]++;
      }

      sort(ind.rbegin(), ind.rend(), comp); 

      ll base = i == 0 ? 1 : 0;
      for(int j = 0; j < stat.size(); j++){
        ans = (ans + ( ( (stat[ind[j]] * base) + mod )%mod) + mod) % mod;
        base = (base + multiplier + mod)%mod;
      }
      multiplier = (multiplier * 50 + mod)%mod;
    }
    return static_cast<int>(ans);
  }
};

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を思いつかなかったのだろう...次回その修正を行います.