cafelier@SRM

SRM444

SRM | 22:13 |

SRM444 の成績・ソース (要ログイン) : AC/AC/- : ちょっと考えすぎた

500開く

• 『最大10x25のマス目が与えられる1x1の点数1のブロックと4x4の点数16のブロックで敷き詰めて点数最大化してね。ただし最初から何個か1x1が置いてあるよ』

• なんか前も似たようなのなかったっけ。
  • 左上から置いてって点数はともかくそのまま敷き詰められるかどうかだけ判定してとか…
  • 違うそれは辞書順最小の敷き詰め方とかそういう問題だ

• てゆーか、左上から見てって4x4をおけるところはGreedyに置いていいのでは
  • 4x4を置かないで1個右に4x4をつかう"144\n144"なら"441\n441"も同じだし、みたいに
  • "1...\n....\n..11" でダメだなー。こういうナナメにかぶる時にまずい
    • サンプルにこういう例はないぞ！
    • 撃墜例候補。保存。

• 要は、最終的なスコアは4x4を置く個数の関数なわけで、それを増やせば良くて…
  • ここに4x4を置いたらこっちにおけない、みたいな依存関係でグラフを作る
  • それは最大独立点集合問題だ！NP完全NP完全

• つーか普通にDPでは
  • 左から埋めてって、「x行目まで埋めたときの、x行目の埋まり具合がmaskというパターンのときの、残り部分で得られる最適スコア」みたいなのを覚えておく。maskは1<<10通りなので(1<<10)*25*各行の埋め方パターン数
  • くらいの時間で終わる
  • 埋め方パターン数は多く見積もって1<<10通り…よりはまあだいぶ少ないでしょう。たぶん動く。

• けど実装面倒くさそう
• やっぱりなんかGreedyっぽく綺麗な解法無いか。
• 無い
• 無いね

• 実装した
• サンプル通った
• 念のため最大の10x25のケースも入れてみる。問題ない。サブミット。

250開く

• スコア見ると結構みんな手間取ってるな
• 『またマス目問題です。今度は最大50x50。白か、黒か、左上が白右下が黒の三角、で塗り分けられてます。最大unfoldLimit箇所の三角を黒に変えてもいいので、できるだけ大きな黒い三角形をつくってね』
  • よこに■が出っ張ってるような図形の一部分を▲と主張するのは認められない。ちゃんと綺麗に▲にすること。

• えーなんだこれ。
  • 2500カ所くらい塗り替えができるので、全通り試すとかは無理

• えーと、作る形は直角二等辺三角形しかないので、
  • 右上の座標(2500通り)と、縦横のサイズ(50通り)を決めれば、そこでunfoldLimit以下で▲を作れるかは判定できる
  • これを全通り数えて一番大きかったやつを返す
  • 作れるのか判定は…三角形のまわりに変なのがくっついてないかと、中身がちゃんと黒埋めできるかだから…50^2？

• 全部で50^5かー間に合うかなあ。怖いなあ。
• 判定を多少インクリメンタルにして50^4にした。
• サンプル通った。50*50でも問題ない。サブミット。

1000開く

• 『n≦4e10ケタ以下の自然数で、"10進表記したときに4が4個以上並んでない" ＆ "44桁,444桁,444...444桁のような4ゾロ目ケタでない" 数の個数は。mod 1000000007で』

• えーと行列のべき乗するだけではなかろうか。
• （k桁の数で最後の4の並びが0個1個2個3個のものの数）から（k+1桁の数で同左）は4x4の行列を掛ければ求まる
• なのでn桁の場合もそれのn乗で。
• その行列をAとして、A^0 + A^1 + ... A^n (※ただし4ゾロ目以外に限る) な和を計算してから1桁の場合 (8 1 0 0) を掛けて和をとれば

• 行列の等比数列の和ってどうなるんだったか。
• 普通の等比数列との類推で (1-A)^-1(1-A^n) にならないですかね
  • なることにしよう
  • そういうプログラム書いた
  • しかし逆行列求めるライブラリって作ってないなー。
  • あと5分…
  • そうだ手で逆行列求めよう
  • 時間切れ

撃墜タイム

• 500をgreedyにやってる人が絶対いると思ったのにいなかった
• 250を5乗でやってる人を撃墜したくなったけど、手元で5乗のループ動かしてみたら余裕だった。やめやめ

感想

• 44, 444, 444...444 の"倍数"桁のもいけないのか。それはもう何回りか面倒だなあ。
• やっぱり1000は解けてない。だめだー
• 逆行列なんて要らないなあ。1個要素ふやして1 1 1 1で足し込んでいくだけだ。次はこういうの解くぞー

SRM444 1000

あとで | 23:05 |

大筋ではあってた。ひたすら行列のべき乗。

static const LL MODVAL = 1000000007;
typedef vector< vector<LL> > matrix;

vector<LL> vMul( const matrix& A, const vector<LL>& B )
{
  const int n = A.size();

  vector<LL> C(n);
  for(int i=0; i<n; ++i)
    for(int j=0; j<n; ++j)
      C[i] = (C[i] + A[i][j] * B[j]) % MODVAL;
  return C;
}

matrix mMul( const matrix& A, const matrix& B )
{
  const int n = A.size();

  matrix C(n, vector<LL>(n));
  for(int i=0; i<n; ++i)
    for(int j=0; j<n; ++j) {
      LL Cij = 0;
      for(int k=0; k<n; ++k)
        Cij = (Cij + A[i][k] * B[k][j]) % MODVAL;
      C[i][j] = Cij;
    }
  return C;
}

matrix mPow( matrix M, LL t ) // t>0
{
  matrix R;
  for(; t; t>>=1, M=mMul(M,M))
    if( t&1 )
      R = (R.empty() ? M : mMul(R,M));
  return R;
}

LL GCD(LL a, LL b) { while(a) swap(b%=a,a); return b; }
LL LCM(LL a, LL b) { return a/GCD(a,b)*b; }

class AvoidFour { public:
  int count(long long n) 
  {
    matrix A(6, vector<LL>(6));
    A[1][0] = 8; A[1][1] = 9; A[1][2] = 9; A[1][3] = 9; A[1][4] = 9;
    A[2][0] = 1; A[2][1] = 1;
                              A[3][2] = 1;
                                           A[4][3] = 1;
                 A[5][1] = 1; A[5][2] = 1; A[5][3] = 1; A[5][4] = 1; A[5][5] = 1;

    vector<LL> v(6);
    v[0] = 1;


    vector<LL> fours;
    for(LL f=44; f<=n; f=f*10+4)
      fours.push_back(f);
    int N = fours.size();

    LL total = 0;
    for(int m=0; m<(1<<N); ++m)
    {
      LL lcm=1, bitCnt=0;
      for(int i=0; (1<<i)<=m; ++i)
        if( m & (1<<i) ) {
          lcm = LCM(lcm, fours[i]);
          if( lcm > n )
            break;
          bitCnt ++;
        }
      if( lcm <= n ) {
        matrix Af = mPow(A, lcm);
        Af[5] = A[5];

        LL sub = vMul(mMul(A,mPow(Af,n/lcm)), v)[5];
        total = (bitCnt&1 ? total-sub+MODVAL : total+sub) % MODVAL;
      }
    }
    return total;
  }
};

初期状態(k=0桁の場合)

(1) ... k桁の自然数のうち、0桁のものの数 (k=0のときだけ1)
(0) ... k桁の自然数のうち、最後に4がゼロ連続
(0) ... k桁の自然数のうち、最後に4が1連続
(0) ... k桁の自然数のうち、最後に4が2連続
(0) ... k桁の自然数のうち、最後に4が3連続
(0) ... k桁未満の自然数のうち、4が4連続してないもの

というベクトル v に

(0 0 0 0 0 0)
(8 9 9 9 9 0)
(1 1 0 0 0 0)
(0 0 1 0 0 0)
(0 0 0 1 0 0)
(0 1 1 1 1 1)

という行列 A を左から掛けてあげると、k=1桁の場合、k=2桁の場合、...が求まっていく。左端の列がk=0→1の時に"0"を入れないための特殊処理。それ以外の時は4以外の9種類のどの数字を入れても「最後に4がゼロ連続」になるので9 9 9 9。「最後に4が1連続」になるのは「ゼロ連続」状態に4を足したとき。……という遷移行列。

• なので、44...44の倍数桁のを除く、という条件を無視すれば、答えは A^{n+1} v の最後の成分。
  • ここから44の倍数桁のものを除くには、(A^44)^{n/44+1} v の最後の成分を引いてやればよい。
  • 444の倍数桁のものを除くには、(A^444)^{n/444+1} v の最後の成分を引いてやればよい。
  • 以下同様
  • これだと44と444の公倍数を引きすぎるので、
    • (A^LCM(44,444))^{n/LCM(44,444)+1} v の分は足しておく
    • というような足したり引いたりを包除原理で調整
• n<=4e10なので、せいぜい9通りの例外ケースに対する包除原理なので2^9=512回くらい行列べき乗をやればよい。

• 6*6*2^9*log(n) くらいなので時間的には余裕