ferinの競プロ帳

競プロについてのメモ

2018-10-09から1日間の記事一覧

AGC009 C - Division into Two

問題ページ 考えたこと 集合を2分割する系なのでDPを考える 集合に入っている要素のうち一番大きい要素が大事 集合が空のときを考えるのは面倒なのでX,Yには-infが入っているものとしておく dp[i][j] = (集合にs[i]まで挿入していて、Yに最後に入れた要素がs…

AGC006 C - Rabbit Exercise

問題ページ 解説を読んだ。 解法 数式で扱いやすい形に変形 公式解説にある通り対称な位置の計算、位置の期待値の計算を扱いやすい形(置換)に変形する。 置換をダブリングで高速に計算 K回置換を計算するのは二分累乗、ダブリングの要領で高速にできる。置換…