問題はこちら No.457 (^^*) - yukicoder ・O(|S|^3) 各カッコ対に対して、その間に'^^*'があるかどうか判定する 当然TLE・O(|S|^2) 各'('について、そこから右に見て'^^*'があった以降にある')'の数を数える (*^^)も同様 17/01/31修正 char s[10010];i,j,L,R…

問題はこちら No.456 Millions of Submits! - yukicoderいろいろな知見が得られた見出し ・愚直二分探索（TLE） ・W関数を使う二分探索 ・ニュートン法（賢い） ・W関数をなんか凄い方法で求める a,bの一方が0のときは自明。そうでないとする とおく b≠0の仮…

問題はこちら No.454 逆2乗和 - yukicoder実験しながら適当に投げたら通ってしまった愚直でいけたり？→n=10^9近くまで計算しないとダメっぽい n=10^7くらいまでで様子見→サンプルに関しては10^-7を足せばちょうどいい感じ じゃあとりあえずそれを投げてみる→…

問題はこちら No.117 組み合わせの数 - yukicoder素直に階乗で計算するだけ C(N,K)はによる単純なループによりO(K)で計算できるけど、KTが大きいのでこれではTLEになる なので、事前に階乗を計算しておけば、各クエリは定数時間で答えられるP:=10^9+7は素数…

問題はこちら No.453 製薬会社 - yukicoder線形計画法とか知らないけど数学で殴るだけ製品Aをxkg、製品Bをykgつくるとすると、問題は 3/4*x+2/7*y≦C 1/4*x+5/7*y≦D x,y≧0 の条件下で1000*x+2000*yを最大化する問題 厳密な証明を書くのが面倒くさくなったので…

問題はこちら No.429 CupShuffle - yukicoder上下からシミュレーションするだけ 上から順に??の直前までやり、下から順に??の直前までやれば、その前後で変化している場所が答えだとわかる #define swap(x,y)(t=x,x=y,y=t) int main(){ int a[100010],b[1000…

問題はこちら No.446 ゆきこーだーの雨と雪 (1) - yukicoder0～12345のいずれかと文字列として一致しているかどうかを調べるだけ c++ならto_string関数なるものがあるらしいが、cにはない 文字列を数値にするならatoiという関数があるのでitoaとかないのかと…

問題はこちら No.445 得点 - yukicoder定義式に従って実装するだけ…… と思わせて、小数で誤差が発生する場合がある（challengeケースを参照） そういうわけで、小数を使わないように、式をちょっと変形する int main(){ int n,k; scanf("%d%d",&n,&k); print…

問題はこちら No.442 和と積 - yukicoderA*Bが64bitに収まらないので、多倍長を持ち出すか、なんか考えないといけない D=gcd(A,B)とし、A=Da、B=Dbとする。ここでa,bは互いに素となる。 gcd(A+B,AB)=gcd(D(a+b),DDab)=D*gcd(a+b,Dab) であり、a,bが互いに素…

問題はこちら No.450 ベー君のシャトルラン - yukicoder２台の電車がすれ違うまでの時間をTとする。 ベー君は速度wで時間Tだけ移動するので総移動距離は明らかにwT。 T=d/(vl+vr)であることから直ちに計算できる。 int main(){ double vl,vr,d,w; scanf("%lf…

問題はこちら No.441 和か積 - yukicoder場合分けをすれば簡単に分かる。 必要ならAとBを入れ替えることでA≦Bと仮定して良い ・Aが0のとき Bも0なら'E'、さもなくば'S' ・Aが1のとき 必ず'S' ・Aが2のとき Bも2なら'E'、さもなくば'P' ・Aが3以上のとき 必ず…