ABC310C 最初は，回文かそうでないかで分けて考えていた． 回文を入れる string 型の set を a, そうでない文を入れる set を b とする．ただし，b に入れるときは， \(s_{i}\) と \(reverse(s_{i})\) の両方を入れる． \(i \in N\) の \(s_{i}\) を \(a,b\)…

ABC310D \(N,M,T\) がいずれも小さいので，全探索して数えても間に合いそう． DFS によりすべて列挙する． このとき，取りこぼしと重複が無いようにする． 今回は起こらなかったが，仮に重複するのなら，その分を割ることにする． 実装先に \(T\) 個の入れ物…

ABC310E 区間の数え上げ． 最初に考えたのは，\(x nand y = 0\) になる \(x,y \in 2\) の方が少ないから， 取り方全体から\(0\)になる取り方を除く方針だった． 区間 \([l,r]\) の nand が\(0\) になるケースは， \(r\)が \(1\) かつ \([l,r-1]\) までの nan…

ABC216E 同じアトラクションに何回乗るのかを高速に求められれば十分． Multiset としての和 \(B := \cup_{i \in N} \{1, \cdots, a_{i}\}\) を取る． \(B\) の元から，大きいほうから \(K\) 個まで取ってくるのが最善． \(m \in \mathbb{N}\) に対して， \(…

ABC215E BitDP. 今調べている \(i \in N\) に対して，コンテストに参加出来るかどうかは， 次の2つが分かっているれば十分． 今まで参加したことのあるコンテストの集合 最後に参加したコンテスト 実装:10種類のコンテストがあるが， まだ 1回もコンテストに…

ABC222E \(a\) により path \(p\) は一意に定まる． よって，\(p\) の中で各辺が何回現れるのかをあらかじめ求めておけば， 各辺の色分けを固定したときに赤と青がそれぞれ何回になるか分かる． 赤，青に塗った辺の本数をそれぞれ \(r,b\) とおき， 辺 \(e\)…

ABC224E マスに書かれた数字が大きいところから答えを決めていく． 大きい数字のマスの答えが確定していれば， (同じ行または同じ列の)小さい数字のマスの答えが確定する． 遷移するために持っておくべきものを求める． 今答えを決めようとしているマスを \(…

ABC224E 連結成分毎に独立して解ける． 連結成分毎の答えを掛ける． 出ている辺と頂点が1:1対応する必要があるので， 辺の本数と頂点の個数が等しい必要がある．逆にこのとき，連結成分は functional graph となり， サイクルが一つだけ存在する． そのサイ…

ABC228E フェルマーの小定理．問題文通りに考えると， 数列 \(A : N \rightarrow K\) の取り方は \(K^{N}\) 通り． 点数の付け方は \(K^{N} \rightarrow M\) であるから，\(M^{(K^{N})}\) 通り． よって，フェルマーの小定理で求まる． 注意 底 \(M\) が \(0…

ABC229E クエリ逆算，クエリの差分辺の削除より，辺の追加の方が簡単なので，そちらで考える． 一つ頂点を追加したときに，connected component がどの程度変化するのか， 差分を求めることで高速にクエリを処理する． 大きい番号から頂点を追加していくので…

ABC230E 同類項でまとめると， 調べるべき \(i\) の個数が \(O(2\sqrt{N})\) 個で抑えられるのがポイント． 見積:ざっくり言えば，\(x := \lfloor \frac{N}{i} \rfloor\) は \(\frac{N}{i}\) とほぼ同じ． よって，\(N\) の約数と同じ程度しか \(x\) の値は…

ABC233E 実際に手を動かしてみると， 各桁ごとの累積和を計算すれば良いことに気づく． 実装:数字を文字列で扱う．繰り上がりに注意． また，繰り上がりが発生すると，最初に与えられた \(x\) の桁よりも ずっと答えの桁が大きくなる可能性がある．繰り上が…

ABC234E \(x\) 以上の最小の等差数を求めるのであるが， まず候補の範囲を考える． \(99\cdots9\) は等差数なので， \(x\) と同じ桁数だけで十分． よって全探索できる． 先頭から決めて行けば良い． 小さい等差数から調べていく． 使っている記号，マクロ等…

ABC235E クラスカル法．与えられた辺がMSTに含まれるか判定する問題． まず，MSTを構築するアルゴリズムをベースに考える． クラスカル法では，コストが小さい辺から使っていく． 辺 \(e : a \rightarrow b\) を追加するかどうかは， \(a,b\) が既に同じ con…

ABC237E ポテンシャル，ダイクストラ．まず，登りが下りのコストの \(-1\) 倍の場合を考える． これは簡単で，始点と終点のみで決まる． 次に，登りが下りのコストの \(-2\) 倍の場合を考える． この場合，\(s\)から\(t\)へのコストは，\(H_{s} - H_{t} + \)…

ABC238E 累積和をを求めるのと同値． \(s_{i} := \sum_{j \in i} a_{i}\)とする． 与えられる情報は，\(s_{r} - s_{l}\) となる． ここで \(s_{l}, s_{r}\) の内，一方が分かればもう一方が分かることになる． また，最初に分かっていることは，\(s_{0} = 0\…

ABC241E ダブリングで求める．問題文通りに実装を考えてみる． 皿に乗っている個数を \(x \in \mathbb{N}\) 個としたとき， 次に乗っている個数を \(f(x) \in \mathbb{N}\) 個とする． \(x_{0} \in \mathbb{N}\) を指定したときの \(f^{K}(x_{0})\) を求めれ…

ABC242E 辞書順なので，先頭から決めていくことを考える． 回文なので，真ん中まで決めれば残りは自動で決まる． 桁DPのときに近い． 先頭から文字列を決めていって，既に真に(辞書順で)小さいことが確定しているか否か \(\in Bool\) を保持しながら遷移する…

ABC243E 辺 \(e\) を一つ固定する． \(e\) を残す条件，消す条件を考える．基本的には，同じコストなら path は長い方を残すのが得と言える． \(e = (a,b)\) を消すのは，ある \(k \in V\) であって， \(k \not \in \{a,b\}\) かつ \(cost_{e} \leq cost_{a,…

ABC309A テストケースは，与えられている物でなく， ミスの起きやすいケースを自作して行う． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll a,b; cin >> a >> b; yesno(b == a+1 && a % 3 != 0); r…

ABC309B 実装配る形が楽だった．貰うでも実装は可能だが，何となく配る法が自然に感じた．試験本番では，実装が面倒で一旦飛ばして戻ってきたら， すんなり書けた． 躓いたり時間がかかると感じたら，試験では一旦飛ばすのは有効． 使っている記号，マクロ等…

ABC309C Imos 法で OK． 結局，大事なのは区間の端だけであり，それ以外は答えに影響しないから． 大事な場所だけ全探索するということ． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, k ; cin …

ABC309D Connected component 毎に，始点を固定したときの最短距離はBFSで求まる． つまり，その中での最大値も求まる．2つの connected component それぞれの最大値を求めて， それの和 + 1 が答え． 使っている記号，マクロ等 "https://ecsmtlir.hatenablo…

ABC309E 何代先まで保険に入っているかは，DFSで確認できる． 実行時間に間に合わせるには，DFSの回数を減らすことを考える．人 \(i\) が複数の保険に入っているとする． \(i\) から \(x\) 代先まで，\(y\) 代先まで保険に入っているとする． このとき，\(i\…

ABC245E マッチング問題．箱を大きい順に優先して使っていく． 入るチョコの内，なるべく大きい物を割り当てたい． 箱とチョコを両方まとめて入れ物 \(s\) に入れておく． 辞書順で大きい順に並べておく． \(s\) から順に取り出していく． チョコが出てくる…

ABC252E Dijikstra tree を求める問題． Dijikstra 法は，最短経路を求めるアルゴリズムよりも高性能で， 最短木を求めるアルゴリズム である． 実装普通に Dijikstra をして，直前の遷移するときの edge を記録しておけば Dijikstra tree が手に入る． 注意…

dp を累積和で高速化する． \(dp_{i,j} := [0,i)\) まで，last \(j\) のときの答えとする． 今を\(y \in M\)，直前を \(x \in M\) とすると， 遷移は\(dp_{i+1, y} += \sum_{x \in [l,r) } dp_{i,x} \)となるので，累積和で高速化できる． ABC253E 使ってい…

ABC257E 決め方の優先順位 \(x\)の桁数の max 桁数を固定したとき，使う値を大きくする 各桁に使う値の multiset を固定したとき，大きい順に並べる これらを優先順位の通りに求めればよい． 2つ目の条件，桁数を固定したときに使う値を大きくするのは， 9 …

ABC259E 操作する場所 \(i \in N\) を全探索． 操作を何もしてないときも含めて，\(N+1\) 通りを考える． 何もしてないときの \(LCM(a)\) を \(L\) とおく． \(LCM_{j \in N, j \neq i}(a_{j})\) を \(L_{i}\) とおく． \(i\) 番目を数えるかどうかは， \(a_…

ABC261E 桁毎に独立して計算することで高速化できる．与えられた \(i \in N\) 番目の操作を \(f_{i}\) とおく． 前計算として，\(g_{i} := \Pi_{j \in i} f_{i}\) を求めておけば良い． ここで，\(f_{j}\) たちは非可換であるから，このような表記は記号の乱…