7K4B blog

猫でも分かる何か

2021-01-01から1年間の記事一覧

深さ優先探索 auto dfs

DFS のテンプレート 深さ優先探索のコツ 樹形図を描く 引数に細心の注意を払う 引数値が1つの状態内で完結してるか、別状態から戻ってきた時に値が復元されてるかチェックする 引数について大雑把な方針としては 頂点インデックスが不要なとき→頂点の値 vx …

ABC025C - 双子と○×ゲーム

ゲーム系の最善手は逆算 木のDFSだが「間違えて元の局面に戻る」ようなDFSが絶対に発生しないので根への遷移かどうかのチェックは不要 問題文を誤読しないよう注意、直大さんのスコアは「マス[i][j] = o かつ マス[i][j] = マス[i+1][j]」でなく単純に「マス…

NyaaLIB::GT_NyaaLCA

LCAライブラリ 木の最近共通祖先 (Lowest Common Ancestor) 前処理 することで以下のクエリに で答える Ancestor(x, y): 木頂点 (x, y) に対する最近共通祖先 Dist(x, y): 全頂点対間距離(任意の2頂点 (x, y) 間の距離) IsOnPath(x, y, z): x-y パス上に頂…

SoundHound Inc. Programming Contest 2018 D - Saving Snuuk

選択肢の少ない状態から考察すると楽 後ろから考えると値を流用できる https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/25168114 0日目から考えると全ての都市で両替できるので最善を考えるのが大変だが n-1 日目なら選択肢は1通りしか…

ABC210 E - Ring MST

https://atcoder.jp/contests/abc210/submissions/24941318最小全域木にクラスカル法というアルゴリズムがある。クラスカル法は「全ての頂点が連結になるまでコスト昇順に辺を選択してく」アルゴリズムだが、頂点と辺の数が多いため愚直にクラスカル法は使え…

AGC017 B - Moderate Differences

足し算と引き算は順序関係ないので足し算と引き算の回数に着目して探索できる https://atcoder.jp/contests/agc017/submissions/24762083ABCD が なので N の線形処理と予想する。例えば A=10 で C=1, D=5 のとき+すると区間 [11, 15] まで表現できる。更に…

LIB::AhriSet

欲張りマルチセット priority_queueとかmultisetとか使い分けるのが面倒な人にオススメ(適当) 内部に unordered_map を持つことで count(x) を定数時間に高速化する工夫をしてある https://rsk0315.hatenablog.com/entry/2019/09/09/214811 namespace LIB …

AGC016 B - Colorful Hats

の種類数が2個以下でないとNoというのは自明なので の種類数を基準に場合分け 条件が多く大変だがサンプルが豊富なので、ある程度サンプルから条件を整理できる https://atcoder.jp/contests/agc016/submissions/24577904自分と同じ色が存在しない猫を「uniq…

NyaaLIB::DS_LazySegmentTree

遅延評価セグメント木 (Lazy Segment Tree) 任意区間のクエリを計算量 で処理するhttps://betrue12.hateblo.jp/entry/2020/09/22/194541 https://atcoder.github.io/ac-library/production/document_ja/lazysegtree.html https://betrue12.hateblo.jp/entry/…

ARC017 C - 無駄なものが嫌いな人

N=32 は半分全列挙 https://atcoder.jp/contests/arc017/submissions/24169529ナップサック問題っぽい文章なのでナップサックDPではないと予想する(ぇ そもそも X が なので DP で処理するのは無理と分かる。 ここで N が 32 しかないことから半分全列挙し…

NyaaLIB::DS_NyaaBIT

BIT (Binary Indexed Tree) 要素加算 、区間総和取得 https://atcoder.github.io/ac-library/production/document_ja/fenwicktree.html Fenwick Tree とも呼ばれる。遅延セグ木の下位互換だが、遅延セグ木に比べて定数倍高速に動作する。 namespace NyaaLIB …

ABC132 E - Hopscotch Addict

頂点を増やすことでmodの遷移を判定する https://atcoder.jp/contests/abc132/submissions/24017041 愚直な考察をすると頂点に移動回数のmod情報を持たせたくなるが、実装が複雑で難しいので逆転の発想をする。具体的には頂点を増やすことで、modの情報を持…

NyaaLIB::DS_NyaaImos2D

二次元いもす法 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) #include <bits/stdc++.h> namespace NyaaLIB { /** * 二次元いもす法 * 矩形区間加算処理O(1)、矩形区間総和取得処理O(1)、更新処理O(HW) **/ template <class T = int64_t> struct DS_NyaaImos2D { int64_t ys</class></bits/stdc++.h>…

テンプレート

型 primitive using bo=bool; using ch=char; using ll=long long; using ld=long double; using vo=void; using ull=unsigned long long; collection template<class T>using de=deque<T>; using st=string; template<class T>using ve=vector<T>; template<class...T>using tup=std::tuple<T...>; te</t...></class...t></t></class></t></class>…

いもす法 LIB::Imos

LIB::Imos 区間加算 、区間和取得 、更新処理 https://imoz.jp/algorithms/imos_method.html 累積和の機能を持つので累積和の上位互換として使える。 単純な累積和だと値の更新はできないが、このライブラリは任意のタイミングで値の更新が出来る。 メンバ関…

ライブラリ

graph 深さ優先探索 auto dfs https://9871225.hatenablog.com/entry/2021/11/25/232020 ダイクストラ法(単一始点最短経路) auto dijkstra LIB::Dijkstra 単一始点から全ての終点までの最短経路を求める https://9871225.hatenablog.com/entry/2022/05/22/…

AGC018 B - Sports Festival

https://atcoder.jp/contests/agc018/submissions/23809861 最大の状態から減らすには何を減らせばよいか考える 最大の状態から始めて小さくするには「最大の要素を取り除くしかない」という貪欲 数字を変化させるには「少なくとも貪欲するしかない」なら貪…

ZONE2021 E - 潜入

https://atcoder.jp/contests/zone2021/submissions/23283470 辺の張り方とコストが特殊なとき、辺の数を減らして同値な移動を再現可能 コストを増やしたい→階層化して辺を追加すれば再現可能 上下左右1マス移動しかないなら単純にダイクストラ法をするだけ…

ABC203 D - Pond

https://atcoder.jp/contests/abc203/submissions/23082310 小さい数を-1、大きい数を+1、としてカウントすると線形処理で中央値かどうか判別可能 中央値を求めるデータ構造として2個の priority_queue を持つ のアルゴリズムがあり、スライドウィンドウして…

ABC165 E - Rotation Matching

https://atcoder.jp/contests/abc165/submissions/22916768 回転するので生徒を円状に配置して考察する 向かい合った頂点に辺を貼ると距離が異なるので被りづらくなる 偶奇で場合分け サンプル2がヒントであり、生徒を並べたとき距離の異なる数字同士でペア…

DDCC2020 D - Digit Sum Replace

https://atcoder.jp/contests/ddcc2020-qual/submissions/22659513 少なくとも(桁数-1)回だけ桁を減らす必要がある 桁は減らないが数字が小さくなる変換もある、条件は2桁の数字 について 適当にシミュレーションしてみると、2桁の数字が小さいとき桁が下…

ABC065 D - Built?

https://atcoder.jp/contests/abc065/submissions/22580754 本当に本の辺を全て試す必要があるか疑うこと 最小全域木なのでクラスカル法ライブラリを貼りたいが、設問そのままグラフを処理しようとするとで間に合わない。街1と繋がるべき街は2と3、街4と繋が…

AGC038 B - Sorting a Segment

https://atcoder.jp/contests/agc038/submissions/22099887 区間の組み合わせが線形という希望的観測をする まず、区間[l,r]と区間[l+3,r+3]のように被っている2区間を各々ソートした結果が等しくなる条件を考えると、互いに被っていない部分にある数が動か…

AGC007 B - Construct Sequences

https://atcoder.jp/contests/agc007/submissions/21896735 の公式が成り立つ理由 結論から言うと が答えになる。 に比べて の制約が非常に緩いことから、ある程度の余裕を持たせて昇順数列 a を考えたほうが良いのかな、という気持ちになる。 公式のように…

Code Formula 2014 C - 決勝進出者

https://atcoder.jp/contests/code-formula-2014-quala/submissions/21743681 で二次元データに順位を付ける 昔は日本語読解が困難な問題も多く、問題文の意味を理解するのが難しいが…一番簡単なテストケースとして重複が一切ない場合は左図のように a[i][j]…

ABC195 E - Lucky 7 Battle

https://atcoder.jp/contests/abc195/submissions/21508217 初期値は dp[N][0]=1 繰り返しは repr(i, N - 1, -1) rep(j, 0, 7) 更新は if (X[i] == 'T') dp[i][j] = dp[i + 1][j] || dp[i + 1][(j + CtoL(S[i]) * NT_NyaaMod::Pow(10, N - 1 - i, 7)) % 7]; …

ABC173 E - Multiplication 4

https://atcoder.jp/contests/abc173/submissions/21143239 K個選んだときの積が負なら「負を1つ減らして正を1つ増やす」「正を1つ減らして負を1つ増やす」両方を試す必要がある 積を最大化するため、絶対値降順に貪欲にK個だけ選ぶ(実際に計算するとオーバ…

ARC043 B - 難易度

https://atcoder.jp/contests/arc043/submissions/20924727 初期値は dp[0][0] = ... = dp[0][N-3] = 1 繰り返しは each(i, e, D) rep(j, 1, 4) 漸化式は dp[j].Add(i, dp[j - 1].Sum(0, distance(D.begin(), upper_bound(all(D), e / 2)))) 最終目標は Sum(…

ABC036 D - 塗り絵

https://atcoder.jp/contests/abc036/submissions/20748614 初期値はall(dp) = 1; 繰り返しは DFS 漸化式は dp[now][B] *= dp[next][W], dp[now][W] *= dp[next][B] + dp[next][W]; 最終目標は dp[0][B] + dp[0][W]; 葉からDPを更新することで根が答えになる…

AGC006 B - Median Pyramid Easy

https://atcoder.jp/contests/agc006/submissions/20609588 中央値なので小中大(x-1, x, x+1)で並べる x, x, y の中央値は x まず、一番上の段がxになるようにしないといけないので真ん中にxを置きたくなる(ぇ 次に、中央値なので x-1, x, x+1 と数字を並…