cafelier@SRM

Codeforces 77 Div1 E

CF | 19:22 |

• 島が V 島あります。
• 橋が E 本ありまして島と島を結んでいます。
• さらに橋を何本か足して、属する島の個数が"Lucky Number"な連結成分を作りたいです。
  • Lucky Number とは、10進表記したとき全ての桁が4か7な数
• 足す橋の本数を最小にして下さい。
• V ≦ 10万

他の皆様の回答を見て勉強になったので自分でも書いておくメモ。たぶん典型手法ではあるのだと思う。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

// 何の変哲もない普通の Union-Find
struct UnionFind
{
   vector<int> uf, sz;

   UnionFind(int N): uf(N), sz(N,1)
      { for(int i=0; i<N; ++i) uf[i] = i; }
   int Find(int a)
      { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
   void Union(int a, int b)
      {
         a = Find(a);
         b = Find(b);
         if( a != b )
         {
            if( sz[a] >= sz[b] ) swap(a, b);
            uf[a] = b;
            sz[b] += sz[a];
         }
      }
};

// 何の変哲もない普通のLucky Number判定
bool is_lucky(int x)
{
   if( x==0 )
      return false;
   for(; x; x/=10)
      if(x%10!=4 && x%10!=7)
         return false;
   return true;
}

// 何の変哲もない普通のPARTITION問題を解く
int solve_PARTITION(map<int,int>& size_to_num, int total)
{
   static const int INF = 0x3fffffff;

   vector<int> minStep(total+1, INF);
   minStep[0] = 0;
   for(auto s2n : size_to_num)
   {
      int siz = s2n.first;
      int num = s2n.second;
      for(int n=1; num; num-=n,n<<=1)
      {
         n = min(num, n);
         for(int x=total; x-siz*n>=0; --x)
            minStep[x] = min(minStep[x], minStep[x-siz*n]+n);
      }
   }

   int result = INF;
   for(int x=1; x<=total; ++x)
      if( is_lucky(x) )
         result = min(result, minStep[x]);
   return (result >= INF ? -1 : result-1);
}

// メイン
int main()
{
   for(int V,E; cin>>V>>E; )
   {
      UnionFind uf(V);
      for(int i=0; i<E; ++i)
      {
         int u, v;
         cin >> u >> v;
         uf.Union(u-1, v-1);
      }

      map<int,int> size_to_num;
      for(int v=0; v<V; ++v)
         if( uf.Find(v) == v )
            size_to_num[uf.sz[v]]++;

      cout << solve_PARTITION(size_to_num, V) << endl;
   }
}

とりあえず前半のグラフっぽい話はUnion-Findして連結成分のサイズを数えれば数の問題に落ちる。

• 自然数のリスト x[0] ... x[N-1] が与えられる（重複可）。
• ここからできるだけ少ない個数を選んで、和が Lucky Number になるようにせよ。
• Σx ≦ 10万

こう。これはほぼ明らかに、典型的なNP完全問題と同じ問題で、これを解かなくてはならない。ただしNP完全といってもΣxに依存する O(N・Σx) 時間のDPは簡単に作ることができる。

(ここまで前置き)

で、O(N・Σx) は 10万の2乗なので間に合わないので、どうするかという話で

• リストに重複があったら個数を数えてまとめる (和が10万なので、重複を纏めるとリストの長さは高々√10万)
• まとめた部分は
  • 1個使うパターン
  • 2個使うパターン
  • 4個使うパターン
  • ...
• だけを考えて表を更新していけば全パターン網羅することができて、logのオーダで終わる