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\) 個まで保持しておいても， 常に空間計算量は…

ABC217E ソートの部分を速く済ませるのが課題． 毎回ソートするのではなく，必要な部分だけソートして， そうでないときはソートを保留しておきたい． priority queue を用いると， 各元を追加したときに同時にソートされた形になる． 追加に \(O(log(size(q…

ABC218E グラフ\(G\) に対して， \(I \subset E(G)\) が connected であるとは， \(I\) により定まる \(G\) の subgraph が connected であるときをいう．以下，\(G\) を与えられたグラフとする．\( E := E(G)\), \(E^{-}\)を，\(E\) における負のコストの辺…

ABC195E メモ化再帰で解くのが自然． 結果的には，for を用いた dp で解ける． 後ろから決めていくのが自然． 二人ゲームの基本に則り逆算する． ターンが交互ではなく指定されいているが，勝敗の決め方は同じ． ターンが交互ではないため，勝敗はプレイヤー…

ABC203E DP. 大事な座標だけ見れば十分．差分を高速に計算する．黒のポーンが置かれている行だけが重要． 黒のポーンが無い行は，真下に進むしかないので， 動けるマスに変化は無い． 黒のポーンがある行 \(x\) に対して，黒のポーンの \(y\) 座標を記録して…

ABC208E 桁DP. 先頭の桁の 0を無視しないといけないので， leading zero を保持する． 無視するというのは，積に使わないということ． 実装Leading zero さえ持っておけば，あとは桁DP のテンプレ通り． 注意 まだ \(N\) 未満が確定していないかつ ne > cu …

ABC210E MST. 解法から攻めるのは邪道な気もするが， 問題の性質から攻めて綺麗な方法が作れなかったので， MST のアルゴリズムであるクラスカル法から攻める． クラスカル法により，コストの小さい辺から追加していく． 計算量を無視すればこれで解ける． …

ABC310B 問題文通りに実装． 別解: ソート済みの iterator 範囲 [l, r) に対して std::includes を使うと楽． set やソート済み vector 等に使える． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll …