SRM603

眠さに耐えつつ参加したら二問解けてhighest rate更新する大勝利回でした。寝不足にはなったけどこの結果なら許します。

結果報告

Level	ProblemName	Status	Point
Easy	MaxMinTreeGame	PassedSystemTest	214.89
Medium	PairsOfStrings	PassedSystemTest	222.02
Hard	SumOfArrays	Opened	0.0

436.91pointの総合59位。Petrさんに勝ったのは初めてじゃなかろうか。

Easy MaxMinTreeGame

問題

各ノードにスコアが与えられている木が与えられる。
(枝はi+1とedges[i]の間に枝が張られている、という形で定義。ノードiのスコアはcosts[i])
今、AさんとBさんがそれぞれ
「枝を一本選択削除し、木を二つに分割。分割要素二つのうち片方を除去する」
と言った操作をじゅんじゅんに繰り返す（Aさんが最初）
Aさんは最終的に残るノードのスコアを最大化・Bさんはスコアを最小化したい。
互いに最適な操作を行った時に得られるスコアを答えよ

考えたこと

なんかうまい具合に分割統治法的なアプローチとかで解けるんですか？とか考えたけどわからず。
メモを書きまくった結果、Aさんが最初に1つのノードを確定させる（つまり葉ノードを取る）以上にスコアを良くしようがなくね？　と推測する。
サブミットしたほうが先か考えるほうが先かはわすれたがコンテスト中に以下のところまで考察した
もしAさんが一回目の操作で小さな木を作って、最初に葉ノードを取る以上に良いスコアが得られると仮定する。
この時、小さな木の中には元の木の葉ノードが必ず含まれることから、Bさんはその葉ノードを取ることによって、上述のようなスコアを取ることを防ぐことが可能である。
よってこれは矛盾である。

要するに、葉ノードのうち最大スコアの値を返せばOKである。

コード

   int findend(vector <int> edges, vector <int> costs){
    int n_size = costs.size();
    int n_deg[n_size];
    memset( n_deg, 0 , sizeof(n_deg) );
    for( int i = 0 ; i < n_size-1; i++ ){
     //cout << i+1 << "-"<<edges[i] << endl;
     n_deg[i+1]++;
     n_deg[edges[i]]++;
    }
    int ans = 0;
    for( int i = 0 ; i < n_size; i++ ){
      if( n_deg[i] == 1 ){
        ans = max( ans, costs[i] );
      }
    }
    return ans;

  }

Medium PairsOfStrings

問題

整数nとkが与えられる
k種類のアルファベットからなる長さnの文字列ペア(A,B)で、
AC=CBが成立するような文字列Cが存在するものの個数を求めよ

考えたこと

、とすると、
AC=CBなるCが存在するとは、なるj

コード

int mod = 1000000007;
int pow( int k , int p){
  long long cur = k;
  long long ans = 1;
  while( p != 0 ){
    if( p % 2 == 1 ){
      ans *= cur;
      ans %= mod;
    }
    cur = cur*cur;
    cur %= mod;
    p/=2;
  }
  return ans;
}

class PairsOfStrings {
   public:
   int getNumber(int n, int k){
     vector<vector<int> > factors;
     int N = n;
     for( int i = 2 ; i*i <= N ; i++ ){
      vector<int> f;
      int cur = 1;
      while( N%i == 0 ){
        N/=i;
        cur*=i;
        ////cout << cur <<"-";
        f.push_back(cur);
      }
      //if( cur != 1 ) //cout << endl;
      factors.push_back(f);
     }
     if( N != 1 ){
       vector<int> f;
      f.push_back(N);
      factors.push_back(f);
     }
     vector<int> divs;
     divs.push_back(1);
     for( int i = 0 ; i < (int)factors.size(); i++ ){
      int s= divs.size();
      for( int j = 0 ; j < (int)factors[i].size(); j++ ){
        for( int k = 0 ; k < s; k++ ){
           divs.push_back(divs[k]*factors[i][j]);
        }
      }
     }
     sort( divs.begin(),divs.end());
     /*
     for( int i = 0 ; i < (int)divs.size(); i++ ){
      //cout << divs[i] << ", ";
     }
     //cout << endl;*/
     int size = divs.size();
     long long cnt[size];
     for( int i = 0 ; i < size; i++){
       int div = divs[i];
       cnt[i] = pow(k,div);
       //cout << i<<":"<<k<<"^"<<divs[i] <<"..."<<cnt[i]<<endl;
     }

     long long ans = 0;
     for( int i = 0 ; i < size; i++ ){
      int div = divs[i];
      //cout << div << "*"<<cnt[i];
      long long tmp = div*cnt[i];
      tmp %= mod;
      ans += tmp;
      ans %= mod;
      for( int j = i+1 ; j < size; j++ ){
        if( divs[j]%div==0 ){
          cnt[j]+=mod;
          cnt[j]-=cnt[i];
          cnt[j]%=mod;
        }
      }
     }


     return ans;

  }
   

約数リストを出す方法がぱっと思い浮かばなくて実装に凄い時間がかかった。
とは言えmediumを通せたと言うのはとても大きいことだと思うので、時間短縮も狙いつつ、通ったことを素直に喜ぼうと思う。
あとk^p のmodを取るところで2011年くらいのGoogleCodeJamが頭をよぎった(k^p(mod n)を計算する際にpが大きな値になるからってうっかりp%nとかつかって計算するとハマるってやつ)
けど、そんな問題だったらk^p計算するだけで滅茶苦茶時間食いそうですね。

約数を列挙するスマートな方法

即興で書こうと思ったらコメントアウト込みで２７行もかかった約数の列挙。
案の定というかなんというか、レッドコーダーの人の実装をみると７行程度でさっくり実装している。
ちゃんと動作検証はしてないけど大体以下の様な感じ。

 for( int i = 1 ; i*i <=N ; i++ ){
  if( N%i==0 ){
    divs.push_back(i);
    if(i*i!=N) divs.push_back(i/N); 
  }
 }
 sort( divs.begin(),divs.end());

こういう実装ノウハウもちゃんと吸収しないといかんな。と思う今日このごろ。