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

AGC020 C - Median Sum

問題 C - Median Sum 解法 解説の通り。空でない部分列の数は 個存在するが、部分列の和が x となるような部分列の構成方法の数え上げは動的計画法で で求まる。だが、これでは間に合わない。中央値は配列の合計の 1/2 以上になるということに気づくと、部分…

みんなのプロコン2018 決勝 A- Uncommon

問題 https://beta.atcoder.jp/contests/yahoo-procon2018-final/tasks/yahoo_procon2018_final_a 解法 ある整数 i について配列内の i と互いに素な整数の数を数えるのは大変そうなので、i と互いに素でない数を数えることにする。i を素因数分解し、例えば…