naoya_t@topcoder

過去問マラソン(#7): SRM457 (きのうの欠席回)

過去問マラソン | 20:31 |

移動中で（というかSRMをその時間にやるのを知らずにその時間に移動してて）参加できなかったのでPractice Roomにて...

Easy(250): TheTriangleBothDivs

• 表示されうる文字列パターンは24x60x19通りなので全部試すよ
• 215.87pt = 11'40'' 遅い...
• passed system test

#define rep(var,n)  for(int var=0;var<(n);var++)

class TheTriangleBothDivs {
  string disp;
  
 public:
  string tostr(int m){
    char buf[6];
    sprintf(buf, "%02d:%02d", m/60, m%60);
    return buf;
  }
  bool possible(string s){
    rep(i,11){
      if(disp[i]=='?') continue;
      if(disp[i]!=s[i]) return false;
    }
    return true;
  }
  
  string fix(string time) {
    disp = time;

    char buf[12];
    priority_queue<int> pq;
    for(int z=-9;z<=9;z++){
      for(int h=0;h<24;h++){
        for(int m=0;m<60;m++){
          sprintf(buf,"%02d:%02d GMT%c%d",h,m, z>=0?'+':'-', abs(z));
          if (possible(buf)) {
            int t=((h-z)*60 + m + 1440)%1440;
            pq.push(-t);
          }
        }
      }
    }

    return tostr(-pq.top());
  }
};

Medium(500): TheHexagonsDivOne

• パターン数え上げ
  • 2nで%n比較、ではなく、n個の数字でそれぞれにchiralityのようなものがあると考えて
  • 隣り合っていなければ、（chiralityの異なる）同じ数字を２回使ってもよい
  • とすると、７つの枠のなかに０ペア、１ペア、２ペア、３ペアの可能性
  • それぞれのパターンをカウント
    • sample caseが通れば（あとlong long的な問題がなければ）大丈夫な気が
• 181.86pt = 74'56'' 間に合ってない...
• passed system test

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

class TheHexagonsDivOne {
 public:
  long long count(int n) {
    if (n*2 < 7) return 0LL; // 7枠あるのです.

    ll N=n; // (ll)nみたいにキャストして使うのめんどくさいから
    ll cnt=0LL;

// BEGIN CUT HERE
    // 0組 z+ 123456
// END CUT HERE
    if (n>=7) { // z, a,b,c,d,e,f
      ll p = N * (N-1) * (N-2) * (N-3) * (N-4) * (N-5) * (N-6);
      ll mag = 2*2*2*2*2*2*2; // z,a,b,c,d,e,f
      cnt += p*mag/6;
    }

// BEGIN CUT HERE
    // 1組 z+ 1.1..., 1..1..
// END CUT HERE
    if (n>=6) { // z, 1, a,b,c,d
      ll p = N * (N-1) * (N-2) * (N-3) * (N-4) * (N-5);
      ll mag = 2*2*2*2*2; // z,a,b,c,d
      ll pat = 2 + 1;
      cnt += p*mag*pat; // 1
    }

// BEGIN CUT HERE
    // 2組 z+ 1212..
    //        121.2.  // 121..2
    //        12.21. 1.12.2 (=21.12.)
    //         [13][24] [31][42]
    //        12.12. // 12.1.2(=212.1.=121.2.)
    //         1[24] 3[42]
    //        //1.212.(=121.2.) //1.21.2(=21.21.)
// END CUT HERE
    if (n>=5) { // z, 1,2, a,b
      ll p = N * (N-1) * (N-2) * (N-3) * (N-4);
      ll mag = 2*2*2;
      ll pat = 2*2 + 2*2 + 1*2 + 1*2;
      cnt += p*mag*pat; // 1,2
    }

// BEGIN CUT HERE
    // 3組 z + 121323, 131232, 123132 (132123), 123123, 132132, x
// END CUT HERE
    if (n>=4) { // z, 1,2,3
      ll p = N * (N-1) * (N-2) * (N-3);
      ll mag = 2;
      ll pat = 2*2*2 + 2*2*2 + 2*2*2 + 1*2*2 + 1*2*2;
      cnt += p*mag*pat/6;
    }

    return cnt;
  }
};

cafelierさんのを見たら、パターンを頭つかって考えるのは良くないなあと思い書き直してみた。

#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()

long long c(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1LL;
  if (r > n-r) r = n-r;
  return c(n-1,r-1) * n / r;
}

class TheHexagonsDivOne {
  // 最小要素が[0]に来るようにvecを左にローテート
  vector<int> shift(vector<int> vec){
    vector<int> res(sz(vec));
    int at = min_element(all(vec)) - vec.begin();
    rep(i,6) res[i] = vec[(at+i)%6];
    return res;
  }

 public:
  long long count(int n) {
    if (n<4) return 0LL;
    ll N=(ll)n;

    ll cnt=0LL;

    // 3 pairs
    if (N >= 4) {
      vector<int> iota(6); iota[0]=-3, iota[1]=-2, iota[2]=-1, iota[3]=1, iota[4]=2, iota[5]=3; // 空き位置なし
      sort(all(iota));
      set<vector<int> > pats;
      do {
        rep(i,6) if (abs(iota[i%6])==abs(iota[(i+1)%6])) goto next3;
        pats.insert( shift(iota) );
     next3:;
      } while (next_permutation(all(iota)));

      cnt += c(N,4) * c(4,1)*2 * pats.size();
      // c(N,4): N個の数から4つを選ぶ
      // c(4,1)*2: 4つのうち１つを中心に。左右あり
      // pats.size(): 残り3つの全順列
    }

    // 2 pairs (z, 1,1,2,2,a,b)
    if (N >= 5) {
      vector<int> iota(6); iota[0]=-2, iota[1]=-1, iota[2]=1, iota[3]=2, iota[4]=0, iota[5]=0; // 空き位置2つ
      sort(all(iota));
      set<vector<int> > pats;
      do {
        rep(i,6) { if (!iota[i]) continue; if (abs(iota[i%6])==abs(iota[(i+1)%6])) goto next2; }
        pats.insert( shift(iota) );
     next2:;
      } while (next_permutation(all(iota)));

      cnt += c(N,5) * c(5,1)*2 * c(4,1)*2 * c(3,1)*2 * pats.size();
      // c(N,5): N個の数から5つを選ぶ
      // c(5,1)*2: 5つのうち１つを中心に。左右あり
      // c(4,1)*2: 残り4つのうち1つを空き位置#1に。左右あり。
      // c(3,1)*2: 残り3つのうち1つを空き位置#2に。左右あり。
      // pats.size(): 残り2つの全順列。回転させて同じになるかは考慮済み。
    }

    // 1 pair (z, 1,1,a,b,c,d)
    if (N >= 6) {
      vector<int> iota(6); iota[0]=-1, iota[1]=1, iota[2]=0, iota[3]=0, iota[4]=0, iota[5]=0; // 空き位置4つ
      sort(all(iota));
      set<vector<int> > pats;
      do {
        rep(i,6) { if (!iota[i]) continue; if (abs(iota[i%6])==abs(iota[(i+1)%6])) goto next1; }
        pats.insert( shift(iota) );
     next1:;
      } while (next_permutation(all(iota)));

      cnt += c(N,6) * c(6,1)*2 * c(5,1)*2 * c(4,1)*2 * c(3,1)*2 * c(2,1)*2 * pats.size();
      // c(N,6): N個の数から6つを選ぶ
      // c(6,1)*2: 6つのうち１つを中心に。左右あり
      // c(5,1)*2: 残り5つのうち1つを空き位置#1に。左右あり。
      // c(4,1)*2: 残り4つのうち1つを空き位置#2に。左右あり。
      // c(3,1)*2: 残り3つのうち1つを空き位置#3に。左右あり。
      // c(2,1)*2: 残り2つのうち1つを空き位置#1に。左右あり。
      // pats.size(): 残り1つの全順列。回転させて同じになるかは考慮済み。
    }

    // no pairs
    if (N >= 7) {
      cnt += c(N,7) * c(7,1)*2 * c(6,1)*2 * c(5,1)*2 * c(4,1)*2 * c(3,1)*2 * c(2,1)*2 * c(1,1)*2 / 6;
      // c(N,7): N個の数から7つを選ぶ
      // c(7,1)*2: 6つのうち１つを中心に。左右あり
      // c(6,1)*2: 残り6つのうち1つを空き位置#1に。左右あり。
      // c(5,1)*2: 残り5つのうち1つを空き位置#2に。左右あり。
      // c(4,1)*2: 残り4つのうち1つを空き位置#3に。左右あり。
      // c(3,1)*2: 残り3つのうち1つを空き位置#4に。左右あり。
      // c(2,1)*2: 残り2つのうち1つを空き位置#5に。左右あり。
      // c(1,1)*2: 残り1つのうち1つを空き位置#6に。左右あり。
      // /6: 回転させて同じになるやつをまとめる
    }
    
    return cnt;
  }
};

Hard(1000): 開いてない