問題リンク 問題概要 回にわたって整数 が与えられる。 を満たす整数 の組で、Euclid の互除法を走らせた時の反復回数の最大値と、それを導く組の個数を求めよ。 解法 まず、最大値を求めることを考える。回数ごとに組の最小値を貪欲に考えていくと、フィボ…
問題リンク 解説 求めるべき長方形がどのような形をしているか考えてみます。 題意より、求める長方形は3頂点が異なる色で、残りの1頂点は残りのどれかと同じ色です。 このような長方形には、3頂点が異なる色になるL字型の部分が必ず2つ含まれています。 よ…
問題リンク 解説 それぞれのジャンルごとに売る冊数を決めたとき、ジャンルごとの価格の最大値は明らかです。価格の高いものから貪欲に売るのが明らかに最適であるからです。 これを先に求めれば、ジャンルごとに売る冊数を適切に決めるだけで価格の最大値が…
問題リンク 解説 動的計画法を適切に高速化する問題です。 を、 番目の階段に来る方法の総数とします。 を求めるとき、どこの階段からここまで上ってこられるかを考える。これは、尺取り法や二分探索を使えば高速に求められます。 そのような段のうち最も低…
問題リンク 解説 初歩的な動的計画法の問題です。 を、 行目かつ 列目のマスにいる状態とし、残り2つの添字で「どちらの方向から来たか、次に曲がれるか」を保持します。 この動的計画法を と の昇順で回すことで解けます。 このように、典型的な動的計画法…
問題リンク 典型寄せ集めみたいな問題 解説 まず、道の本数が高々 本なので、作れる道を列挙できれば、クラスカル法で空港の数と道のコストの組を計算できる。 空港の建設コストは会社ごとに異なるので、これを変数だと考えると、上に挙げた組は一次関数にな…
Li Chao Tree を書いた. 一次関数 の追加と, での取る値の最小値の取得が、取得したい点の集合のサイズを としてそれぞれ になるデータ構造. 使い道 最適化DPの遷移でこういう式が出てくることがあって, これで高速化ができることがある. JOI で出ることもあ…
問題リンク 解法 重要な考察がいくつかある すべてのテストの重要度は のどちらかである。これは、 どんな場合でも損失を最小化/得を最大化するのはこの2つの値のどちらかになるからである。 時間勉強するとき、その内訳は、重要度が で 時間勉強する教科、…
問題リンク 解法 先頭に追加していって辞書順最小を目指すので、操作を後ろから考える。 数列のうち、使っていない数でできた連続区間の長さがすべて偶数となるように、同じ連続区間からふたつの数を取っていけばよいということがわかる。 問題は、1個目に取…
問題リンク 解法 前からDPしていく. 2以上の要素が2連続するとそこから先はすべて埋まり、そうでない場合1を置くか、2以上の要素を置いた後十分になるまで1で埋めるしかない。 これを考えると、 を、「 要素目以降がまだ決定していない場合の数」としてDPが…
online-judge-tools と atcoder-cli, verification-helper を導入した 導入方法 npmとpipにあるので普通にインストールする online-judge-toolsとatcoder-cliはこれで普通に使える verification-helperは, githubAPIキーを取得して, リポジトリでSECRETの変…
数え上げは言い換えの質 問題リンク 解法 0の前の1の数を並べて数列に変換する。 みたいな感じ この数列と文字列は一対一対応をもち、この数列を , もとの文字列の0の数を とすると、操作は なる を選び、] に 加え、] から 減じる、と言い換えられる。 この…
問題リンク 解説 要素が複数あるクエリ問はとりあえず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…
