mayoko’s diary

プロコンとかいろいろ。

2015-09-27から1日間の記事一覧

AtCoder Regular Contest 023 D - GCD区間

問題 arc023.contest.atcoder.jp 解法 まず少し考察です。区間 [s, t] にある最大公約数は, s が t から 0 に動くにつれて単調減少します。そして, その最大公約数の減少の仕方は, 素因数が 少しずつ減少していくことで生じます(例えば 6 -> 3 -> 1 と最大公…

AtCoder Beginner Contest 005 D - おいしいたこ焼きの焼き方

かみぺさんがまとめていたので解いてみることにしました。 良問,教育的問題リスト - Google スプレッドシート 問題 abc005.contest.atcoder.jp 解法 各クエリごとに計算するのではなく, データが与えられた時点で計算して, 各クエリには前計算した値でその…

SRM 656 div2 hard:PermutationCountsDiv2

SRM 656 に参加した時 med で同じ解法を使ったんですが, いい復習になりました。 問題 TopCoder Statistics - Problem Statement 解法 包除原理を使います。例えば, N 個のうち, 2 つだけ p[k] 「区切りごとに p[k] ① 1 つ目の区切りまで単調減少, 1 つ目の…