競プロ問題記事逆引き
Notionで造ろうと思ったけどNotion操作下手なんで......
Diffは下位はマイナス、中位は無印、上位は+をつける。具体的な境界はない。
木系
| Title | Diff | タグっぽいの | 簡単な説明 |
|---|---|---|---|
| ABC202-E | Blue- | 木 クエリ 先読み | 木の上のオイラーツアー(記事に詳細ある) |
| LowLink法の解説 | 木 橋 関節点 | LowLink法勉強してた時のメモと写経してカスタマイズしたライブラリ |
実装テク系
| Title | Diff | タグっぽいの | 簡単な説明 |
|---|---|---|---|
| ABC277-D | Green- | modで連続の実装 | modで連続系は同じ配列を2つくっつける。その時は集計する区間の長さが元の配列を超えないように！！！ |
データ構造系
| Title | Diff | タグっぽいの | 簡単な説明 |
|---|---|---|---|
| ABC273-E | Blue- | 永続データ構造 | 永続スタックの理論の解説 |
グラフの橋と関節点の効率的な判定LowLink法の解説
LowLinkを実装してみた。自分用の詰まった部分のメモも含む。
どういう問題をやるの
グラフが与えられて
- 関節点 その点を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる)
- 橋 その辺を取ってしまうと、グラフの連結成分は増えてしまう(バラバラになる)
これを求める。
Union-Findでつながってるかどうかを$ O(V + E) $で判定できるので、 抜く頂点や辺を全通り試せば、$ O(V(V + E)), O(E(V + E)) $の計算量になる。
LowLinkという手法を使うことで、$ O(V + E) $にとどめることができる。
LowLinkのきもち
先行記事たち。ここら辺を見ながらこれをサブノートとして見る方がいい。
DFSしながら、ループを構成してるものに全部同じ番号を割り当てることで、ループ内なら基本的に点や辺抜いてもOKを実現させている(いくつかの例外あり)
low[]は、初めは今の頂点のDFS順番を入れる。
そして、今の点からがすでに訪ねたことがある点に行きついたとき、その時点でループが完成されているので、訪ねたことある頂点のDFS順を入れる。
そして、今のDFSの再帰を終わらせて戻りながら、その今の再帰を呼び出したものにも衝突した点でのlow[]を、minで伝播させる。
橋の判定は
- 親のDFS順 < 子のlow
- 子のlowはループ作ってるなら、ループ内でみんな同じだが、みんな親より後にDFSで見たので、これが必ず成り立つ。
関節点の判定は
- 根ノードなら、子が2つ以上
- 1つしかないなら明らかに取り除いても、全体のグラフを複数の連結成分に分割させない。
- 根ノード以外だと、親のDFS順 <= 子のlow[]
- 橋と違って、子のlowが親と等しい=ひとつのループを構成する時でも、そこを取り除いたらループ自体は壊れることから、イコールの条件を追加。
実際の例
ここが一番の本体だったりする。どこにも無かった一歩ずつの例の動画とかを載せてみた。
将来の私も含めて困ったら見にこよう。
実装例
/** * 関節点と橋をO(E + V)で求めるアルゴリズム. */ class LowLink { typedef std::vector<std::vector<int>> Edge; /** * 訪問したことがある頂点かどうか. */ vector<bool> visited; /** * 順序. */ vector<int> order; /** * 配列low. low[親] < low[子]なら、ブリッジとなる。 */ vector<int> low; public: /** * 与えられる木。隣接リスト形式でコストは含まれない.親は-1とする。 */ Edge E; /** * 関節点 その点を取り除くと全体が不連結になる点. */ vector<int> articulation_points; /** * 橋。pair<int, int>でfirst < secondで橋となる両端を入れる. */ vector<pair<int, int>> bridge; private: void dfs(int now, int parent, int& count) { visited[now] = true; order[now] = count; low[now] = order[now]; count++; bool is_art = false;/* 関節点であるかどうか */ int son_count = 0; for (auto next : E[now]) { if (!visited[next]) { son_count++; dfs(next, now, count); if (next != parent) low[now] = min(low[now], low[next]); // ループに行きついたときに、戻る際の伝播 //関節点か イコールがつくのは、ひとまとまりのグループ内のlow[]は関節点のlow[]と同じ値だから。端はもうこれ以上伸びないので、関節点にカウントしない if (parent != -1 && order[now] <= low[next]) is_art = true; //橋か if (order[now] < low[next]) bridge.push_back(make_pair(min(now, next), max(now, next))); } else { //すでに行ったことある頂点=後退辺 if (next != parent) low[now] = min(low[now], order[next]);// ループに行きついた時にorder[]を代入 } } //根は2つ以上の子があるなら、関節点 if (parent == -1 && son_count >= 2) is_art = true; if (is_art) articulation_points.push_back(now); } public: /** * 渡すのは隣接リスト形式のグラフ。辺の長さは受け付けない. * * \param e */ LowLink(const Edge& e) { E = e; visited.assign(E.size(), 0); order.assign(E.size(), 0); low.assign(E.size(), 0); } /** * 計算の際に呼び出す。各連結成分ごとにDFSしている。. * */ void build() { int count = 0; for (int i = 0; i < E.size(); i++) { if (!visited[i]) dfs(i, -1, count); } } };
使い方は下のverifyの問題のソースコードを参照。
一言
やっぱライブラリ写経は大事。1回理解してこういう記録を残しておくと、将来の自分が追いやすい。
ABC273-E
問題概要
クエリが$ Q $個、以下の形式で与えられ、最初は空列を1つ持ち、$ 10 ^ 9 $ページあるノートの各ページには空列が初めから入っている。
ADD x列にxを末尾に追加する。DELETE列の末尾から1つ削除する。空列の場合は何もしない。SAVE x今の列をノートのxページに記入。LOAD xノートのxページの列で、今の列を置き換える。
すべてのクエリを実行するたびに、今の列の最後尾の要素を出力する。空列ならば、-1と出す。
制約: $ Q \in [1, 5 \times 10 ^ 5], x \in [1, 10 ^ 9] $
考察
愚直だとどうなる
明らかに愚直だと大量にコピーをせざるを得なくなる。これはメモリも、制限時間も超える。
必要なぶんだけ持たせてコピーはどう？(TLE)
では、全部コピーが厳しいなら、クエリを先読みして、たかだかX個までしか後続でみられないのならば、保存する列を末尾からX個に縮められるよね？の方針を考えて、必要な分だけコピーを考えてみる。
方針として、後ろから読んでいく。値として、今Xページのデータをロードというコマンドが来たら、これから逆算してセーブコマンドで渡す野に必要な配列の長さを持たせ、これを$ A $とする。
- ADD
A--1つ足すので、必要なセーブ時に渡す配列の長さを減らせる。 - DELETE
A++1つ消すので、必要なセーブ時に渡す配列の長さを減らせる。 - LOAD X 後ろから見てここでXページからロードされたので、XページにSAVEする際にわかるように、std::mapでSAVEする際の保持するべき配列の長さをメモ。このとき、
- 最低の長さを1にする。なぜならばロードした直後に配列の末尾を知る必要があるので、たとえロードしてADDを連発しても最低でも1つはメモしないとならない。
- すでにXページの必要な長さがYだとわかっている場合、今の必要な長さがY以下ならば、更新しない。
LOAD 4, DELETE を5回, LOAD 4, DELETEを5000回のような物の対策- 言ってしまえばここがTLEの原因。
めちゃくちゃADD, SAVE 1, (LOAD 1, DELETE1回)を10万回, LOAD 1, DELETE10万回とかされると、配列のstd::mapからの全数コピーが何回も出てしまうし、これは根本的には対処のしようがない。
- SAVE X Xページにセーブする必要があるときの長さを、逆算してる過程でのメモから回収する。ただし、今の持っている長さの方が、逆算過程からの要求長さより長いならそのままキープ。
1ケースだけWAになってしまったが、上をうまく実装できてない可能性もある。ともかく、3ケースだけTLEで落ちる。
ACするには
GitHubと似ている。
struct Node { int val, parent; vector<int> next_idx; Node(int a, int b) { val = a, parent = b; } };
こんな風にNodeを作って、vectorにでも入れて、木を作る。そして、注目してるノード(のvectorのなかでのindex)をカーソルとする。
まずは、Node(-1, -1)で根のノードを作り、カーソルをそこに置く。次のように操作する。
ADD今のカーソルの子に新しいノードを作り、カーソルをそこに置く。- この時、子にvalが同じなノードがあったとしても、別の新しいノードを作る。その判定をすること自体が線形時間かかってしまうからである。今回の制約では全部新しく作ってもメモリ的には超過とはならない。
DELETE今のカーソルを親に置く。もう親がないのならば、それは空列なのでカーソルそのまま。SAVE Xstd::map<int, int> reference;のように作り、reference[X] = カーソル;として、連想配列で保存。LOAD Xカーソル = reference[X];
ここで、連想配列を使用することによって全体では$ O(Q \log Q) $時間がかかる。ここでは、SAVEとLOADは、木構造で列を保持する事によって、どの頂点かを保持するだけで一意に全ての操作に$ O(1) $で対応できるのがポイント。
このように、スタックの操作を撒き戻したりすることはまさにGitHubのツリーの形そのものである、言われてみればそう。
永続スタック
noshiさんの解説。私も家に永続データ構造飾ります。
今回の要求されるのはスタックというデータ構造であるが、これを永続化させたもの。永続化データ構造とは、
- 普通のそのデータ構造の動きができる。
- 過去のある時点でのデータ構造のデータを、低コストで保持できる。
- 例えば、
std::stackはコピーしておくと、入れたデータのサイズ$ n $に依存した時間$ O(n) $かかってしまう。
- 例えば、
今回の場合、うまく木で実装したことによって、複数回stack自体を保存する前提で、1回ごとの操作量に均したとき、操作を終えたあとのstack自体を保存させるには、本質的にはノード1つぶんとそれを指し示すindexだけである。これはほぼ$ O(1) $に近い。
上のように、木で実装したのが永続スタック。
一言
永続データ構造を一通り勉強して家に飾ろう。
ABC277-D(Green-)
概要
カードが$ N $枚で$ A _ i $である。最初はすべて手札。次のようなことをして、手札に残るカードの和を答えよ。
- 手札からカード1枚を選ぶ。
- 次の行為を好きなだけ繰り返す。
- 場にあるカードの値が$ X $なら、元のカードを捨てて、$ X $か$ (X + 1) \mod M $の値のカードを場に出す。
$ N \leq 2 \times 10 ^ 5, M \leq 10 ^ 9, 0 \leq A _ i \leq M $
考察
どういう場合がいいのか
明らかに、$ X $のカードが複数枚あるなら、実質全部出すことができる。
となれば、同じ種類のカードをまとめて、番号が連番(modのところで跳ぶ)のものを全部集計して、その連番部分で最大のものを取ればよい。あらかじめ全部の和は全部足し合わせておく。
実装上での技法
今回みたいにmodでつながっていれば系は、同じ配列をお知りにくっつけていくと楽。
1234->12341234
____ <-このように連続をうまく実装できる
あとは、普通に連続が続く、続かないならその時点で切って答えを更新。
だがここで忘れやすい2点が。
最後の更新
int v = 0; for(){ if(継続){ v += ???; } else { //ここで終わり vで答えを更新; 新たな連続部分を始めるにあたっての初期準備; } vで答えを更新;//忘れるな！！！ }
今回は同じものを2週させているので、これは発生しないが、2週させないものならば、最後にvで答えを更新を忘れるな！
連続区間の長さに制限を
悔しいながら今回何回も引っかかってしまった。
同じ配列$ X, Y, ... $をくっつけて長さ2倍の$ X, Y, ..., X, Y, ... $でmodでの番号ループを対応するなら、区間の長さをたかだか$ \mathrm{length}(X, Y, ...) $に制限する実装を書くべき。
今回の場合、例えば
5 5 0 1 2 3 4
の場合、全部一気にとれるので、そのまま2週目も取り始めて結果的に0 1 2 3 4 0 1 2 3 4と取ってしまう。
これの対策として以下の2つがある。
streakの長さに制限をつける。
これが一番やりやすいしミスらない。絶対に越えてはならない連続区間の長さを設けて、それを超えたら強制的に終了させる。
int streak_length = 0; for(;;){ if(streak_length > 所定の長さ){ goto end_streak; } ... end_streak:; //連続区間終了操作 }
やらかしてしまった時に出る異常値を最後で弾く
やらかしてしまった時に出る異常値は、今回では何週もしてしまうということで、全ての和が$ S $なら、2倍引かれて$ -S $となる。このように問題となる条件を毎回見つけて弾く。
一言
久しぶりに出たらめちゃくちゃレート溶けて青コーダーやめました。次で戻します。
ABC202-E Count Descendants (Blue-)
問題概要
サイズ$ N $の木が与えられる。次のクエリを$ Q $個処理せよ。
$ U, D $という値が与えられる。頂点$ U $を取って、根から距離が$ D $の頂点の個数を答えよ。
制約: $ N, Q \in [2, 2 \times 10 ^ 5], U \in [1, N], D \in [0, N - 1] $
考察
ダブリングで行ける？
LCAのこともあったのでダブリング的手法でいけるか？と思った。つまり、
node[i][j][k] := 頂点iから距離が(2^j)の頂点のk番目
みたいに保持させておいて、クエリごとに$ 101 _ {(2)} = 5 $ならば、
- 根から4マス先の頂点をリストに入れる。
- そのリストの中からそれぞれ1マス先を入れる。
で決めてみる。
しかし、ダブリングテーブル構築自体は$ O(N \log N) $だが、どうしてもQuery1回あたり$ O(N) $ほど最悪かかってしまう。
オイラーツアー
木に対して○○のテクをするといえばオイラーツアー。典型です。
この記事にいろいろな応用がある。maspyさんのやつ良い。
簡単にまとめると、
cnt = 0; void dfs(int now, int bef){ cntをメモ cnt++; for(子ども) dfs(子ども, now); cntをまたメモ cnt++; }
このように探索の始めと終わりにメモをする。DFSの性質上、ある頂点の2回のメモの値は$ b, e $ならば、子どもの頂点にまつわるメモの値は$ [b, e] $にちょうど入る。
また、オイラーツアーに直接関係あるわけではないが、$ b $をメモするときの何かしらの値を$ X _ b $、$ e $をメモするときのその値を$ X _ e $とすれば、$ X _ e $と$ X _ b $の差分を取れば、自分の子供全てに対しての操作を取得できる。
今回はどうするの？
今回の場合、オイラーツアーを知っていれば一発。
深さごとに$ b $に当たる値をメモして、そしてその同じ深さの中でソートされてれば(DFSされてるのでそもそもソートされてるけど)、 指定頂点の$ [b, e] $の区間内の$ b $に当たる数が、その指定の深さでの該当頂点の子どもの頂点の数に当たる。
これは二分探索lower_bound, upper_boundを使えば、全体で$ O(N \log N) $で解ける。
これはそもそも深さ的あり得ないものがあったら打ち切っていたけど無くても動きそう。
よりよい解法 クエリ先読み
さきほど、$ X _ e $と$ X _ b $を見れば、子供全てについて行った結果がわかると書いたが、今回は先読みしてクエリを各頂点にあらかじめ置いておくことによって、$ X _ e $が分かった時点で、メモしておいた$ X _ b $との差分を追うことによって、DFSをしながら無駄なくクエリに答えられる。
簡単にメモする、クエリを置くとか言っていたけど具体的な実装はコードみるとわかりやすい。
一言
ikefumyありがとう(定期)。課題解決通話ありがとう！
ABC202-E Count Descendants
問題概要
サイズ$ N $の木が与えられる。次のクエリを$ Q $個処理せよ。
$ U, D $という値が与えられる。頂点$ U $を取って、根から距離が$ D $の頂点の個数を答えよ。
制約: $ N, Q \in [2, 2 \times 10 ^ 5], U \in [1, N], D \in [0, N - 1] $
考察
ダブリングで行ける？
LCAのこともあったのでダブリング的手法でいけるか？と思った。つまり、
node[i][j][k] := 頂点iから距離が(2^j)の頂点のk番目
みたいに保持させておいて、クエリごとに$ 101 _ {(2)} = 5 $ならば、
- 根から4マス先の頂点をリストに入れる。
- そのリストの中からそれぞれ1マス先を入れる。
で決めてみる。
しかし、ダブリングテーブル構築自体は$ O(N \log N) $だが、どうしてもQuery1回あたり$ O(N) $ほど最悪かかってしまう。
オイラーツアー
木に対して○○のテクをするといえばオイラーツアー。典型です。
この記事にいろいろな応用がある。maspyさんのやつ良い。
簡単にまとめると、
cnt = 0; void dfs(int now, int bef){ cntをメモ cnt++; for(子ども) dfs(子ども, now); cntをまたメモ cnt++; }
このように探索の始めと終わりにメモをする。DFSの性質上、ある頂点の2回のメモの値は$ b, e $ならば、子どもの頂点にまつわるメモの値は$ [b, e] $にちょうど入る。
また、オイラーツアーに直接関係あるわけではないが、$ b $をメモするときの何かしらの値を$ X _ b $、$ e $をメモするときのその値を$ X _ e $とすれば、$ X _ e $と$ X _ b $の差分を取れば、自分の子供全てに対しての操作を取得できる。
今回はどうするの？
今回の場合、オイラーツアーを知っていれば一発。
深さごとに$ b $に当たる値をメモして、そしてその同じ深さの中でソートされてれば(DFSされてるのでそもそもソートされてるけど)、 指定頂点の$ [b, e] $の区間内の$ b $に当たる数が、その指定の深さでの該当頂点の子どもの頂点の数に当たる。
これは二分探索lower_bound, upper_boundを使えば、全体で$ O(N \log N) $で解ける。
これはそもそも深さ的あり得ないものがあったら打ち切っていたけど無くても動きそう。
よりよい解法 クエリ先読み
さきほど、$ X _ e $と$ X _ b $を見れば、子供全てについて行った結果がわかると書いたが、今回は先読みしてクエリを各頂点にあらかじめ置いておくことによって、$ X _ e $が分かった時点で、メモしておいた$ X _ b $との差分を追うことによって、DFSをしながら無駄なくクエリに答えられる。
簡単にメモする、クエリを置くとか言っていたけど具体的な実装はコードみるとわかりやすい。
一言
ikefumyありがとう(定期)。課題解決通話ありがとう！
パタヘネ第6版 第2章演習問題解答
6th editionについての解答。
解答がおかしいとかがありましたらSen(@nonpro3)のTwitterアカウントにDMやリプライ飛ばしてください。
大体ここにある。ほとんどそろっている。先駆者様ありがとうございます！
上で事足りると思うが、ここにもあるよ！
ただし、これは最新の6th editionではないので、下に対応表と乗ってない問題の回答を載せる。
| 6th edition | old |
|---|---|
| 2.1 | 2.1 |
| 2.2 | 2.2 |
| 2.3 | 2.3 |
| 2.4 | 2.4 |
| なし | 2.5 |
| なし | 2.6 |
| 2.5 | 2.7 |
| 2.6 | 2.8 |
| 2.7 | 2.9 |
| 2.8 | 2.10 |
| 2.9 | 2.11 |
| 2.10 | 2.12 |
| 2.11 | 2.13 |
| 2.12 | 2.14 |
| 2.13 | 2.15 |
| 2.14 | 2.16 |
| 2.15 | 2.17 |
| 2.16 | 2.18 |
| 2.17 | 2.19 |
| 2.18 | 2.20 |
| 2.19 | 2.21 |
| 2.20 | 2.22 |
| 2.21 | 2.23 |
| 2.22 | 2.24(少し違う) |
| 2.23 | 2.25 |
| 2.24 | 2.26 |
| 2.25 | 2.27 |
| 2.26 | 2.28 |
| 2.27 | 2.29 |
| 2.28 | 2.30 |
| 2.29 | 2.31 |
| なし | 2.32 |
| 2.30 | 2.33 |
| 2.31 | 2.34 |
| 2.32 | 2.35 |
| 2.33 | 2.36 |
| 2.34 | 2.37 |
| 2.35 | 2.38(全てじゃない) |
| 2.36 | なし |
| なし | 2.39 |
| なし | 2.40 |
| なし | 2.41 |
| なし | 2.42 |
| なし | 2.43 |
| 2.37 | 2.44 |
| 2.38 | 2.45?(少し違う) |
| 2.39 | 2.46 |
| 2.40 | 2.47 |
| 2.41 | なし |
| 2.42 | なし |
以下の者はすべて6th editionのもので新規追加された問題の回答。
2.22
2.22.1
jal命令は、J形式で、即値は32-6=26bit これで実際のPCで使用される値は、2進数に直すと末尾が00なので、26bitは2bit左へシフトして28bitとして扱う。そしてその際、上位4bitはプログラムカウンタの値そのままとして使って、変更しない。今回は0x 2000 0000なので上位4bitは変更されず、PCはjal命令を使っても、0x 2000 0000のまま。
2.22.2
beq命令は即値は16bit。実際は2bit左にシフトした18bitぶんだけPCをずらすことができる。この場合、即値の18bit相当分を32bitに符合拡張して、PCと足し合わせた範囲へ行ける。すなわち、0x 1FFF 0000 - 0x 2000 FFFF
2.35
問題文は\$t2について言及は一切ないが、上のブログを参考する限り、
レジスタ$t1にはアドレス0x10000000が保持されており，レジスタ$t2にはアドレス0x10000010が保持されているものとする．アドレス0x10000000に収められているデータ（16進数）は0x11223344であるとする．レジスタ$t2によって指されるアドレスには，どんな値が収められるか．
が本来の意味と思われる。
lbuは1バイトぶんだけ、下の1-8桁に入れる命令 なお上の24bitは0埋めされる。(lbなら符号拡張もされる)
2.35.1
ビッグエンディアンは、数字の上位桁がアドレスの小さい方になる。0x11223344なら、11側がアドレスが小さいので、スタート(アドレスが小さい左端)から数えて1バイトぶんを下1-8桁に入れるlbuは、0x00000011となる。それを$t2にロードしてるので、$t2にあるのは0x00000011。
2.35.2
リトルエンディアンは、数字の下位桁がアドレスの小さい方になっている。0x11223344なら、44側がアドレスが小さいので、lbuでロードする1バイトぶんは44となり、それは$t0では上1-8桁に入れる。よって$t2にあるのは0x44000000。
ここは確信をもって正解かどうかわからない。
2.41, 2.42
よくわからないです……(院試に出なさそうなのでスキップ)
