cafelier@SRM

SRM424 Div2

SRM | 22:32 |

SRM424 の成績・ソース (要ログイン) : AC/AC/WA : 初参加

250 開く

• 『あたえられた文字列のなかのAとZの部分だけreverseして返せ』

• まあ実装するだけだなー
  • 'A'と'Z'の部分を'_'に変えつつ'A'と'Z'の部分だけ別の文字列に足し込んで覚えておく
  • もういっぺんループ。'_'の部分に、さっきの'A'と'Z'を貯め込んだ文字列の後ろの字から埋めていく
• 完了。submit

500 開く

• 『各桁の数字の積が n になっているような最小の数の桁数を求めてね』

• とりあえず n を素因数分解する Project Euler 脳。
  • 11 以上の素因数があったら不可能。
  • 7 と 5 の個数分の桁数は必要
  • 8==2^3 を取れるだけ取る
  • 9==3^2 を取れるだけ取る
  • 6==2*3 を取れるだけ取る
  • 残った 2 か 3 があればそれも

• 実装完了。サンプル通らない
  • n==1 のとき 0 桁になってる。うわこれサンプルになかったら絶対見逃してた
• 通った。submit。

1000 開く

• 『N点の無向グラフがあります。各枝に優先度が設定されてます。ぴったりM要素の枝集合で優先度最大のものを求めてね』
  • おいこれ枝を優先度でソートして最初のM個とってくるだけじゃないのか。なんだこれ
  • サンプル合わない
  • なんかメッセージ来た
    • 『かならずグラフが連結になるようなM要素の枝集合で優先度最大のものを求めてね』だそうです。はあ。

• まあ、まず最小全域木を求めて、残りM-N+1本は、使わなかった辺のなかから優先度高いのを順に使っていくだけだ
• Prim のアルゴリズムを書く。
  • ただし Prim の途中で捨てた辺はあとで再利用するかも知れないので別に覚えておく
  • 全域木完成したら、覚えておいた辺 + まだ使ってない辺から優先度高いのをとってくる
• サンプル通った。合ってるはず…submit！

• Div2なら全問解けるぜ俺すごい！
• と余裕かましてたらシステムテストで落ちました。ばーかばーか
  • （※ submit したコードだと !Q.empty() と nVisited == N の条件判定する順番が逆だった。これだと、キューに残った最後の辺で全域木が完成するケースで残りM-N+1本を足すコードが走らないので間違う）

撃墜タイム

• 500 で、6 があるケースを考慮してるように見せかけて 8*9*6みたいなのがあるケースを考慮してないのを見つけたので Challenge。成功
• 500 で、n=1 に対応してないのを見つけたので Challenge。成功

感想

• 500は単に9から順に割れるだけ割っていけばよかったらしい。変に考えすぎた…。

• 1000はミスはともかくとして、そもそも、プリムではなくクラスカルにすべきだったかな、と思っています。クラスカルなら必ず優先度高い順に辺を捨てるので、わざわざ別にとっておくとかしなくても、捨てる端からM-N+1本まで辺を拾っていけばいいだけ。

// SRM424 Div2 Lv3 : Kruskal's Algorithm
#include <vector>
#include <string>
#include <set>
using namespace std;

struct BestRoads
{
   vector<int> numberOfRoads(vector<string> roads, int M)
   {
      int N = roads.size();
      vector<int> ans(N);

      // 辺を優先度高い順に並べる
      typedef pair<int,int> road;
      set<road> Q;
      for(int i=0; i<N; ++i)
         for(int j=i+1; j<N; ++j)
            if( roads[i][j]=='Y' )
               Q.insert( road(i,j) );

      vector<int> p(N,-1), s(N, 1); 
      int div = N; // Union-Find 用データ。p:親, s:各連結成分のサイズ, div:連結成分の個数
      int red = M-N+1; // 拾っておきたい捨て辺の本数

      for(set<road>::iterator it=Q.begin(); it!=Q.end(); ++it)
      {
         road r = *it;
         int a=r.first;  while(p[a]!=-1) a=p[a];
         int b=r.second; while(p[b]!=-1) b=p[b];
         if( a != b ) // まだつながってないとこだったらつなげる
         {
            ans[r.first]++, ans[r.second]++, div--;
            if(s[a]<s[b]) p[a]=b, s[b]+=s[a];
            else          p[b]=a, s[a]+=s[b];
         }
         else if( red ) // 繋がってるところでも優先度高ければ使う
            ans[r.first]++, ans[r.second]++, red--;
      }

      return (red==0 && div==1) ? ans : vector<int>();
   }
};