naoya_t@topcoder

SRM531 Div1 Medium: MonsterFarm

過去問 | 02:29 |

なんかEasyより簡単そうに思えたんだけど、やってみて5回目でSystem Test通った程度の体たらくなのでまあEasy頑張っておいてよかった的な。

〈1投目〉ナイーブにシミュレーション。step by stepで100万回ぐらいしか見てない。収束するまでやれてなくてアウト。

〈2投目〉ちまちまstep by stepしてくんじゃなくて自乗を繰り返してみる。まあそれは良いとして。1000000007 周期のやつなんて無いとか高をくくってたのかアウト。

〈3投目〉mod 1000000007系とmod 1000000009系を回して両方で収束を確認できなければ-1、としてみる。2501回回して51回不変、という条件では（手元のcore i7では余裕なのだが）TLEでアウト。

〈4投目〉1001回回して51回不変、にしてみるがまだTLEでアウト

〈5投目〉101回回して51回不変、にしてやっと通った。

最終的なコード：

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '\0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }
  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

const ll MOD7 = 1000000007LL;
const ll MOD9 = 1000000009LL;

class MonsterFarm {
 public:
  int numMonsters(vector<string> transforms) {
    int N = sz(transforms); // 1-50
    vector<vector<ll> > ta(N,vector<ll>(N,0)); // 1-50
    vector<vector<ll> > tb(N,vector<ll>(N,0)); // 1-50
    rep(a,N) {
      vector<int> ns = map_atoi(split(transforms[a],' '));
      tr(ns,it){
        int b=*it - 1;
        // ta[a][b]++;
        ta[b][a]++; // TR
        tb[b][a]++; // TR
      }
    }

    ll sum7_ = 1, sum9_ = 1, staying=0;
    rep(j,101) {
      vector<vector<ll> > taa(N,vector<ll>(N,0)), tbb(N,vector<ll>(N,0));
      rep(x,N) rep(y,N) {
        rep(i,N) taa[x][y] = (taa[x][y] + ta[x][i]*ta[i][y]) % MOD7;
        rep(i,N) tbb[x][y] = (tbb[x][y] + tb[x][i]*tb[i][y]) % MOD9;
      }

      ll sum7 = 0; rep(i,N) sum7 = (sum7 + taa[i][0]) % MOD7;
      ll sum9 = 0; rep(i,N) sum9 = (sum9 + tbb[i][0]) % MOD9;
      
      ta = taa;
      tb = tbb;
      
      if (sum7 == sum7_ && sum9 == sum9_) {
        staying++;
        if (staying==51) return (int)(sum7 % MOD7);
      } else {
        staying=0;
      }
      sum7_ = sum7;
      sum9_ = sum9;
    }
    return -1;
  }
};