SRM440 の成績・ソース (要ログイン) : AC/AC/- : もう少し500を素早く片付けてれば1000に挑めた気がする…
500開く
- 『どの２点を結ぶ経路もちょうど１通りになっているような迷路をランダムな始点からランダムウォークしてゴールマスにつくまでの経過時間の期待値』
- 期待値は、
- ゴールマスは常に e=0 で、
- たとえば隣が１マスしかなくてそのマスの期待値がe0ならe=e0+1で、
- 隣が２マスで期待値がe0,e1ならe=0.5*(e0+e1)+1で…
- という連立方程式の解だ。
- 2500変数の連立方程式…
- それは愚直に解こうとすると時間間に合わないなあ。
- なんかO(n^2)で解けるような特殊形の式になってたりは…
- うーんわからん。
- 各マスごとの期待値ではなくて全部の平均が求めるものなので、実は総和だけ考えると１変数の式に落ちたり
- 迷路がツリー状になっているという条件は重要な気がする
- 隣が１マスしかないところの制約 e = e0+1 を隣のマスの制約式に代入して…
- を繰り返すと O(n) 回の代入で全部解ける、よね
- 式のまま代入ってめんどいなあ。
- 具体例で *.. で考える。それぞれ期待値は e,f,g
- f=0.5(e+g)+1 に g=f+1 を入れると f=e+3。
- 具体例で *..\nX.X で考える。それぞれ期待値は e,f,g,h
- f=1/3(e+g+h)+1 に g=f+1 と h=f+1 を入れると f=e+5。
- なんだか、期待値 = 親の期待値 + 子の数*2 + 1 になっているような予感
- とりあえず組んでしまえ！
- 組んだ
- 最初の方のサンプルは通る。複雑なやつは通らない。
- ...
- ツリーが２段以上になっている場合におかしいような…
- *..... で考える。
- 式を手で解きまくる…
- 期待値 = 親の期待値 + 子孫の数*2 + 1 になっているような予感
- とりあえず組んでしまえ！！！
- 組んだ
- 複雑なやつも通った！
- 全然正しさ確認してないけど、この最後のサンプルくらい複雑なの通れば十分でしょー。
- えいsubmit。
- 念のためコーナーケーステスト。
- * １マスだけとか、壁だらけでやっぱり結果的に * 1マスだけのを幾つか。
250開く
- スコアボード、部屋のも全体のを見ても、みなすごい苦戦している(200点前後)。これはじっくり落ち着いて構えよう。
- 『与えられたstrictly下り坂の折れ線の上をT秒でボールが転がり落ちました。重力加速度はいくつでしょう。1e-9精度で答えてね』
- 折れ線は100折れまで。座標も100まで。T=100。
- 解析的に一発で解けそうな気もするけど２次方程式とかそういったものがめんどい
- 重力加速度の二分探索でOK。
- 初期値いくつからはじめればいいだろ？
- (0,1)-(100,0) を 1秒で落とす場合がたぶん一番重力加速度でかいから、適当にみつもっても2万+αが最大。
- 念のため g_left=0 と g_right=1e+9 から二分探索。
- まああとは地道に重力加速度g=(g_left+g_right)/2の元でかかる時間を計算して、
- Tより大きいか小さいかでg_leftかg_rightを更新、というコードを書く…
- 結局二次方程式の解を求めるはめに…
- 書けた。
- 全部答えが NaN になる → yが減少列なのを忘れててsinが負になってた
- 全部答えが 1e+9 になる → 左と右の更新する側間違えた
- 通った。submit。
1000開く
- 『[2,N]の数の[2,K]要素の集合でperfect square freeなものの個数をmod 100..007で。』
- p.s.f というのは、要素全部の積がp^2の形の約数を持たないもの
- N,K≦500
- 要は互いに素（かつ１個１個の要素そのものがp.s.f）な部分集合の個数を数える。
- mod なんとかってことは全探索は無理でDP的に数えるしかない。
- 互いに素、という制約は…
- 共通因数を持たないというわけで、
- clique…じゃなくて安定集合の数を数える感じ？グラフ？
- いや、500までということはsqrt(500)までの素数だけ考えれば良くて
- 2,3,5,7,11,13,17,19 の8個考えればいいのでは。
- for n in [2,N] で新しく入れるnの入れ方を数えていくDPなら 500*500*256くらいで終わるような
- 500*500*256 ってどうだろ。6000万？軽くやばい気がするけど残り時間ほとんどないしこれで組んでみる
- …
- 時間切れ
撃墜タイム
- 二分探索の範囲が小さい人が絶対いるはずと思って、{0,100},{1,0},1 を用意してスタンバイ
- 自分のコード曰く20000強の値なので20000より小さい範囲しか調べてない人をターゲットに
- ２人撃墜
感想
- 撃墜タイム中に、加速度と経過時間の2乗が比例関係だよね、と１発で解いてる人がいてなるほどと感心。なるほど。
- 1000は上に書いた方針はかなり怪しい気がするけどどんなもんかなー。あとで考える。
- 同じ部屋のsystem test結果見てたら、二分探索で right-left < 1e-12 を終了条件にしている人２人が解が20000越えるやつでfailしてた。
- 12*log_2(10) + log_2(20000) ≒ 12*3.3 + 15 + α ≒ 55 ＞ 53。おお。
- なんとなくいつも log_10(2)=0.3、log_2(10)=3 で見積もってたけど今度から3.3で見積もってみるか
だいたいあってた
static const int MODVAL = 1000000007;
bool is_square_free(int n)
{
for(int p=2; p*p<=n; ++p)
if( n%(p*p) == 0 )
return false;
return true;
}
static const int SP[] = {2,3,5,7,11,13,17,19};
static const int SPN = sizeof(SP)/sizeof(*SP);
int small_prime_mask(int n)
{
int m = 0;
for(int i=0; i<SPN; ++i)
if( n%SP[i] == 0 )
m |= 1<<i;
return m;
}
int big_prime_factor(int n)
{
for(int i=0; i<SPN; ++i)
while( n%SP[i] == 0 )
n /= SP[i];
return n;
}
class SquareFreeSets {
public:
int countPerfect(int N, int K)
{
int way[501][1<<SPN] = {};
way[0][0] = 1;
for(int n=2; n<=N; ++n)
if( is_square_free(n) )
if( big_prime_factor(n) == 1 )
{
int mask = small_prime_mask(n);
for(int k=K; k>=1; --k)
for(int m=0; m<(1<<SPN); ++m)
if( (m|mask) == m )
way[k][m] = (way[k][m] + way[k-1][m&~mask]) % MODVAL;
}
else if( big_prime_factor(n) == n )
{
vector<int> mask;
for(int p=1; n*p<=N; ++p)
if( is_square_free(p) )
mask.push_back( small_prime_mask(p) );
for(int k=K; k>=1; --k)
for(int m=0; m<(1<<SPN); ++m)
for(int j=0; j<mask.size(); ++j)
if( (m|mask[j]) == m )
way[k][m] = (way[k][m] + way[k-1][m&~mask[j]]) % MODVAL;
}
int sum = 0;
for(int k=1; k<=K; ++k)
for(int m=0; m<(1<<SPN); ++m)
sum = (sum + way[k][m]) % MODVAL;
return sum;
}
};
ただし19＜sqrt(500)までの使用済みフラグを持っているだけではそのままではダメで（たとえば23と46が同時に入れられないという条件が抜けてしまう）、23を入れるときに同時に46,69,...を入れるパターンも試してみることで19より大きい共通素因数は省く方針で。もう少し整理すると綺麗になるかも…。
