2023-06-01から1ヶ月間の記事一覧
ABC293E 解法0平方分割． \(O(x^{1/2})\) なら間に合う． \begin{align} y &:= a^{1/2}, \\ b &:= \sum_{i \in y} a^{i}, \\ c &:= \sum_{j \in y} b a^{jy} \end{align} とおく． このとき， \begin{align} c &= \sum_{i, j \in y} a^{jy + i} \\ &= \sum_{…
ABC294E シュミレーションを実装する問題．上下のマスが一致してるか判定しないといけない箇所は， 高々\(N_{0} + N_{1}\) 個のみ．実装上下それぞれについて，run length の情報を deque に入れておく． 取り出して，min(上下の長さ) だけ，今調べている長…
ABC295E ソートはしないで個数を数える． \(1\) から \(m\) を動く確率変数 \(x\) に対して，\(x\) の期待値は \begin{align} e_{x} & = & \sum_{i = 1}^{m} \ i \cdot p_{x = i} \\ & = & \sum_{i = 1}^{m} \ p_{x \geq i}. \end{align} \(p_{x \geq i}\) …
ABC296E 言い換えfunctional グラフが与えられる． 連結成分毎の サイクルの長さの和を求めよ．実装DFS する． 各頂点に対して，3つの状態がある． 0: 訪れてない 1: 訪れたが，まだ遷移の途中の点． 2: 訪れて，遷移が全て終わった点 気持ちとしては， 1 が…
ABC297E 小さいほうから順に構成していく． \(x\) 円が作れるとき，どの様な作り方かは無関係に \(x + a[i]\) 円が作れる． 作れる値全体を保管する set を用意すればよい．実装今調べている場所をiterator で持っておいてもよいし， 調べ終わったら set か…
ABC298E 確率DP. ゲームの終端から決めていく.実装1再帰で奥の方から決めていく． 決まった場所は答えをメモしておくことで，同じ計算を省略できる． 再帰なら，仮にゲームの遷移が複雑な場合でも可能． 実装2for でも実装できる．今居る座標を\(x\)とおけば…
ABC246F 包除原理の基本を学ぶのに丁度良い問題．\(\cup_{i \in N} X_{i}\) の要素の個数を数える問題． \(\Lambda \subset N\) に対して， $$\cap_{i \in \Lambda} X_{i}$$ を高速に求められれば十分． 実装:使える文字の種類 \(\subset 26\) を高速に求め…
ABC251E Cycle DP. 最初を固定して考えて，1周してきたときに辻褄があっている物を採用する． 実装:\(-1 \,(mod N)\) 番目を固定した上で， \(for i \in N\) をループする． \(i = N-1\) のときに，最初に固定したものと一致するものを採用する． 使っている…
ABC232E 配るDP. 類別して状態をまとめる．遷移する際，今いるマスと次のマスそれぞに対して，(ゴールのマスと同じ行にいるか) \(\in 2\), (ゴールのマスと同じ列にいるか) \(\in 2\)の情報だけが重要． つまり，状態をまとめて減らすことができる．注意:行…
ABC307E Cycle DP. この問題のポイントは2つ． 最初を決め打って，一周したときに辻褄が合うようにする． 基本は line 型で考えて，最後だけ注意する．類題: ABC251E (記事) 状態をまとめること． \(0\) 番目を固定して \(i\) 番目を決めるときに，(\(0\) 番…
ABC307D 実装:愚直に実装する． 再帰で実装するより，for, while の方が楽．本番では沼らない様に，多少無駄でも素直な実装が安全． この問題なら， \begin{align} &for(c \in s) \\ &\ \ \ c \text{で場合分け} \end{align} とすれば，迷わなくて済む． 使…
ABC307B \(S[i]\)と\(S[j]\)の順番が異なるときに， 異なる文字列になることがある．文字列 \(t\) が回文である \(\iff\) 任意の \(i \in [0, \lfloor t.length()/2 \rfloor)\) に対して，\(t[i] = t[t.length()-1-i]\).\(i \in [0,t.length())\)でもよい． …
最近は, AtCoder Beginner Contest が unrated になることがある． 良い成績が取れたとき -> unrated 悪い成績のとき -> rated イライラする．
ABC278F 分野: ゲーム，メモ化再帰． ルール通りに再帰を書けば良い． 局面は， 組\*1; // rem: v = -1 にしてしまうと memo[s][v] の indexx で RE. auto dfs = [&](auto self, ll s, ll v) -> bool { if(in(v,n) && memo[s][v] != -1){ return memo[s][v];…
ABC279F Balls と boxes の対応を表す写像を作りたい． ただし，balls は同じ箱に入っているものは同一視できるから， 類別して代表系で考える． つまり union-find が便利． $$f : Balls / \sim \ \rightarrow \ Boxes,$$ $$g : Boxes \ \rightarrow \ Ball…
ABC280F 全域木の ポテンシャルを用いた問題． \(x, y \in V(G)\) をとる． Case: \(x,y\) が異なる connected component に属するans = nan. Case: \(x,y\) が同じ connected component \(=: H\) に属する Case : あるサイクル \(c\) on \(H\) のコスト が …
ABC301E 5 sec, 1024 mb. 制約が 5 sec と長い． 大事な頂点の個数が少ない事を利用する． \(S, G, o\) が 20 個以下になるので，bit dp 可能． つまり，訪れた点の集合と時刻さえ分かれば，順番は関係ないということ． 実装: お菓子の置かれたマスの個数を …
ABC281F 解法 桁ごとに独立に計算する． 上の桁から決めていく． vector \(a\) に対して，各元の \(2^{k}\) の係数が \(0,1\) で分類する． それらを \(a^{(0,k)}, a^{(1,k)}\) とおく． \(f(k, a)\) を，\(x\) を動かしたときの \(x \oplus a\) の \(2^{j} …
ABC291F グラフの形が特殊なことを用いる． 各頂点から出ている辺の本数は，高々 \(M \leq 10\) 本． 頂点 \(k \in N\) を通らない \(0\) から \(N-1\) への path は， $$ 0 \rightarrow x \rightarrow y \rightarrow N-1 $$ の形． ここで，\(x \rightarrow…
ABC306E 上位 \(K\) 個が重要なので，それを持っておく． ただし，\(K\) 個の中から追加や削除を行う場合がある． 削除するとき，足りない分を補充しないといけないので， 残りの\(N-K\)個も保存しておく． 削除の際に，配列 \(a\) 自体も持っておく必要があ…
ABC306D 状態をまとめる事でDPできる． 遷移に影響するのは， 今の料理が解毒剤入りか 今まで食べた美味しさの合計 のみであり，それまでお腹を壊したか否かの状態列は無関係． つまり状態をまとめる事が出来る． 使っている記号，マクロ等 "https://ecsmtli…
ABC302E 同じ頂点同士を結んだ辺であっても， 追加される度に別の辺として考える． 各辺に対して， 高々1回ずつしか追加と削除が行われない． 言い換えると，追加の回数が合計\(x\)回なら， 削除の回数は合計\(y \leq x\)回しか行われない． 一方，\(x \leq …
ABC303E 星の特徴になっているのは中心なので， 中心を軸に考える． 星において，中心から出てる頂点を葉と呼ぶことにする． \(T\)において degree が 1の頂点は， もとのグラフで星の中心にならない． また，星\(S_{0}\)の中心 \(\rightarrow \) \(S_{0}\)…
ABC305C 角が欠けているときだけ注意．もとの長方形の大きさが，1辺が2以上であることにも注意すると， もとの長方形の辺にあたる部分が特定できる． 言い換えると， 一番小さい行， 一番大きい行， 一番小さい列， 一番大きい列 の番号が手に入る． 使って…
ABC305D 0-indexed とする． 区間毎に値を振っておく． 偶数番目とき数番目の区間に対して，0 と 区間の長さを対応させる． この値に関して累積和をとればよい． 区間の端だけ中途半端になりうるので微調整．\(l,r\)が与えられたときに，どの区間に\(l,r\)が…
ABC305E 多始点Dijkstra. 各警備員に対して，警備している頂点を求める． 警備するたびに体力が減っていくと考えると， 残り体力を保持しながら遷移する． ただし，このままではTLE.頂点 \(v\) であって，\(v\) を複数の警備員が警備されているものを 任意に…
ABC304D ケーキの個数は (A+1)(B+1) 個なのでTLE. そこで，イチゴが1つ以上乗っているケーキの方だけ注目する． これは\(N\)個．イチゴの座標が与えられたとき，どのケーキに乗るのかは， binary search で求まる．各ケーキ毎にイチゴの個数を数えるが，それ…
ABC304E クエリ問題で，一つのクエリにつき高速に求める． 良いグラフの定義通りだと，全ての\(i \in K\)に対して調べることになるが， クエリでは1本しか辺を追加しないので，変化は少ない． クエリ毎に共通して使える部分が多くあるので，そこを前処理して…
