2020-12-14から1日間の記事一覧

nCr メモ化再帰(DP)バージョン

大抵nCrを求める時はmodをとったものを返すが、以下の問題は違った (ABC 300点) C - Duodecim Ferra https://atcoder.jp/contests/abc185/tasks/abc185_c パスカルの三角形を上に登っていく再帰でnCrを求めればoverflowに怖がらずに済む AC https://atcoder.…

K番目の数は何か?(N=10^5, 作られる数字はO(N^2))個...の解き方

(自分で検索する時用の記事です) 下記の700点問題が典型っぽい L - をあ ぷろぶれむ https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_l この問題名で検索して出るアルメリアさんのBlogを読めばいい ポイント:二分探索・単調性・セグメ…