kaage精進録

雑な解説とかライブラリとかおきもちの垂れ流しです。

2020-06-19から1日間の記事一覧

2020JOI二次予選2 いちご 解説

問題リンク 解説 難易度5の中では考察寄りな問題です。 結論から言うと、「座標と熟すまでの時間の和の最大値」と、「座標の最大値の2倍」のうち大きいほうが答えになります。 以下に証明を示します。このような問題の証明を考えるのは、より難しい問題を解…

2019JOI本選1 勇者ビ太郎 解説

問題リンク 解説 累積和の典型的な問題です。 まず、宝石の位置を固定すると解きやすくなる、というのは感覚的に明らかでしょう。オーブと金塊のあるべき位置の条件が定まるからです。 結局、宝石を決めたとき、その右側にオーブが何個あるか、下に金塊が何…

2012JOI本選2 たのしいカードゲーム 解説

問題リンク 解説 まず、B が残すカードは、山の中の連続する部分列だということがわかる。このようなものは 個ある。 これらすべてについて、A からカードを取ることで作れるか判定すればよいが、これは となってしまい、間に合わない。 B の残すカードの列…

2012JOI予選C 最高のピザ 解説

問題リンク 解説 まず、トッピングの個数を固定することを考えます。トッピングの個数が一定なら、カロリーを高いものから貪欲に選んでいくのが当然最適です。 そこで、トッピングの個数を決め打ちして最大の1ドルあたりのカロリー数を計算し、最大のものを…

2011JOI本選1 惑星探査 解説

問題リンク 解説 調べなければいけない長方形が多いので、それぞれの長方形について高速にクエリを処理する必要があります。 これは、二次元累積和を使って、それぞれの種類のブロックが、1頂点を左上の端などに固定した長方形 通りの中にいくつかあるかを高…

2010JOI本選1 旅人 解説

問題リンク 解説 愚直にシミュレーションすることを考えると、時間計算量は になって、間に合いません。 毎日の移動で、区間の和をひとつずつ足して計算するのは無駄なので、累積和を使って高速化すると、計算量を にすることができます。 また、毎日の移動…

AtCoder でも colun 法を

AtCoder でも colun 法が使えたというだけの話。 colun 法とは およそ6年前のこと。 TopCoder SRM 620 Div1 Easy で、再帰の引数を増やしすぎるとスタックオーバーフローする問題が出たらしい。 これを、「自分で確保したヒープ領域に rsp ポインタを移動さ…