TCO10 R3 の成績・ソース (要ログイン) : WA/WA/- : 完 全 敗 北
500開く
- 『王子様がN人います。それぞれ(px[i],py[i])にいて、(dx[i],dy[i])に行きたいのです。王子様は他の王子様を自分のいる場所に呼び寄せる魔法のテレポーテーションカードが何度でもいつでも使えます。（ただし、同じ一瞬には世界で一枚しかこのカードは使えません一瞬でもずれていれば複数枚使えます）。全員が目的地に着くまでの時間を最短化？』
- とりあえず「最大値の最小化→二分探索」テンプレを発動させて考えてみる
- 二分探索の初期値… 0-ε分では不可能。下限は0
- 全員直接向かっても √2 * 10000 時間あれば着ける。上限は20000くらいにしておこう
- という範囲から、時刻 T を二分探索して、T で全員目的地に行ける？行けない？を探索する
- 目的地d[i]から半径Tの円を描いてみて…
- この範囲に入れれば、到着できる。
- d[i] の近くに p[i] さんが p[i] さんは到着できることは確実なんだけど
- テレポートしまくれるから、p[i] さんでなくて p[k] さんがその範囲にいて、適当なタイミングで p[i]さんを召還してくれれば、それでも行ける
- テレポするタイミングって考える必要あるのかな…
- しばらく自分の目的地とは遠ざかる方向に走って他の人を助けてから戻るとか
- ううーむ無さそうな気もするけどちょっとわからん
- 逆に、d[i] の半径T近傍に誰もいなければ、どれだけテレポートを駆使してもその範囲に行けないので、無理。
- やっぱりテレポは最初の一瞬だけしか使わない気がするなあ。
- そういうことにしよう。
- すると、d[i] -- p[k] が距離 T 以内にあるペアが行けるペアなので、ここにうまく配置できるかどうか判定を考えればいい。
- 二部グラフのマッチングか！
- ↑の二部グラフで最大マッチングが N か判定するお仕事
- できた
- あれ？答えサンプルと全然合わない
- あー、そうか、p[k] が複数の目的地にとってベストポジションだったら何人も集まってここから出発していいので
- 最大マッチングじゃないや。一つの頂点から何本辺がでてもいいので。
- すると…？
- あれ、単にすべての d[i] から距離 T 以内に p[?] がどれか一個あればOK？
- つまり距離の最小値が T 以下ならOK か
- これ二分探索とか要らなかったなー。まあいいや速度は十分だし
- 書いた
- あれ？まだ１個だけ答えサンプルと合わない
- 合わないサンプルを見てみる
- 集合として {d[0],...,d[N-1]} = {p[0],...,p[N-1]}
- だからさっきのアルゴリズムだと 0 秒で全員行けることになるけど、
- こう、たとえば目的地が{A,B}で現在地が{B,A}だとすると
- Aに要る王子様がもう一方を召還すると、その時点で{A,A}になっちゃってBに行けなくなるし、
- 逆に{B,B}にするとAに行けなくなるし
- つまり、そうか、「同じ瞬間に同時発動できない」という制約はこういうことか。
- 一気にみんなでテレポ使うとしても、一人だけは移動できずに元の場所から走らないといけない
- なるほどなー
- で、どうするんだこれ。
- 一人テレポできないので、F さんができない人と仮定して、
- それでT秒でいけるかどうかチェック
- F が 0～N のどれか一つででも全員到着できたら勝ち
- 本当かこれ
- ううむ
- ううむ
- 自信ないけどサンプル通るし時間なくなってきたし、出しちゃおう
250開く
- 瞬殺されてる
- 『エラトステネスのふるいをmaxNumまでやります。最後に消される数字はどれですか』
- テストケース作成
- 小さい方4,5,6と
- 大きい方20億と、20億未満の最大の素数でも入れておくか
- えーと素直にエラトステネスを実装すると…20億は無理ですね
- 消えるのは合成数
- 素因数が大きいほど遅くに消える
- てことは、√maxNum 以下の最大素数の平方あたりが最後ではないか
- 書いてみた
- √maxNum 以下、とりあえず10万以下のエラトステネスを普通に書いて素数リスト作成しつつ…
- 全然合わない
- maxNum=100 で 91 らしい。7×13。
- そりゃそうだ。7×7 より大きい。
- むむう。
- 最後に消えるのが√maxNum 以下の最大素数(Pとしよう)の倍数であることは間違いない
- のうち、maxNum以下で最大のもの
- P × (P以上の素数)
- でループしてみて、maxNum を超えない限り大きくしていけばいのでは
- しかしこれは、「答えは必ず素数2個の積で書ける合成数である」と仮定していることになるなあ。
- 本当かな…
- とりあえず書いてみたらサンプルと答えは合った
- ううむ3個以上の積の場合…
- といっても、それがあるとするとP×(P以上の数全部素因数分解してみてP未満で割りきれないもの)
- とか書かなくちゃいけなくて、素因数分解のコスト掛け算すると最悪 O(maxNum) になったりしちゃいそうな…
- うむむわからんし3個以上要る場合思いつかないし
- 500を落とすつもりで考えると、今submitして250の点数だけだと200位とかだし
- そろそろsubmitしないと150位入れない。出すならもう出さないと意味ない。
- えお、みんな瞬殺で解いてるからそんな複雑にはならないに違いない！出しちゃえ！
1000開く
- 問題文みじかっ
- 『アルファベットと数字からなるN文字のパスワードで、最低U文字大文字が、L文字小文字が、D文字数字が入っているものの総数』
- mod 1000000009 で
- 0≦U,L,D≦N≦10万
- あれ、なんとかなりそうに見える…
- けどスコアボード見てもまだ誰も解いてない。難しいのかな。
- 式でとりあえず書いてみると
- Σ_{l≧L,u≧U,d≧D, l+d+u=N} C(N,l)・C(N-l,u)・26^l・26^u・10^d
- ちょっとよくわからないが
- N≦10万ということは、一個くらい固定して、残りをO(1)かO(log N)で計算できれば十分なのでは
- 数字の個数dを先に固定すると
- Σ_{D≦d≦N-U-L} C(N,d)・10^d f(N-d)
- where f(N') = Σ_{l≧L,u≧U, l+u=N'} C(N',l)・26^l・26^u
- 26^{l+u} は 26^N' だからくくりだせるか
- Σ_{D≦d≦N-U-L} C(N,d)・10^d・26^{N-d} f(N-d)
- where f(N') = Σ_{l≧L,u≧U, l+u=N'} C(N',l)
- ほら簡単になった。
- 要は Σ_{l≧L,u≧U, l+u=N'} C(N',l) これさえ高速に求まればいい
- LとUの制限がなければ2^N'なんだけどなー。左右切り落とすとどうなる…
- いやちょっとその前に
- この計算をO(N)回するんだけどこれ、それぞれO(1)でできるか？
- ベキ乗はO(log N)のオーダでできるとして、C(N,d) って毎回定義式どおり計算するとO(N)時間かかるよね
- ううむ
- メモ化しても再利用するわけでなし
- パスカルの三角形も10万まで計算は無理か
- あ、
- いや、
- これ単純なループなので、求めるべきものは C(N,D),C(N,D+1),C(N,D+2),...
- で、C(N,D)は普通に求めるとして、C(N,D+1) は、C(N,D)から掛け算１回割り算１回で求まる
- だから、ループの度に更新していけば平均コストはO(1)だ。
- よし
- f(N')=Σ_{l≧L,u≧U, l+u=N'} C(N',l)
- すなわち Σ_{L≦l≦N'-U} C(N',l)
- に戻る。これもだから、lとl+1の場合で使う C(n,k) は掛け算１回割り算１回で更新できる程度しか変わらないのを利用して、最初だけ定義通り計算してあとはインクリメントにどうにかすればどうにかなりそう…
- ええと f(N') は普通に計算するとして、そこから f(N'-1) をインクリメンタルに求めるには
- パスカルの三角形を考えると、だいたい
- f(N'-1)*2 + C(N'-1,L-1) + C(N'+1,N'-U+1) = f(N')
- こんな感じに、2倍して端っこだけ足してやれば次になる感じなので
- この端っこの C をインクリメンタルに求めていけばよくて、これは掛け算割り算で定数オーダで管理できる
- OK!
- そして最初のf(N') は普通に計算…あれ？
- これ全部普通にやったらO(N^2)かかるのでは
- あーこの中のC(N',l)もやっぱり少しずつけいさんしていけば、頑張るのはC(N',L)だけでいいや
- あるいは、N'を試す順を逆にして、L=N'-U になるところからループすれば…と思ったけどこれはDが小さいとそんな状態がないから駄目か
撃墜タイム
- 部屋の250が凄い勢いで落とされていく
- うわあこれは絶対やっぱり3個以上の積が正解になるケースがあるんだ…orz
- 撃墜して回ってる人のソース開いてみる
- if(maxNum==8)return 8; みたいなコードが
- おお、8の場合2*2*2の8が最後に消える！確かに！！！
- あ、自分のも落とされた。はいはい。
- しかしまだ間に合う、乗るしかない、この撃墜ビッグウェーブに。
- 500の自分の点数280点くらいあるから、撃墜多少失敗してもこれがあってれば150位には残れるはず
- 逆にこれが落ちてたらもう無理だし、あってると仮定してガンガンチャレンジしてみよう
- 適当に開く
- よし、なんか素数二個の積しか試してないっぽいコードが！
- 8 ！
- あれ？チャレンジ失敗…？？
- うおお、この人、上の方で素数リストを作るためのエラトステネスと見せかけて、10万くらいまでは実際にエラトステネスで最後に消えた数字を覚えておいてそれ返してる！賢い！
感想
- というわけで初のネガティブスコアでした
- 反省点はなんだろう
- 250だなー。
- 「小さいケースでナイーブな解法と完全に一致する」は確かめておくべきだった
- 特に今回はエラトステネスまで書いてるんだから、ほとんどノーコストでsmall用の解が作れるのに…
- 普通に素因数分解的なことして十分間に合うじゃないですかー
class SieveOfEratosthenes { public:
vector<int> eratos(int M)
{
vector<bool> isComposite(M+1);
vector<int> ps;
for(int p=2; p<=M; ++p)
if( !isComposite[p] )
{
ps.push_back(p);
for(LL q=LL(p)*p; q<=M; q+=p)
isComposite[q] = true;
}
return ps;
}
int minFactor(int N, const vector<int>& ps)
{
for(int i=0; i<ps.size(); ++i)
if( N % ps[i] == 0 )
return ps[i];
return INT_MAX;
}
int lastScratch(int maxNum)
{
vector<int> ps = eratos(int(sqrt(double(maxNum))));
int P = ps.back();
int M = P*P;
for(int Q=P+1; P*Q<=maxNum; ++Q)
if( minFactor(Q,ps) >= P )
M = P*Q;
return M;
}
};
- Pから2Pの間には別の素数があるので
- Q はたかだか4Pまで考えればよくて
- minFactorは…大きい素数の掛け算でできてる値の時しか時間かからないので、まあ大丈夫なのか
- Pがせいぜい5万弱で
- Pまでの素数は5000個とかで
- なので最悪でも3*5万*5000だし、明らかにほとんどの場合5000もかからないし
- 1/2 は 1イテレーションで終わる
- (1-1/2)*1/3=1/6 は 2イテレーションで終わる
- (1-1/2-1/6)*1/5=1/15 は 3イテレーションで終わる
- (1-...-1/15)*1/7=4/105 は 4
- 残り 8/35
- 思いっきり大目に見て残り平均2000回かかるとしても 1/2 + 2/6 + 3/15 + 16/105 + 8/35 2000≒500とかだし実際はもっと少ないだろう
- これは十分間に合うなあ
- なんで本番で見積もれなかったんだろう…
- 8以外の場合は2個でいいのは
- p*q*r (p<q<r) は q*q より前に消される</li>
- p*q*q (p<q) は q*q より前に消される</li>
- p*p*q (p<q) は、pの次の素数 < p*p, q なので (pの次の素数)*(pの次の素数) より早く消される</li>
- p*p*p は… (pの次の素数)*(pの次の素数) と、2**3 vs 3**2 のところだけ逆転している！
- こうか。ふむふむ
- 方針はあってた
- UTPCのときに、C(n,k)の計算はfactorialの値をメモしておけば定数回のmod演算で済む、とlaycurseさんがおっしゃっていたのを今更ながらに思い出した。
- そうだそうだ。
- なので、変にインクリメンタルに計算するのはΣC(n',u)の部分だけでいい
static const int MODVAL = 1000000009;
struct mint
{
int val;
mint():val(0){}
mint(int x):val(x%MODVAL) {}
mint(LL x):val(x%MODVAL) {}
};
mint operator+(mint x, mint y) { return x.val+y.val; }
mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
mint POW(mint x, int e) {
mint v = 1;
for(;e;x=x*x,e>>=1)
if(e&1)
v=v*x;
return v;
}
mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }
vector<mint> FAC_(1,1);
void FAC_INIT(int n) { for(int i=1; i<=n; ++i) FAC_.push_back( FAC_.back()*i ); }
mint FAC(mint x) { return FAC_[x.val]; }
mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
class Passwords { public:
int countValid(int N, int L, int U, int D)
{
FAC_INIT(200000);
mint answer=0, f=C(U+L,U);
for(int d=N-U-L; d>=D; --d)
{
answer = answer + C(N,d)*POW(10,d)*POW(26,N-d)*f;
f = f*2 + C(N-d,U-1) + C(N-d, N-d-L+1);
}
return answer.val;
}
};
- ついでに、今までADDとかMULとか名前付き関数で書いていたmod演算を全部演算子オーバーロードしてみた
- こっちの方がうっかりミスしやすいこともあるのでどっちがいいか微妙だけども
- まあ見やすくてよい
class TheChroniclesOfAmber { public:
double minimumTime(vector <int> princeX, vector <int> princeY, vector <int> destinationX, vector <int> destinationY)
{
int N = princeX.size();
vector< vector<double> > d(N, vector<double>(N));
for(int s=0; s<N; ++s)
for(int g=0; g<N; ++g)
d[s][g] = hypot(princeX[s]-destinationX[g], princeY[s]-destinationY[g]);
double noTelepo = 0;
for(int i=0; i<N; ++i)
noTelepo = max(noTelepo, d[i][i]);
double answer = noTelepo;
for(int unused_s=0; unused_s<N; ++unused_s) {
double withTelepo = 0;
for(int g=0; g<N; ++g) {
double t = 1e+300;
for(int s=0; s<N; ++s) if( s != unused_s )
t = min(t, d[s][g]);
withTelepo = max(withTelepo, t);
}
answer = min(answer, withTelepo);
}
return answer;
}
};
- 瞬間移動は、やるとしたら最初の一瞬のみ
- (直感的には自明な気がするんだけど証明できてない)
- 瞬間移動を使う場合
- 元々王子様がいた場所N箇所のうち、どこか一カ所には誰もいない状態になる
- 逆に、「どこか一カ所には誰もいない状態」は全てどの状態であっても作れる
- (証明できてない)
- この仮定の下で、「誰もいない初期位置」をどこにするかN通り全探索して、あとは全員目的地に一番近いところに飛んでいくとすれば最小の答えが出る
- 『「どこか一カ所には誰もいない状態」は全てどの状態であっても作れる』
- 作りにくい状態というのは [A] [B] [C] を [C] [A] [B] のようにサイクル状にぐるっと回すときだけなので
- ひとり犠牲者のDさんを連れてくれば
- [A][B][CD]
- [CA][B][D]
- [C][AB][D]
- [C][A][BD]
- のように所望の移動ができるので、
- あとは、こういうサイクルが何個あってもこのDさんを市中引きずり回しの系にして他全員動かしてから、最後にDさんが行きたいところに飛べばいい
- 誰をDさんにするかは
- 一カ所は初期位置を空けるので、鳩ノ巣原理により全テレポート完了後はどっかに二人重なる
- その重なるところに行く人を犠牲者にすれば「最後に行きたいところに飛べばいい」が可能になるので、
- このプランは可能
