ARC133C \(\equiv\)は\(mod\ K\)とする． 必要条件や，上限の見積もりを考える． 判定問題最大の前に，簡単のため判定問題を考える． 行列において掛かれた値の和は， 行方向と列方向それぞれで集計すれば， \(\sum_{i \in H} A_{i} \equiv \sum_{j \in W} B…

ARC132C まず，愚直なDPを考えると， \(dp_{i,s} := \) \([0,i)\) まで,使った数のset \(s \in 2^{N}\). これは TLE, MLE. 改良を考える． \(i \in N\) は減らすのが難しいので， \(s \in 2^{N}\) を減らすことを考える． 与えられた条件から，任意の \(i \i…

ARC135C 最終形の性質から考える． 操作を1回以上施した場合，帰納的に ある \(k \in N\) があって，任意の \(i \in N\) に対して \(a_{i}\) は \(a_{i} \oplus a_{k}\) の形． これは， \((x \oplus y) \oplus (z \oplus y) = x \oplus z\) であることから…

ARC136B 明らかに，multiset として \(A = B\) が必要なので，以下ではそれを仮定する． まず簡単のため2-shift で考える． これは常にそろえる事が可能で，先頭から貪欲に決めていけばよい． 次に，3-shift も同様の方針で先頭から揃えてみる． 簡単のため…

ARC158B 3文字動かすのは大変なので，1文字だけ動かす． あるいは，2文字しかないverで解く． 2文字ver\(b\) を固定したときの \(f(a) := \frac{a+b}{ab}\) の min, max を考える． \(f(a) = \frac{1}{b} + \frac{1}{a}\) であるから， \(a\) 自体が min, ma…

ARC141B 2進数で考える． \(d_{a}\) で \(a\) の桁数を表す． \(a \leq b\) ならば \(d_{a} \leq d_{b}\) となる． 今の問題設定では， \(d(A_{i})\) は \(i\) に対して真に単調増加となる． 解法if \(60 < N\) : ans = 0 else 前処理: \(k \in N\) に対して…

ARC144B \(+a, -b\) を単に \(+,-\) と書く． 操作は可換． 最適な操作列の性質操作 \(f\) を， \(i\) に \(+\), \(j\) に \(-\) として， 操作 \(g\) を， \(j\) に \(+\), \(k\) に \(-\) とする． 操作列 \(h\) において， \(f,g\) を使うとする． \(j = …

ARC143B 条件を満たす場合の性質，必要条件条件を満たさないマスを悪いマスと呼ぶ． 悪いマスは高々1個． 2つ以上存在すると仮定して，それらのうち異なる2つを\(x,y\ (x \neq y)\) とする． このとき， \begin{align} a && \cdots &&y \\ \vdots && && \vdo…

ARC145B とりあえず， \(A,B\) の大小で場合分けする． もしかしたら，場合分けは不要かもしれないけど． 今ある石の個数を \(s\) とおく． Case 0 : \(A \leq B\) \(s \geq A\) のとき，Alice は取れるだけ取れば 残りは \(r < A\) 個残るので，仮定\(A \le…

ARC158A 操作の言い換え，不変量等しい値にする事だけが重要なので，差を考えたほうが楽． \(+3, +5, +7\) の操作は \(-2, 0, +2\) と言い換えても良い． 言い換えた操作では， vector \(x\) の値は不変． よって，もし等しい値 \(s\) にできるのであれば， …

ABC293E \(M\) の制約が大きいので，ループで周期を見つける方法は無理． 実際， \(M\) が素数のとき，周期の長さが \(M-1\) になるケースがある． そこで最初考えたのは，等比数列の和の公式を使って，分母が \(M\) と互いに素な 場合に帰着させようとした…

ABC293D \(N\) 個の頂点を2倍して \(2N\) 個の頂点とみなしたグラフを考える． ひもが結ばれているとき，グラフの方で辺があるとみなす． 各連結成分に対して，サイクルになっているかを判定すれば良い． 実装するときは， 初期で \(a,a'\) が繋がっている事…

ABC293_C DFSするか，bit全探索でよい． どちらでも良い場合は，forで実装した方が簡単でミスも少なく， 計算量も良い． 注意DFSする場合は，葉の部分に着いたときに答えを集計するが， return するときに v.pop_back() を忘れないこと． 使っている記号，マ…

ABC195B 実数は全探索できないので，整数部分を全探索する． \(x\)個で可能であるかを判定して， \(x\) を全探索する． \(x\) 個で可能であることは， \(xA \leq W \leq xB\) であることと同値． あとは \(x\) の範囲に注意． \(W\) はグラムに変換するため…

ABC159F O(NS)は間に合うので，次の二つが考えられる． 今見ている index を \(i \in N\)，部分和をとる区間を \([l,r)\) とする． (i): \(i \in N,\ s \in S\) を全探索， (ii): \(r \in N,\ s \in S\) を全探索， (iii): 多項式を使った数え上げ． 解法(i)…

ABC292F 置き方が連続的で，これは全探索できないので， 最適な置き方やその性質を考える． すると，ある最適な置き方であって， 三角形の頂点の一つを，長方形の頂点と重ねたものが存在すると分かる． 以下，場合分けをしてそれぞれのmaxが答え． \(f_{\the…

ABC266C \(AB, BC\) の表すベクトルを，それぞれ\((a,b), (c,d)\) とする． 角 \(ABC < \pi\) であることは， \(ad - bc > 0\) であることと同値． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" ll check(pll x, pl…

ABC146F 最短を求める部分と，lex order 最小を求める部分を，分けて考える． 辞書順最小を求める． これは，全ての候補を求めてソートするのは間に合わないので， 自分で構成したほうが良い． 先頭から小さい順に決めるのが理想だが， それだとゴールできる…

ABC148F \(v \in V\) をとる． 高橋君が最初に居た座標から \(v\) への距離を \(dis_{0}(v)\) とおく． 同様に青木君版を \(dis_{1}(v)\) とおく． 高橋君が \(v\) に到達可能であることは， 青木君よりも先に到達可能であることと同値． すわなち， \(dis_{…

ABC161F \(N \leq 10^{12}\) なので， \(O(N^{1/2})\) は間に合う． よって，約数列挙は大丈夫． 操作の逆を考えて， \(1\) から \(N\) を作ることを考える． \(x\) に \(\times K, + K\) をするが， いつでも出来るとは限らない． \(+ K \) は \(x \not\equ…

ABC216F \(max(A_{S})\) と \(sum(B_{S})\) をとる． \(A\) をソートしておくと良さそう，ただしそれに合わせて \(B\) も一緒にソートする． \(i \in N\) を全探索して， \(A_{i}\) が最大になる \(S\) の取り方を調べる． \(sum(B_{S}) \leq A_{i}\) になる…

ABC292C 何を全探索するか，探索する範囲を小さくすること， 前計算すること． 基本通りにやればAC． まず \(a,b,c,d\) のどれかを \(N\) の範囲で全探索する． 次に \(b\)は \(N/a\) 程度なので， \(a,b\) で \(O(Nlog N)\) 程度． あとは， \(c,d\)を高速…

BABC292 ABC292に参加． 結果A~Dの1000点． Eが解けなかったのが勿体ないのと， Cに時間を使いすぎた． コメントなどABCは部分点が無いのがきつい． 1問の配点が大きいため，一つ多く解けると一気に順位が上がって， 解けないと一気に下がる． AtCoder Jobs …

ABC292D DFSして数える．dfs(cu){ 頂点に入るときの処理 for(ne in to[cu]){ 次の頂点に遷移する辺に関する処理 dfs(ne) 前の頂点に戻るときの辺に関する処理 } 頂点から出るときの処理}が基本形． あとは，ループや多重辺に注意． 使っている記号，マクロ等…

ABC292E 辺の取り方は \(O(N^2)\) ． しかし，辺の追加がやっかいで，シュミレーションするとRE,TLEになりやすい． 最終的なグラフの性質に注目する． 頂点 \(x\) に対して， \(x\)から追加すべき点は何かを考える． \(x\) から何度か辺を辿って辿り着ける点…

ABC167F \(s_{i}\) を一つのブロックだと思って，ブロック単位で計算しても良い． ブロック \(s_{i}\) においての \(p_{i} := \) (min, 増加量)を持って計算すればよい． ブロックの結合に対応する演算は， \*1; sort(rs.rbegin(), rs.rend()); yesno(tot ==…

ABC169F 和だけが重要なので，\(|U|\) は dp の状態として持っておく必要がない． \(dp_{i,x} := \) \(a_{[0,i)}\) において， \(\emptyset \neq U \subset T \subset N\) となる \(U,T\) のとり方であって， \(sum(a_{U}) = x\) となるものの個数 とする．…

ABC255F (Sub) tree を区間で表す．Pre order P : \( [r \ (A_{0})(A_{1})] \), In order I: \( [(B_{0})\ r \ (B_{1})] \)の形で表せる．ここで， \(r\) は root, \(A_{0}, B_{0}\) は左側の subtree, \(A_{1}, B_{1}\) は右側の subtree. Root \(r\) の入…

ABC217F 区間DPとなる． ペアを作って取り除いていく場合の数を数えるが， これは取り除く順序を木構造にして，それを数え上げる問題． 今回は，木の形が決まっていない． \([l,r)\) に対する答えを，より小さい区間に帰着させたい． \(i \in [l,r),\ i += 2…

ABC187F 連結成分ごとに完全グラフになっていることが必要十分． DPでの全探索を考える． \(s \in 2^{N}\) に対する答えを \(dp_{s}\) とおく． 連結成分の頂点の選び方さえ決まってしまえば， その内部でどの様に辺を削除したのかは関係ないので， \(s \in …