2023-01-01から1年間の記事一覧
ABC300F 解法 部分問題として,\(M=1\) のときを考える. \(s\)のうち,丁度\(k\)個の x を o に変えた後の 最大の o の長さを求める. 補助的な配列 \(a\)を用意する. 大体は,\(s\) の x の部分を \(0\) にして,o の部分を長さとする. ただし,0 が並ぶ…
ABC332C 解法 シミュレーションというか,貪欲法. 気を付けることは, 無地のシャツを買う必要はないので,足りないときは印刷されてる方だけ買う. 洗濯したら枚数を回復するので,今持っているシャツの枚数をそれぞれ記録しておく. 最後に,印刷したシャ…
ABC332D 解法 行と列の個数が\(5\)以下と少ないので全探索できる. 入れ替え全体は\(\,(5!)^{2}\,\)通り. 置換を与えたとき,互換の積で表したときの最小の個数は, 置換の転倒数と一致. これは愚直に実装でも,置換のサイズの2乗オーダーで求まる. Segtr…
ABC332E 解法 分散 \(V\) の最小化. \(V = \frac{\sum_{i \in D} (x_{i} - \overline{x})^{2} }{D}\) を最小化する.\(\overline{x}\) は,振り分け方と無関係な定数. よって, \(\,(x_{i}-\overline{x})^{2}\,\)の最小化をすれば十分. \(D,N\)が小さいの…
ABC320E 解法 シュミレーション. 時刻毎のイベントを priority queue に入れておく. 食べるイベントと,人が復帰するイベントに分ける. 注意 人が復帰するのと,食べるイベントが同時刻の場合, 人が復帰するのを先に行うので,priority queue の順序に注…
ABC327E 解法 レーティングの計算式を見ると,\(k\)を固定したときに 第一項の分母と第二項は定数. よって,第一項の分子だけ最大化すればよい. この DP は容易. 注意 普通にDPを実装すると,-inf * \(0.9^{t}\) の形を計算することになる. これだと,\(…
ABC329E 解法 操作を逆に行う. 文字列\(S\)からスタートして,\(S\)を ##...# にする. # はワイルドカードだと思ってよい. つまり,何が入っていいても良い文字と考える. \(S\)において,文字列 \(T\) を連続部分列として含むかどうかを判定して, 含む…
ABC323E 解法 問題文がおかしい? 誤解していたが,テストケースを見て読み取れた. 正しくは,\(X+0.5\)秒の時点で曲0が流れている確率. 時刻 \(y \in [0,X]\) において,\(y\) に曲が開始される確率を求めておけば十分. これは dp で求まる. 計算量は,…
ABC331E 解法0: Priority queue とソートを用いて,調べる候補を減らす. \(a\)と\(b\)を降順ソートしておけば,基本的には \(a\)と\(b\)の先頭から選んでいけばよい. 今調べている\(a\)と\(b\)のインデックスの組を \(\,(i,j)\,\) とおくと, 次に調べるべ…
ABC330E 解法 vector \(a\) に対して,\(mex(a)\) の求め方を考える. \(N := \vert a \vert\)とおく. まず, \(0 \leq mex(a) \leq N\) であることに注意する. \(a\)の元のうち,\(N\)以上の物は無視して良いことになる. \(mex(a)\)を答えるためには, \…
ABC328E 解法 BitDP による全探索. \(N = 8, M = \frac{N(N-1)}{2}\) の最大ケースで 辺の選び方は\({}_{M}C_{N-1} \leq \frac{25^7}{7!} = 1,211,015\)通り であるから間に合う. 辺の取り方を \(s \in 2^{M}\) から選べばよい. 別のbitDPとして,頂点の…
アルゴリズムと数学061 - Stone Game 2 解法 勝敗を逆算していく. 手番を持っているほうが勝ちか負けかを考える. 今の局面が勝ちか負けかを決めるとき, 遷移先に負けの局面が存在するならば,今の局面は勝ち. 遷移先が全て勝ちの局面ならば,今の局面は…
アルゴリズムと数学079 - ModSum 解法 上界を見積もる. 各\(i \in [1,N]\)に対して, \(i\)で割ったあまりは \(i-1\)以下. よって,答えは \(\sum_{i \in [1,N]} (i-1)\) 以下. 実際に,これを実現する例が存在する. 1-indexed で \(p_{i} = i+1\) とお…
アルゴリズムと数学089 - Log Inequality 2 解法 式を同値変形すると, \(a < c^{b}\). 桁あふれに注意して冪を計算する. \(a\)より大きいかだけが問題になるので, \(a\)の最大値よりも大きい値は区別する必要がないので, 気持ちとしては \(\infty\) の様…
アルゴリズムと数学094 - Maximal Value 解法 \(a_{i}\)の和の最大を求める. まず,各\(i \in N\) に対して \(a_{i}\) の最大を見積もる. \(b_{i} \geq max(a_{i}, a_{i+1}) \geq a_{i}\) かつ \(b_{i-1} \geq max(a_{i-1}, a_{i}) \geq a_{i}\) であるか…
アルゴリズムと数学057 - Domino Tiling 解法: 行列冪乗 これも遷移が線形になるので,行列冪で解ける. 状態を \(2^{K}\) で持っておき, 次数\(2^{K}\)の行列を考える. まず\(N\)が小さい場合で考えてみる. DP による全探索をすると, 左から \(i\) 列目…
アルゴリズムと数学056 - Recurrence Formula 2 解法: 行列冪乗 遷移が線形なので,行列冪により \(O(M^{3} log N)\) で求まる. ここで,\(M\)が行列の次数,\(N\) は行列冪の指数. 遷移が \[ \begin{pmatrix} a_{n} & a_{n+1} & a_{n+2} \end{pmatrix} = …
アルゴリズムと数学062 - Teleporter 解法0: 周期性を用いる \(i \rightarrow a[i]\) と遷移を繰り返すと,あるところでサイクルに入る. \(i_{0}\)からスタートするとして, \[ i_{0} \rightarrow \cdots a \rightarrow b \rightarrow \cdots \rightarrow c…
ABC324D 解法 \(N \leq 13\) より,\(N\)桁の平方数は \(10^{6.5}\) 以下なので,全探索できる. \(0\)の桁の扱いに注意. 一番上の桁に\(0\)を追加してもよいという設定. あるソートで一致することは, 各桁の\(0\)から\(9\)の個数が全て一致することと同…
ABC142F 解法 Sub 0: 有向グラフにおける,サイクルを求める. Sub 1: 有向グラフにおける,最短サイクルを求める. Sub 0: サイクルを検出するだけなら,DFS, BFS で可能. Sub 1: 最短のサイクルを求めたいので,BFS を行う. 計算量的には,始点 \(i \in …
ABC165F 解法 Sub: LIS(line 型) Main: LIS(Tree 型) Line 型の LIS が解けていれば,それを tree 型にするのは容易. DP 配列を DFS で使い和ます. 注意は,遷移から戻るときに DP 配列を元に戻すこと. 使っている記号,マクロ等 "https://ecsmtlir.haten…
ABC170F 解法 いくつか解法があるが, ダイクストラで解く. コストが \(\frac{1}{k}\) として, 向きを変えたときまたはゴールしたときに,小数点以下の切り上げをする. 少数だと扱いにくいので,コストを \(1\) にして,\(k\) の倍数に切り上げる. 使っ…
ABC173F 解法 \(0\)-indexed, 半開区間で考える. 森の誘導部分グラフは森になる. よって, グラフ \(G\) が森のとき, (\(G\)の connected component の個数) = \(|V(G)| - |E(G)|\) となる. 頂点集合が区間 \([l,r)\) となる \(G\) の誘導部分グラフの …
ABC184F 解法 半分全列挙. \(a\) を半分に分けて,それぞれの和を集めておき, その vector を \(v_{0}, v_{1}\) とする. \(x \in v_{0}\) を全探索して, \(y \in v_{1}\) を,\(x + y \leq t\) となるもののうち 最大となる様にとる. これは,前処理で …
ABC192F 簡単な問題から考える. 取り方 \(s \in 2^{N}\) を固定 \(t := sum(s)\) とおく. \(s\) に対する答えは, \(x-t \equiv 0 \ mod \ |s|\) のとき \(\frac{x-t}{|s|}\) となる. それ以外のときは不可能. 取った個数 \(k \in [1,N]\) を固定 これも…
ABC306F \(\def\cnt #1{\lvert {#1} \rvert}\) 解法 \(A,B\) を集合,\(A \cap B = \emptyset\) とする. 集合 \(C\) に対して,\(x\) 以下の元全体を \(C^{\leq x}\) とおく. \begin{align} f_{A,B} &= \sum_{x \in A} \cnt{A \cup B}^{\leq x} \\ &= \sum…
ABC276F 部分問題 \(a\) を size \(N\) の vector, \(i \in N\) とする. \(a_{[0,i)}\) において, \(a_{i}\) 未満の個数と \(a_{i}\) 以上の和が分かれば十分. これらは segtree で実装可能. 使っている記号,マクロ等 "https://ecsmtlir.hatenablog.co…
ABC275F 解法 \(a_{i}\) を残すとき 0, 消すとき 1 として,01 列を考える. 1 が連続している区間の個数を最小化する問題となる. 区間を数える代わりに,[01] の並びを数えると考えるとよい. [11], [00], [10] は数えないとする. つまり,01 列において …
ABC309F 解法 平面走査. 2次元 segtree は,1次元を 2方向にとる. まず回転が 6通りあるが,これは直方体のどの面を一番下にするかが 6通りあって, それらに 1対1 対応する. つまり,回転するということは,自由に辺の長さを並び変えることに対応する. …
ABC271F 解法 半分全列挙. 最短ルートで移動したとき,右上から左下の対角線 \(l\) を一度だけ通る. \(l\) で正方形を 2分割して,それぞれで計算した結果をつなげる. 左上から \(l\) への移動方法は,雑に見積もって \(2^{n}\)通り. 点 \(\,(x,y\,)\) …