SRM484 の成績・ソース (要ログイン) : AC/-/- : どうも不要に苦手意識持ちすぎです
250開く
- 250, 550, 950 の変則セットだったので警戒して550回避
- 『Rabbit』『Taro』『Hanako』ぎゃあ出た！全く心構えが出来ていないぞ…
- 『S(n)を10進表記でnの各桁を足した値としたとき、S(n*n)=S(n)*S(n)になる数は区間[low,high]に何個あるか』
- 考える前にまずは low, high が小さい場合の全探索を書いておこう
- for(int n=low; n<=high; ++n) if(isRabbit(n)) ...
- できた。100万くらいで動かしてみる。
- よし、サンプルとは合ってる。理解は間違ってないようだ。
- 具体的に条件を満たす n を表示させてみる
- うーむ規則性よくわからない
- けど、条件を満たす数はそんなに多くはないっぽい
- てことは、なにか探索範囲をうまく狭めれば、十分小さい範囲に全部が入る、とか。
- 問題文にでてきた値のとれる範囲を考える。
- n : 1 から 10億。でかい。
- S(n) : せいぜい10桁の数の桁の和だから、90以下。
- S(n*n) : せいぜい20桁だから、180以下。
- いやちょっと待て、180以下の値全部を取り得るかというと…
- 平方数である、という条件があるから、1,4,9,16,...,169 のどれかでしかあり得ない！
- ということは、S(n)は 1,2,3,...,13 のどれか！
- これだ！
- 「桁の和が13以下の10桁以下の自然数nを全探索」
- は、ええとなんかこういう、"13+10 個のものが一列に並んでいるのから10個選んで仕切りとするパターン数" みたいなヤツで、
- 大雑把に数えても 2^23 よりは圧倒的に少なそうだし余裕でしょう
- で条件を満たす数の表を作っておいて、あとは数えるだけ…
- 書き書き
- isRabbit判定はさっきのを使い回せるので、small用コードの8割ぐらい再利用できてる。なんとなく得した気分。
- できた
- あってるっぽい。
- [1,10億] のケースを、念のため、S(n)≦13 を S(n)≦15 に変えて全探索しても答えかわらない
- じゃあ大丈夫かな
- ≦15でもtime limit十分間に合うから、念のため15のままでsubmitしちゃおう！
550開く
- 『普通のぷよぷよは6列ですが、1列です。4色あります。L個くっつくと消えます。N個振ってきた時に全消し状態になっているような配ぷよは何通り？ mod 10億7で。』
- テストケース作成：(2,2)と(2,4)がサンプルにあったので、(2,1)と(10,1000)を足してみた
- そういや、N は L の倍数じゃないと自明に 0 か
- この入力サイズは、O(L N^2) くらいが目標か…
- 1列にぷよが並ぶのは、{a,b,c,d}の4種類の文字が並ぶ文字列に見える…
- 「全消しになる配ぷよ」の文法（L=4 の場合）
A ::=
""
| A "a" A "a" A "a" A "a" A
| A "b" A "b" A "b" A "b" A
| A "c" A "c" A "c" A "c" A
| A "d" A "d" A "d" A "d" A
- こんなんかな。
- これにマッチする長さNの文字列の個数…
- 普通にCYK法っぽいDPをやるとO(N^3)だよなあ
| A "a" A "a" A "a" A "a" A
- ここの A では、端っこに "a" がくると前の "a" とくっついて勝手に消えちゃって、意図したパターンと違う物をカウントしてしまう。
| A "a" (端がaじゃないA) "a" (端がaじゃないA) "a" (端がaじゃないA) "a" A
- とする必要がある。まあ記号の数が増えるけど、これでも文脈自由文法で書けることに違いはない…
- えーと、数を数えるには、
- 長さ n でAにマッチにする文字列の個数 = Σ_i
- 「長さiでAにマッチする個数」*「長さn-iでaAaAaAaAに」
- +「長さiでAにマッチする個数」*「長さn-iでbAbAbAbAに」
- + ...
- とかいう漸化式で。DP。
- 文法の各部分式について、「長さnでマッチする個数」を求める。
- で、それぞれは左右に分割するやり方を掛け算してΣなので、O(n)で小問題の解から求まる
- O(n^2)
- これでいいかな？
- ある！
- aaaabbbbcccc を (aaaabbbb)(cccc) と (aaaa)(bbbbcccc) の二通りで数えてる！
- うーむ、文法とか考えると曖昧な文法では個数数えにくいから
- 考え直すべきかなあ。
- 普通に真っ正直にDPをそのまま考える…
- 「長さ0の列から始めて、"最後に消える組" aaaa をどこかに挿入、を繰り返す」
- という入れ方を数える
- 途中状態でどこに入れられるかというと、
- えー、どこ？
- 周囲と同じ色だと予定外にくっつくから、xxxxyyyy だったら
- _x_x_x_x~y_y_y_y_
- の _ には3通りの色が入れられて~には2通りの色が
- つまり長さと変わり目の個数で決まる
- 挿入後は長さは += L で、変わり目の個数は
- むむむ長さと変わり目の個数だけからは決まらなくないか（※決まります）
- これはちょっと難しいなあ
- いや
- AaAaAaAaA みたいに両側Aじゃなくて
- 「全体を通して最後には全消しになるけど最後にしか全消しにならない配ぷよ列 U」みたいなもので定義すれば
- 考え直し
A ::= U*
U ::= aAaAaAa | bAbAbAbA | ...
- こうだ。正確には勿論さっきと同じで「端がaじゃない」を考慮しないといけないけど
A[端!a] ::= "" | U[端!a] A[右端!a]
A[右端!a] ::= "" | U[端!a] | U A[右端!a]
- みたいな感じかな（※間違い）
- A[端!a]::=U[端!a] U U U ... U U U U[端!a]
- こういう気分
- …？
- あ、掛け算じゃなくて足し算してる…
- 修正。単純なサンプルは合った。でもまだ合わないのが２つ。
- …？
- わからない…方針は合ってると思うんだけど…（時間切れ）
撃墜タイム
- 550, 950 はACRushの提出のみ。
- 250もTLEしそうな人はいない
- することがない
感想
- 自分では特に手間取ったつもりはなかったんだけど、
- 他の人と比較して250が遅すぎる。ちょっとスピード上げることを意識しないと。
- だいたいあってた。
- A[端!a]::=U[端!a] U U U ... U U U U[端!a]
- これが間違いで
- こうすべきだった。でないと結局aがくっついて消えちゃう
- 自分で "端" とかいう微妙な概念を作ってしまってセルフメダパニしてしまった
static const LL MODVAL = 1000000007;
class PuyoPuyo { public:
int theCount(int L, int N)
{
vector<LL> A4(N+1), A3(N+1);
vector< vector<LL> > U(L, vector<LL>(N+1));
A4[0] = A3[0] = U[L-1][1] = 1;
for(int n=1; n<=N; ++n) {
for(int k=L-2; k>=0; --k)
for(int z=0; n-z-1>=1; z+=L)
U[k][n] = (U[k][n] + A3[z]*U[k+1][n-z-1]) % MODVAL;
for(int i=L; i<=n; i+=L)
A4[n] = (A4[n] + 4*U[0][i]*A4[n-i]) % MODVAL;
for(int i=L; i<=n; i+=L)
A3[n] = (A3[n] + 3*U[0][i]*A3[n-i]) % MODVAL;
}
return int(A4[N]);
}
};
文脈自由文法を定義する。簡単のためL=3、ぷよはabcの3色という例で。
- A =「全消しできる配ぷよ列」
- U =「最初のぷよが最後まで残るけど結局全消しできる配ぷよ列」
A ::= U*
U ::= a A[端!a] a A[端!a] a | b A[端!b] b A[端!b] b | c A[端!c] c A[端!c] c
A[端!a] ::= U[端!a]*
A[端!b] ::= U[端!b]*
A[端!c] ::= U[端!c]*
U[端!a] ::= b A[端!b] b A[端!b] b | c A[端!c] c A[端!c] c
U[端!b] ::= a A[端!c] a A[端!c] a | a A[端!a] a A[端!a] a
U[端!c] ::= c A[端!a] c A[端!a] c | b A[端!b] b A[端!b] b
これにマッチする長さNの文字列の個数、が求める物。
