アルゴリズム・数学 slope trick (3) slope trick の凸共役
slope trick (1) 解説編
slope trick (2) 問題編
概要
凸関数の凸共役（Legendre-Fenchel 変換）とその性質について、軽くまとめます。さらに、slope trick による...
maspy
アルゴリズム・数学 問題解説 [yukicoder] No.1216 灯籠流し/Lanterns
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説よりも計算量が良いので、書いておきます。
解法
消灯への対応
$v$ を出発した灯籠が、$w$ から先では消灯しているとします。このとき、
$v$ か...
問題解説 [yukicoder] No.1763 Many Balls
概要
問題文 → ■公式解説 → ■自分の提出 → ■
割と素直な解法だと思いますが、少し公式解説と違うのかな？大差での Fastest AC にもなったので、書いておきます。
解法 $p = 90001$ とします。$K = 60...
問題解説 [yukicoder] No.1379 Postponed
概要
問題文 → ■公式解説 → ■自分の提出 → ■
公式解説では、最小値の挙動に注目しています。私は最大値の挙動に注目して解いたので、解説しておきます。
私の解説では、$A_i+1$ のことを改めて $A_i$ と呼ぶこと...
AtCoder [AtCoder] ジャッジが壊れている問題
ジャッジがこわれていて AC 不可能
（特殊ジャッジ） （特殊ジャッジ） （誤差ジャッジ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （インタラクティブ） （特殊...
問題解説 [yukicoder] No.1353 Limited Sequence
概要
問題文 → ■公式解説 → ■自分の提出 → ■
想定解法よりも計算量が落ちたようなので、一応書いておきます。$O(R\log R)$ 時間で解けます。
解法
$a$ を $1$ 個以上 $k=A_a$ 個以下並べ...
形式的べき級数解説 [多項式・形式的べき級数] （補足）定義や式変形の正当性の確認
この記事は、形式的べき級数の厳密な定義や、その正当性に疑問を感じた場合に見ることを想定しています。次の記事との関係については、どちらが先でも構いません。より手短に面白い所を勉強したり、問題解決に役立てたい場合には、先に（１）（２）（３）な...
アルゴリズム・数学 Stirling 数を $p$ で割った余りの計算
概要
下降冪 $(x)_n$、符号つき第 1 種 Stirling 数 $s(n,k)$、第 2 種 Stirling 数 $S(n,k)$ を次で定義します：
$(x)_n = \prod_{0\leq i < n} ...
問題解説 [yukicoder] No.1292 パタパタ三角形
概要
問題文 → ■公式解説 → ■自分の提出 → ■
Fastest AC 記念
解法
まず、正三角形を次のように座標空間内に配置します： $A(1,0,0), B(0,1,0), C(0,0,1)$.
$A$...
AtCoder 天下一折れ線遊戯（天下一プログラマーコンテスト2013 決勝 [E]）
概要
問題文 → ■公式解説 → あるのか不明自分の提出 → ■
解法
LGV 公式を使います。
参考：ABC 216 H 解説（）
可能な線分すべてを考えてしまうと、線分に交差が生じる場合があります（サンプル 3...