構築問題 メモ
構築の思考パターンメモです。主にはまやんさんの構築まとめに載っている問題をを埋めていきます。
2べきを考える
+1および×2の遷移を作成して任意の値を構築
問題
提出コード
既にある文字列に対して、先頭の文字を両端に追加する→×2
既にある文字列に対して、先頭の文字と異なる文字を両端に追加する→+1
の操作となります。
解説にもあるように、aTa|b|aTaのようなケースが作成できてしまうと、数が増えてしまうので、Tが回文とならないようにする必要があります。これは、文字の種類を3種類以上用意して、ローテーションで新しい文字を割り振ればOKです。
構築の実装は、一番上のビットから順番に見ていき、
今見ているビットが立っている→ビットを立てる(+1の操作)
今見ているビットが立っていない→ビットを立てない(操作なし)
を行い、その後で右のビットにうつる際に、×2の操作を行えば構築完了です。
のケースや一番最初に追加する文字の選択に気を付ければ終わりです。初めに1文字何か入れておけば問題ないです。
その他
ARC102 D - All Your Paths are Different Lengths
ARC102 D - All Your Paths are Different Lengths - ツバサの備忘録
までを上手く構築し、残りの
についてもそれを利用して構築します。
特徴のあるグラフをベースに考える
完全グラフ
Tenka1 Programmer Contest (2018) D - Crossing
Tenka1 Programmer Contest (2018) D - Crossing - ツバサの備忘録
完全グラフそのものです。
スターグラフ
ABC132 E - Friendships
問題
提出コード
スターグラフをまず構築した後に、問題の条件を満たすまで辺を追加しつづけます。
木
頂点
辺の単純連結無向グラフが与えられた場合に、適当な全域木を取って考えると見通しがよくなることがあります。
WUPC2019 C - Permutation City
再帰DFSをしつつ、葉の方から、今見ている頂点とその子に対して処理を行います。
AGC035 B - Even Degrees
問題
提出コード
こちらも同様、葉から見ていき、今見ている頂点の子の情報を集めた後、辻褄が合うように自身の状態を確定します。
ABC155 F - Perils in Parallel
問題
提出コード
前半の難しいパートを終えると、上の問題に帰着できます。
二部グラフ
日立製作所 社会システム事業部 プログラミングコンテスト2020 C - ThREE
問題
提出コード
適当に根を決めると、そこからの距離の偶奇で置くべき数字が変わってきます。
そこで二部グラフになっていることがわかり、あとは頂点数によって構築方法を場合分けします。
第一回日本最強プログラマー学生選手権-予選- D - Classified
二部グラフになればよく、頂点を決め打って奇数距離同士を結ぶ、偶数同士は別のレベルで結ぶ、を繰り返します。ビットを利用すると構築が楽。
XOR
Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix
構築の典型というよりかは、XORの典型を用いるとスムーズにいく、という感じでしょうか。
しいて言うなら、とりあえずシンプルに構築して、最後に微調整を行う という考えがポイントでしょうか…？
未分類
順列の和差昇順ペアを作成
差が昇順
のとき、
の偶奇で場合分け
E - Rotation Matching
やることはどちらも同じで、前半部分で差が偶数のペア、後半部分で差が奇数のペアを作成する和が昇順
こちらはの偶奇で場合分け(
でペアを作成)
E - Non-triangular Triplets
偶数の場合はという形でならぶ(奇数は等差)
TODO 昔の記事をまとめる
