問題リンク 問題概要 回にわたって整数 が与えられる。 を満たす整数 の組で、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の数を とすると、操作は なる を選び、] に 加え、] から 減じる、と言い換えられる。 この…