2017-02-10から1日間の記事一覧

yukicoder #250: atetubouのzetubou

実行時間をf(X,D)とすると f(X,D) = (X+D-1)!/(X!(D-1)!) これを普通に計算するとオーバーフローなどが面倒。 なのでとりあえず素因数分解した形で、肩の足し引きだけしておく。 素因数を1個ずつ掛けていって、tを超えないか、オーバーフローしないかをチェ…

SRM 638 DIV1 Medium: NarrowPassage2

解法は簡単だが思いつけないタイプ 解法 分割統治法、再帰 maxSizeSum=10で色々やってみる。 m = min(size), M = max(size) とする。 size = {5,2,3,4,6} のような場合 m = 2, M = 6 であり、 m+M <= maxSizeSumが成り立つので 2はどこにでもおける。 すなわ…

SRM 708 DIV2 Hard: PalindromicSubseq2

dp[i][j]:=左は文字iまで、右側はjまで見たときの偶数長(長さ0以上)の回分の個数の数(ただし1<=i<=j<=N) たとえば、文字列sが以下のような形の場合(1-indexed) abcxycba abc...ba dp[3][7] = 2^2 = 4 1<=j-i<=nを nから順に確定していけばいい。つまり dp[i]…

SRM 708 DIV1 Easy: BalancedStrings

文字列s[0]~s[N-1]の文字列の末尾に文字追加して解を構成すことを考える。ある文字列s[i]に文字を追加したときに全体で、instabilityは0~1、similarityは0~100*(N-1)増加する。このようにinstabilityの値のほうが調整がし易い。そこでまずsimilarityが小さく…