解説することはあんまりないです． 問題リンク？ B - 古本屋 (Books) 解法 各ジャンルについて， 個売るときの買取価格の最大値は貪欲法で求まります．したがって， を(既に0冊以上売却したジャンルの集合が ，売却した総冊数が のときの買取価格の最大値)と…

急に思いついたので実装してみたらなんか速かった。 アイデア 集合の要素数の最大値が高々 であるとして, 個の集合 を次のようなルールにしたがって管理することを考えます。 各 の要素数は高々 である。 かつ なら である。 かつ なら である。 このとき、…

Merge Sort Tree というデータ構造があります。 要素の 静的な列 に対し、次のようなクエリを処理できます。 が与えられるので、 に含まれる 以下の値の総和を求めよ。 atcoder.jp 以下の総和なので、ソートされていれば累積和+二分探索で 時間で求められま…

毎日自分のレート+400以上のdiffの問題を解きます。 問題リンク F - Silver Fox vs Monster 解法 座標順にソートした後、単純に前から順に「 が負ならcontinue, 正なら座標が から の間にあるモンスターの体力に 以上の最小の の倍数を引く」という操作を行…

毎日自分のレート+400以上のdiffの問題を解きます。 問題リンク C - AtCoDeer and Election Report 解法 投票数が満たすべき条件は 「広義単調増加」 かつ 「比が 」 したがってi回目での投票数は 「 回目の投票数以上の最小の の倍数 」 「 回目の投票数以…

毎日自分のレート+400以上のdiffの問題を解きます。 問題リンク D - joisino's travel 解法 という制約からワーシャルフロイド法 が見えてくる。町を訪れる順番は順列全探索で 、順番が決まれば移動距離の総和は で求められるので、合計で となりAC。 Submis…

問題リンク C - Tsundoku 解法 答えを二分探索する。 「 冊読めるか」の判定は、事前に累積和を取り「机Aの本を 冊読むための所要時間」(Bも同様)を求めれば、机Aで 冊、机Bで 冊読むとしてそれぞれの所要時間の和が以下かどうか判定すれば良い。 判定は で…

問題リンク F - Double Sum 解法 問題の式を次のように変形する。 したがって、 各に対し, かつをみたすについて, (の総和) - (の個数) を求め、その総和を取ればよいことが分かる。 これはをからの順に考えると、 より大きい要素の総和を管理するsegment tr…