2023-01-01から1ヶ月間の記事一覧
ABC287 A~Dの1000点． D問題先頭から調べるのと末尾から調べるのは， 同様の操作になるので関数化できる． \(s[0,i+1)\) と \(t[0,i+1)\) がマッチするのは， \(s[0,i)\) と \(t[0,i)\) がマッチするかつ \(s[i] = t[i]\) または \(s[i] = ?\) または \(t[i]…
ABC286 ABC286受験結果 A~E の1500点STLを使えば実装はもう少し早かった． C問題操作が複数与えられた場合は，順序を変えるとどうなるかを考えると役立つケースが多い． 今回は最適解として， Rotateを何回か \(\rightarrow\) 置き換えを何回か の形のものが…
ARC135B まず，漸化式に出てくる項を減らしたい． \(a_{i} \geq 0\) の条件を無視する． \(S_{i}, S_{i+1}\) の変化を調べると， \(a_{i}, a_{i+3}\)だけが異なり，\(a_{i+1}, a_{i+2}\) は共通している． 式 \(-a_{i} + a_{i+3} = - S_{i} + S_{i+3}\) を得…
ARC134B 貪欲法． アルファベット順の小さいほうから試す 右側から優先して選ぶ 左側からも優先して選ぶ 左，右から選ぶindexを\(l, r\) とすると， 常に \(l \leq r \) である． このことに注意すると， \(O(N)\) で実装できる． 使っている記号，マクロ等 …
ARC133B 拡張したLIS.類題: 問題:ARC126B， 記事実装 \(P\) のindex を回した方が楽． 倍数判定なので，エラトステネスの篩と同様にできるため． \(Q\) のindex を回すと，約数を列挙しないといけないとので， \(O(N^{\frac{1}{2}})\) が余分にかかる． 使っ…
ARC122B \(x \in \mathbb{R}\) であるから，範囲を狭くしたい． min を外すため，大小で場合分けする． 場合分けの境目の値が候補になりそうで， 実際にそうなる． これで候補が \(N\) 個に絞れたので全探索できる． 実装\(a\) の中に同じ値が複数ある場合に…
ARC124B 2つのvector に対して，次は同値． ある並べ替えで一致 multiset として一致 ソートしたvectors が一致 よって， \(x\) を固定したとき， \([a_{i} \oplus x ]_{i \in N}, \ b\) が multiset として一致していれば良い． \(x\) の候補は \(a_{0} \op…
ARC120B \(k\) を固定する． \(k = i+ j\)となる (\(i,j\)) の組は同じ色で塗るのが必要． 逆に十分であることもよい．例えば，以下の様にグリッドを類別する． 0から8まで移動するとき， パスによらず 0から8のマスをそれぞれ一度ずつ通る．0 1 2 3 4 5 1 2…
PAST003D 出力1をコピーすれば， \(0, \cdots, 9\) に対応するchar たちが分かる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { vector<string> t = { ".###..#..###.###.#.#.###.###.###.###.###.", ".#.#.#</string>…
PAST003F 回文は，外から決めるか内から決めるかのどちらかが基本． 今回は外から決めることにするが，どちらでも可能． \(a_{i}\) と \(a_{n-1-i}\) に共通の文字があればそれを使う， なければ回文が作れない これを \(i\) について貪欲に決めていく． 今…
PAST003G 問題文に金移動とあり将棋の金のような動きだが，移動方法はあまり重要ではなく，基本はBFS. ただし，そのままやると無限に広がるグリッドなので無限ループに入ってしまう． そこで，グリッドの範囲を狭くすることを考える． 遠くに行き過ぎるメリ…
PAST003H 座標 \(i\) にいるとき，次に取るべき行動は， 今までの行動とは無関係に選べる． つまり，時刻だけが重要で今までの選択は無関係なので， 状態をまとめることができ，これはDPで実現可能． 実装ジャンプ中にゴールするときだけ注意． 問題文にも書…
PAST003I 転置のクエリだけが時間がかかるので，そこを何とかする． 転置は2回繰り返すともとに戻るので，回数だけ記録しておく． また，行と列は独立に操作可能． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int…
PAST003J LISに近い問題． 実験してみると，子供 \(i \in N\) が食べた最大の寿司を \(v_{i}\) とおくと， \(v\) は常に降順． よって，誰が食べるのかは binary search で求まる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/1…
PAST003K データ構造の問題． 愚直に移動を実装していてはTLE. コンテナ毎について， 下に何があるか，上に何があるか を記録しておく． 切れ目とつなぎ目だけ更新すれば良いので \(O(Q)\) 実装今回の問題では，上に何があるかは記録しなくてもよい，また，…
PAST003L データ構造を用いたシュミレーションの高速化問題．\(1 \leq a_{i} \leq 2\) と小さいので，そこから考える． 簡単のため， まずは\(a_{i} = 1\) で考える．最大値を高速に求める必要がある． 消費期限はすべて異なるので，set型で実現できる． 最…
ABC284D \(N = p^{2} q \leq 9*10^{18}\) と \(N\) が大きいが， 素因数の最小値は小さい． (重複を許して)3つの素因数があるので，どれか一つは\(N^{1/3}\) 以下． よって， \(min(p,q)\) のうち，一方は全探索で求まる． \(p,q\) の一方が求まれば，もう一…
第二回 アルゴリズム実技検定 K問題 \(O(N^{2})\) は通る． 全探索するとき， \(for \ i \in N\) はこれ以上簡単に出来なさそう． そこで，残りを\(O(N)\) で押さえたい．( を+1, ) を-1 とみる． 計算量を無視して，持っておきたい情報（状態）を考えてみる…
第二回 アルゴリズム実技検定 I問題 完全二分木のトーナメントをシュミレーションすれば良い． \(2^{N}\) 人のトーナメントの試合全体は \(2^{N} * 2\) 個程度なのがポイント． 実際，等比数列の和の公式から \(1 + 2 + 4 + \cdots + 2^{N} = 2^{N+1} - 1\)…
第二回 アルゴリズム実技検定 H問題 のマスには が書かれていると考える． とする．前処理として， を求めておく． 遷移は : 今のマス : 次のマス に対して全探索すればよい． 2マス間の距離はマンハッタン距離． 使っている記号，マクロ等 "https://ecsmtli…
ARC114B の定義域を に制限したとき 値域が になり単射となる を数え上げる． つまり， の値域と定義域を に制限したときに 全単射となる を数え上げる問題． は functional graph と呼ばれるグラフになる． 連結成分毎にサイクルが一つあり，そこに枝が何本…
ARC106B 連結成分毎に考えてよい． 連結なグラフで考えるとき，まずはtreeで考えるとよい． Spannig treeを用いて，treeの場合に帰着できるケースも多いし， まずtreeで解けないと，一般の場合は話にならない． また，操作の性質として，操作によって値の総…
ARC108B fox の文字が全て異なっているので楽． s を先頭から調べていき，スタックに積んでいく． スタックの方で後ろ3文字がfoxになったら消せばよい． O(N)で解ける． 実装は，スタックでなくvector で行った． 使っている記号，マクロ等 "https://ecsmtli…
ARC109B まででなく， と が入っているのが気になる． まず，丸太の買い方として，同じ値段なら長いほうが得． 言い換えると，短いほうで出来るなら，長いほうでも出来る， いわば上位互換． 上位互換の考えは，貪欲法を示すときによく使う． 大きい方から買…
ARC110B 110をブロックと考えて分割する． 個のブロックに分ける． 実装を簡単にするため，110のブロックを 個並べた文字列 を用意する． のとき， の最初の3文字によって場合分けして考える． の形も，同じ形の繰り返しになり，最後に余った部分が出てくる…
ARC111B カードの表裏に書かれた数字を頂点として，カードを辺とみなしたグラフを考える．カードの表裏を選ぶ事は，辺に向きを付けることとみなす． 連結成分毎に考えればよい． 連結成分をtreeの場合を先に解いて，そうで無い場合はtree に帰着させる． 連…
ABC282E ボールを頂点としてグラフを考える． 辺にコスト をつける．辺 を選んで を戻すという操作により， に を対応させる．操作は 回で終わる． 有限グラフであることから，サイクルはない． よって，操作で選んだ辺全体は木になる．あとは，最大コストに…
ABC270Dmin-max法．まず，簡単な問題を考える．何個取れるのかは無視して， 先手が必勝か必敗か引き分けかを判定する． 先に判定問題を解いて，それを改良する手法はよくある．判定問題 := (先手の取った石の個数) - (後手の取った石の個数)を考える． 最善…
ARC126一般化したLIS.LIS まず普通のLISを考える． vector に対して，連続するとは限らない部分列であって 狭義単調増加になるもののうち，最長の長さを求める問題． 増加列は2つの図形的な捉え方がある． 一つ目は，の組を頂点として2次元平面に図示すれば…
