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\)の個数が全て一致することと同…