Hatena::Grouptopcoder

hirosegolf@競技プログラミング

2012-01-23

SRM530

| 17:50

250: Opened

500: x

900: Opened

悲惨な感じの結果になった。500は気付けば非常にシンプルな解法があるタイプの問題だった。探索範囲が大きすぎて無理っぽい問題は、まずこのタイプを疑うべきかも知れない。900は全く解法が思いつかなかった。Editorial見たら普通だったけど、dpdpする量のおき方が本当に難しい。

2011-10-13

SRM521

| 21:53

  • 結果

o--

246.07

1000を解けなかったのが悔しい。500は解けそうに無かった。

左から順に見ていって "(" が足りなくなったら、追加する。最後に足りない ")"を追加する。

  • 500

分からない。難しい。

  • 1000

漸化式を立てて行列を求めればいい。行列の立て方に慣れてなくて手間取ってしまった。結局時間オーバーしてしまった。行列を立てるうまい方法を思いついたので、次回からは似たような問題はすぐ解けるはず。行列の積もテンプレ化したほうがいいかも。

  • ソースコード

250


class MissingParentheses {
public:
  int countCorrections(string par) {
    int ans=0;
    int t=0;
    REP(i,par.size()){
      if(par[i]=='(')t++;
      else t--;
      if(t==-1){
        ans++;
        t++;
      }
    }
    return ans+t;
  }

1000

void mult(vvl &a, int i,int j, ll v){
  REP(k,a.size()){
    a[i][k]+=v*a[j][k];
  }
}

void fus(vvl &a){
  mult(a,1,0,1);
  mult(a,2,1,2);
  mult(a,3,1,2);
  mult(a,4,2,2);
  mult(a,4,3,1);
  mult(a,5,2,1);
  mult(a,6,5,1);
  mult(a,6,4,1);
  mult(a,7,6,2);
  mult(a,8,7,1);
}

ll mod=1000000007;

vvl mul(vvl a, vvl b){
  //debug(a[0][4]);
  //debug(b[4][0]);
  int k=a.size();
  vvl ret;
  ret.resize(k);
  REP(i,k)ret[i].resize(k);
  REP(i,k) REP(j,k) REP(l,k) ret[i][j]=(ret[i][j]+a[i][l]*b[l][j])%mod;
  return ret;
}

vvl powm(vvl s, vvl t, ll n){
  //debug(t[4][0]);
  if(n==0)return t;
  if(n%2==0)return powm(mul(s,s), t, n/2);
  else return powm(mul(s,s), mul(s,t), n/2);
}

int comp(ll n){
  vvl a,b;
  int k=10;
  a.resize(k);
  b.resize(k);
  REP(i,k)a[i].resize(k);
  REP(i,k)b[i].resize(k);
  a[0][4]=4;
  a[1][6]=2;
  a[2][7]=1;
  a[5][8]=1;
  vvl xx;
  xx.resize(k);
  REP(i,k)xx[i].resize(k);
  xx[0][0]=1;
  fus(xx);
  fus(a);
  //REP(i,k) REP(j,k) printf("%d %d %I64d\n", i, j, a[i][j]);
  //REP(i,k)printf("%I64d\n", xx[i][0]);
  //debug(xx[4][0]);
  vvl ret=powm(a,xx,n);
  return (int)(ret[0][0]);

}

class Chimney {
public:
  int countWays(long long n) {
    int ans=comp(n);
    return ans;
  }