問題リンク 解説 要素が複数あるクエリ問はとりあえず1要素ソートするのが基本。 たぶんどっちをソートしても解けるが、今回は直径を降順ソートした。 クエリとマトリョーシカの追加を合わせてソートすれば、直径についての条件を考える必要はなくなる。 次…

だるかったので高速化したら通った 問題リンク 解法 とりあえず交点を求めてダイクストラしたいおきもちになるが、めんどくさいので愚直なダイクストラを書いてみる。 路線と場所ごとに距離を持たなければいけないが、これは unordered_map を使うのが最適（…

この問題好き。面白かった。 問題リンク 問題概要 文字列 と整数 がある。 の好きな位置に好きな英小文字を 回挿入してできる文字列の通り数を で求めよ。 解説 とおく。 結果の文字列を前から決めていくことを考えると、 を、「 文字目までで、 回小文字の…

問題リンク 解説 問題の要旨を見ればわかると思いますが、すべての注文について、「どの店が一番注文先に近いか」を求めることができればよいです。 円環なので少し実装が煩雑になりますが、これは店の位置をソートして二分探索してやればよいです。 ここか…

問題リンク 解説 動的計画法の問題です。 たとえば、 を 日目に、前日店 で買い物をし、そこでは 日連続で買い物をしている、という場合の最小の合計金額とすると、 で解くことができます。 このように、最終的な最適解が、条件を絞れば途中まででも必ず最適…

問題リンク 解説 蟻本にもほぼ同じ問題が載っていることで有名です。 解法の説明はおそらくそちらの方が詳しいので、そちらを参照していただければ良いと思います。 2本の矢を投げて作れる点数を で列挙しソートしたあとに、それらを探索しながら「和が を超…

問題リンク 解説 問題文中にもあるように、 が小さいことを利用します。 まず、行の裏返し方を全探索した上で、列の裏返し方を考えます。 行の裏返し方が決まっていれば、各列について、裏返すべきかそうでないかは一意に定まります。表になるおせんべいが多…

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

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

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

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

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

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

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

Segtree Beats を書いた。 仕組みや計算量について話そうと思う。 仕組み 普通の Segment Tree を使うと、chmin クエリなどでは、総和の効率的な更新が不可能である。（それはそう） ここで、特殊な場合だけ更新が可能になるのでその場合になるまで下に辿っ…

雑なライブラリを切り貼りする生活だったので書いといた。 非再帰・std::function排除なので定数倍は軽め…なはず？ あと、std::functionを排除すると、外でラップしないと使えない。（ので、典型的なクエリはすでにクラスにしてある。） 区間変更が必要なけ…

問題リンク 問題概要 長さ の文字列に対して、 文字選んで 0 にする、 文字選んで 1 にするという操作を好きなだけ行って生成できる文字列の個数を求めよ。 考察 10秒くらい考えると、 文字選ぶ、というのは 文字以上選ぶ、というふうに言い換えられる。 で…

Project Eulerの解説をひたすら書き綴ります。 すべてに共通することがら プログラムしたいときはPythonを使うと楽です。 オーバーフローの心配がないのが大きなメリットでしょうか。 最初の方もはや解答と感想になってるんですけどごめんなさい。 1 Multipl…