アルゴリズム・数学 slope trick (2) 問題編
以下の、解説編を読んでいることを仮定とします。使う記号などは共通で、改めて説明していません。
前 → (1) 解説編
ABC 127 Absolute minima
解説編で述べたものをそのまま実装すれば...
maspy
アルゴリズム・数学 アルゴリズム・数学 slope trick (1) 解説編
続き → (2) 問題編
ネタバレに配慮して、これが使える問題をまとめたものは、別記事 (2) 扱いとしています。
実装をしている具体的なコードについても、必要であれば (2) 問題編 における解答例を確認してください。
...
AtCoder [ARC] Paper Cutting 2 (ARC 114 [E])
概要
問題文 → ■公式解説 → ■自分の提出 → 本番 ■, コンテスト後 ■
本番、計算式を間違えていて 1 時間消し飛んで、間に合わなくなってしまった。悲しい。
公式解説と違っていて、また同方針で解こうとしている方も居るよう...
AtCoder [ARC] Sequence Scores (ARC 114 [C])
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説と少し違う感じがしたので書いておきます。
最適な操作回数を理解する
数列を、ヒストグラムにより可視化します。$x$ 座標、$y$ 座標が定義できます。例え...
AtCoder [JAG] Permutation Period（jag2017summer-day3 [K]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
シンプルな問題で、問題設定自体は自分でも考えたことがありました（この制約で解ける問題だとは思っていなかったです）。出題されて改めて考えてみると、上手く解けました。
...
AtCoder [JAG] 夕食（jag2014summer-day4 [D]）
概要
問題文 → ■作問者解説？ → ■ 自分の提出 → ■
公式解説がなさそうだったので書いておきます。→ 作問者解説が見つかったのでリンクしました。
愚直解法を数式にして、それを元に考察するのが最近の好みです。
$O(N...
AtCoder 整数をつくろう！（pakencamp 2018 day3 [H]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
Heuristic contest タイプの問題です。
現時点（2021/02/25）で、1 位のスコアが出ています。しかも、（解説 PDF と比べても）かなり少ない実装量で...
AtCoder コインの取り合い（dwango 2015 本選 [D]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
たぶん最終的なアルゴリズムは一緒ですが、思考過程は割と違いそうなので、書いてみます。愚直解法を作ってから、漸化式を観察することで高速な解法を探ります。
$O(NQ)$ ...
AtCoder [TTPC] 多項式の零点の個数（TTPC2019 [L]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
これリアルタイム参加したコンテストなんですが、当時は解法は分かっても構文解析書けないと思って取り組みませんでした。同じ解法をとった人、結構多いっぽいですが、「別解」だったみた...
AtCoder LCP(prefix, suffix)（みんなのプロコン 2018 決勝 [D]）
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説の手法が派手でびっくりしました。
かなり簡単に解けるので、書いておきます。
解法
問題文で与えられる数列を逆順に並べたものを $A$ とすると、問題は次のように言...