2023-01-01から1年間の記事一覧
ABC189F 漸化式を立てると,一見循環してしまう. これを式変形して循環しない形にして計算する. 振り出しに戻るものが厄介. そのときの答えを \(x\) とおいて, \(x\) に関する 1次式とみなす. \(dp_{i} := i\) に居るときの答え(期待値) とする. \(x =…
ABC313 ABC313 参加. 水色 になって嬉しい!! まぐれでなく,レーティングをあげるために対策をした結果なので, その取り組みも含めて満足した. 具体的には,水色問題の復習をメインにした. 新しく学ぶよりは,すでに解き方を知っている物を, 速く正確に…
ABC188F 操作の逆を考える. \(f(y) := y / 2 \ (\text{if}\ y \equiv 0 \ mod \ 2)\), \(g_{+}(y) := y + 1\), \(g_{-}(y) := y - 1\). これらの操作で \(Y\) から \(X\) を作ることを考える. 操作 \(f\) のおかげで,小さくしていくので計算量の見積りも…
ABC190E Tree におけるクエリ. まとめて処理することで回数を減らす,いつものやつ. Subtree に関する処理を,補題の様に扱えばよい. Subtree の root \(r\) を指定したとき,\(r\) の値を subtree 全体に伝搬させる. 使っている記号,マクロ等 "https:/…
ABC190E グラフの問題. ハミルトン閉路に近い. 大事な頂点が \(K \leq 17\) と少ない. 訪れた頂点を再び使う可能性はある. すべての大事な頂点を 1回以上使う. 訪れた頂点の集合と,最後に訪れた頂点を保持しながら dp. 大事な頂点間のコストは,BFS と…
ABC191E ダイクストラ. サイクルを含んでいるので注意. サイクルだけ別に管理してしまうと楽. 始点を \(s \in N\) とする良い path を考えると, [\(s \rightarrow s\) のループを使う path] または, [\(s \rightarrow i \rightarrow s\) かつ \(i \neq …
ABC192E コストが特殊な Dijikstra. 時刻を距離の代わりとして保持しておき, 時刻が \(k\) の倍数になるまで待機してから移動すればよい. 現時点の後ろの,一番近い \(k\) の倍数で移動するのが最善. 使っている記号,マクロ等 "https://ecsmtlir.hatenab…
ABC310F 部分和 DP. \(M := 10\) とおく. \(s \subset [0,M] \) を作れる数全体とする. 今のさいころの出目 \(x\) によって場合分け. \(x \in [1,min(a_{i}, M)]\) の場合:作れる数の集合が \(t := s \cup \{y+x \ \vert \ y \in s\}\) に変わる. \(dp_{…
ABC312F 3つタイプがあるが,いずれも貪欲に取れる. どれか一つを全探索しよう. 缶切りを使わない缶全体, 缶切りを使う缶全体, 缶切り全体 をそれぞれ \(a,b,c\) とおく. \(a,b,c\) を全てソートしておく. \(a\) を全探索する. \(i \in size(a)\) に…
ABC312E 何を全探索するかを考えるのが基本. 座標の範囲 100 と小さいので,3次元で全探索しても \(O(100^{3})\) で間に合う. よって,それを軸に考える. 座標で全探索するということは,境目になる面を全探索しているのと同じ. しかし,面を全探索する…
ABC312D DP で全探索.\(dp_{i,x} := \) \([0,i)\) まで調べ終わって,値が \(x\) の場合の数.ここで,( を +1, ) を -1 として,先頭から調べて累積和をとる. かっこ列になる必要十分条件は,常に和が 0 以上かつ,最後に和が 0になること. 遷移は,今調…
ABC172E 類題: Complete permutation\(S_{N} := N\)次対称群, \(k \in N\) に対して,部分群 \(S_{N}^{k} := \{ \sigma \ \vert \ \sigma(k) = k \}\) をとる. 求めたいのは, \(\vert S_{N} - \cup_{k \in N} S_{N}^{k} \vert = \vert S_{N} \vert - \ver…
ABC166E 相異なる \(i,j \in N\) の組を数える. これは典型で,\(i < j\) として \(j\) の方を全探索する. それにより,今 \(j\) を探索しているとき,すでに \(i < j\) については すべて調べ終わった状態になるため. abs(j-i) = a[i] + a[j] より, j-i…
ABC181E 先生の身長を固定して考えて,\(h\) に追加しておく. このとき,ペアの作り方の最適解の一つは, ソートした \(h\) に対して先頭から貪欲に 2人ずつ組んでいく方法が挙げられる. それが解ければ,あとは先生の身長を全探索すれば OK. 前もって \(h…
ABC189E アフィン変換. 実装するときは,3次元の行列にした方が簡単. 行列は class にしておいた. 操作列は行列の列に対する積をとっておけばよい. つまり累積和を求めておけば,クエリ毎に O(3^3)で答えられる. ここで,3は行列の次数. 使っている記…
ABC194E Mex を求めるアルゴリズムまずは問題を保留して,vector \(a\) が与えられたとき,\(mex(a)\) を求める手順を考える. 小さい自然数から実験してみれば,\(i \in \mathbb{N}\) に対して, \(mex(a) = i\) となるのは,任意の\(j \in i\) に対して \(…
ABC311B まず \(N = 1\) の場合を考える. vector \(v\) に対して何個 o が連続しているかは, for i in v.size() を回して,\(v[i]\) が o だったら カウント \(cnt\) を増やして,そうで無ければ \(cnt\) を 0 に戻す. \(i\) ごとに chmax(ans, cnt) を行…
ABC311C すべての頂点から \(1\) 本ずつ辺が出ているので, どの頂点から始めてもサイクルにたどり着く. サイクルの検出は,訪れた頂点を記録しておいて, すでに訪れた頂点に再び来たときにサイクルがあると分かる. 使っている記号,マクロ等 "https://ec…
ABC311 D BFS で求まる. 訪れたマスを記録しておいて,1回しか調べないことにする. ただし,通過したマスと止まったマスは区別する. 遷移するとき,ぶつかるまで一気に進むので while 文で実装する. 使っている記号,マクロ等 "https://ecsmtlir.hatenab…
ABC311E \(H, W \leq 3,000\) であるから,\(O(HW)\) は間に合う. 升目を全探索できるので,その上で穴の無い正方形を高速に数える. 升目 \(\,(x,y)\,\) を固定したとき,\( (x,y) \) を左上とする正方形のうち, 穴の無いものを数えたい. これは単調性が…
ABC311 ABC311 参加. E,D の両方で変数名を勘違いしていた. 自分が馬鹿だった. E はギリギリ通ったけど,D は試験の後に AC. 対策: 2次元のときなどは,多少面倒でも 2次元配列を使ったほうが安全? たとえば,サイズが \(N \times M \) のグリッドのと…
ABC202E Euler tour, sub tree, DFS. 取りあえず,木に関するクエリ問題なので, 少ない回数の DFS で多くのクエリの処理を同時に行いたい. 頂点 \(u\) 以下の部分木で,深さが \(d\) である頂点の個数がクエリ毎の答え. これは,深さ \(d\) となる頂点全…
ABC204E コストが変則な Dijikstra. 時刻 \(t\) に 頂点 \(v\) を出発すると,次の頂点に到達する時刻が \(f(t) := c + \lfloor d/(t+1) \rfloor\) となる. 出発するときに待てば良いので,それ以外のタイミングで待つ必要はない. 簡単のため floor を無視…
ABC196E clamp 関数の合成 は clamp 関数になる. 関数をそのまま持たずに,必要な情報にそぎ落とす. 今回の clamp 関数では,組 \( (s,l,r) \) を持っておけば 関数が復元できる. ここで,clamp 関数において, 全体を \(+s\) シフトする, 下限が \(l\),…
ABC205E カタラン数に近い計算. \(K\) に関する条件がなければ \({}_{N+M}C_{N}\) 通り. \(K\) に関する条件を満たさない場合の数は,グリッドを考えると分かりやすい. ある直線があって,その直線で折り返した場合の数に一致する. 通ってはダメな点を列…
ABC201E 距離の定義に XOR が用いられている. 桁毎に独立して計算して,集計するのが良さそう. Tree であることを用いると,根からの距離を用いて \(i , j \in N\) 間の距離が求まる. ここで,距離は XOR であることに注意する. \(l \in N\) を \(i,j\) …
ABC199E BitDP. 順列を決めていくが,次を決めるときに, 今まで選んだ元の集合が分かっていれば,選んだ順番は無関係. 実装\(M\) 個の条件を調べる. 数え上げるとき,常に条件を満たしている様にとっている. つまり,\(s \in 2^{N}\) を調べ終わっていて…
ABC197E 色毎に分けて考える. 回収したボールを並べると,色が広義単調増加なので, 同じ色がひと塊となるから. 色 \(i \in N\) を固定して,色 \(i\) の座標だけを考える. 最適手順として,左端または右端で終える物が存在する. よって,左端か右端か \…
ABC211E BFS で全探索. 丁度 \(k \in K\) マス塗っている状態全体を,入れ物 \(q\) に入れる. \(q\) の中から,次の1マスを塗って遷移すると,丁度 \(k+1\) マスを塗った状態となる. 実装塗ったマス全体の集合を \(2^{N^{2}}\) で管理する. long long で…
ABC239E 部分木に関する処理なので,自然に書けば DFS. 任意の \(i \in N\) に対して, \(K_{i}\) は \(K_{i} \leq 20\) と小さいので, 大きいほうから \(20\) 個すべて保持しておける. 各頂点に関して \(20\) 個まで保持しておいても, 常に空間計算量は…