コンテスト全体の解説
by 
maspy
ヒント集
A - Inside or Outside
Hint 1
まずはコスト $2$ 以下で目標が達成できるかどうかを調べましょう．Hint 2
$M\geq 3$ ならば必ずコスト $3$ 以下で目標を達成することができます．解説 → https://atcoder.jp/contests/arc190/editorial/11720
B - L Partition
Hint 1
「レベル $k$ の L 型が置かれる」という条件よりも，「レベル $k$ 以下の L 型が置かれる」という条件の方が簡潔です．Hint 2
縦方向・横方向それぞれについて独立な数え上げ問題に分割できます．解説 → https://atcoder.jp/contests/arc190/editorial/11768
C - Basic Grid Problem with Updates
Hint 1
パスの終点が \((h,w)\) である場合の答 \(\mathrm{dp}[h][w]\) を考えるのは自然でしょう．あるマスの値が変更されると，そのマスの手前までの値は変更しないでよいですが，そのマスから先の部分の値をすべて変更する必要があります．
Hint 2
パスの始点が \((h,w)\) で終点が \((H,W)\) の場合の答 \(\mathrm{dp}_2[h][w]\) も考えます．\(\mathrm{dp}\) については変更されたマスの手前部分まで，\(\mathrm{dp}_2\) については変更されたマスから先の部分を保持することを考えましょう．
D - Matrix Pow Sum
Hint 1
行列の \(0\) をそれぞれ適当な不定元に置き換えたうえで \(p\) 乗することを考えます．例えば入力例 1 であれば
\[\begin{pmatrix}x_{11}&1\\\ x_{21}&2\end{pmatrix}^3=\begin{pmatrix}x_{11}^3+2x_{11}x_{21}+2x_{21}&x_{11}^2+2x_{11}+x_{21}+4\\\ x_{11}^2x_{21}+x_{21}^2+2x_{11}x_{21}+4x_{21}&x_{11}x_{21}+4x_{21}+8\end{pmatrix}\]
のようになります．
Hint 2
ある項について各不定元を \(1,2,\ldots,p-1\) に置き換えて和をとった場合，\(0\) でない和が出てくるのは各不定元についての指数が \(p-1\) の場合に限られます．
Hint 3
実装によっては \(p=2,3\) の場合がコーナーケースになるので注意してください．
E - Gaps of 1 or 2
Hint 1
この問題はグラフの最大マッチング問題として定式化可能です．
Hint 2
Tutte-Berge formula を使うことを考えましょう．
Hint 3
max-plus semiring 上でベクトルに行列をかける形の dp により解が計算できます．したがってセグメント木に行列をのせることで区間クエリに対応できます．
投稿日時:
最終更新: