ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

精進メモ 2021/03/22~

更新は飽きたらやめます。クオリティも気分次第です。

Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round) C. Skyline Photo

問題
提出コード
dp[i] = i番目の写真まで取り終えた時点でのスコアの最大値
として最大化します。
dp[i] = \max (dp[j] + b_{k}) (ただし, \min (h_{j+1} \ldots h_{i}) = h_{k})
という遷移ができるので、これを遅延セグ木で高速化します。
DP配列を遅延セグ木にし、そのノードには、dp_{j}の値、今i番目を見ている際、[j,i]をまとめて一枚に収めるときに加算されるb_{k}の値、dp_{j} + b_{k}を持たせます。
区間更新で、b_{k}を更新します(どこからどこまで更新するかは、二分探索で求められます)。
DPの遷移を、dp_{j} + b_{k}の最大値を取るような区間取得と遅延セグ木の set_val() で更新します。
あとはこれを繰り返せば、dp_{n}が答えです。
b_{k}の更新に使う作用素単位元0にしていたため、b_{i} = 0が存在するケースで壊れてシステス落ちしました。

ARC115 E - LEQ and NEQ

問題
提出コード
↑の問題とほぼ同じ形で解けます。
dp[i][j] = i番目の要素まで見て、違反が少なくともj回(偶奇)あるような数列のパターン数、とすると、包除原理で答えが求められます。
遷移は、
dp[i][j] = \sum dp[k][p] \times min(A_{j + 1} \ldots A_{i})
となります(pは偶奇を適宜調整します)。
min(A_{j + 1} \ldots A_{i})の部分は、↑の問題と同じ形をしているので、全く同じ更新ができます。DPの値も、こちらは数え上げですが、\maxを総和に置き換えてあげれば大丈夫です。
jの値が0,1,0,1...となるように区間和を取っていく必要がありますが、これはiの偶奇で、DP配列そのものを01反転させてしまえば、綺麗に区間和が取れるようになります。
あとは遅延セグ木にのせてあげることで、この問題を解くことができます。

ARC115 D

問題
提出コード
コンテスト中にDFS木を取った直後にEへ逃亡した問題です。
まず、連結成分ごとに個数とパターンを数えていけば良いです。連結成分ごとのマージは、二乗の木DPの要領で計算量が落ちるので、3重ループのDPを書けば良いです。
それぞれの連結成分は、DFS木を取って、元の無向グラフとDFS木の差を見てみる(辺の使う/使わないを全探索する実験コードを書けばいいです)と、木の状態から、

  • 2^{(減らした辺の本数)}

だけ増えていることがわかります(解いた際は証明していないですが…)。
木の場合は、dp[i][j][k] = 頂点i以下の部分木について、iに直接つながっている辺で使った本数がj (偶奇)であり、次数が奇数の頂点がk
というDPを計算すればよいです(jについては、親に繋がる辺を使うかどうか、というフラグで利用する場合もあります)。
あとは、先ほどの冪乗をかけてあげた後、マージすれば答えがもとまります。

ARC111 E - Simple Math 3

問題
提出コード
(C-B)i \geq Dの場合、答えでカウントされることはありません。
N =  \lceil \frac{D}{C-B} \rceilとすると、答えはN未満です。
この範囲で、答えとしてカウントされない条件を見てみると、
\lceil \frac{A + Bi}{D} \rceil \lt \lceil \frac{A + Ci}{D} \rceil
です。
この値が2以上ズレることはありません(上記の条件に反するため)。
よって、取り得るiについて、上記の不等式の差があるかどうかを見ればよいのですが、その個数は
\displaystyle \sum_{i =0}^{N-1} \left\lceil \frac{Ci + A}{D} \right\rceil - \sum_{i =0}^{N-1} \left\lceil \frac{Bi + (A-1) }{D} \right\rceil
となります。これをN-1から引けば答えになります。

AGC052 B - Tree Edges XOR

問題
提出コード
次数が1の頂点を根とし、それぞれの頂点にパスに含まれる数字の総XORを書き込むことにします。
そうすると、根に繋がる辺以外を選んだ場合、根以外の頂点にある数字をスワップする操作に対応します。この時点で、どの頂点に数字があるか、は関係なくなり、数字の集合が目標のものと一致すればいいことがわかります。
そして、根に繋がる唯一の辺を選んだ場合、その辺に繋がっていない全頂点の値を、元の値を今選んだ辺の値とのXORに置き換える、という操作を行います。
結局、集合A,Bが与えられるので、以下の操作を任意回数行い、AをBと一致させることができるかどうか判定する問題となります。

  • Aから要素を一つ選ぶ。他の全要素について、選んだ要素とのXORで置き換える。

ここで、Nが奇数なので、集合の要素は、根の頂点を除くとN-1個あります。このことから、答えは以下のようになります(証明をする際にこの偶奇がきいてきます)。
A,B全要素のXORに注目すると、値が一致している場合、既にAとBが一致していなければ、答えが NO になります。
そうでない場合は、そのXORの差分がAに存在している場合、その要素を選択して一致するかどうか試すのが、一致させる唯一の方法になります。これでも一致しない、もしくはそもそも差分がAの要素にない場合はNOになります。
A,Bの構築はdfsで行うことができるので、あとは総XORを取って確認すればOKです。

AGC050(Good Bye rng_58 day 1) C - Block Game

問題
提出コード
文字列のリバースしてる/してないが記事の中でぐちゃぐちゃになっている気がします
まず、ブロックを置く回数が2^{22}回以上になると、確定で勝てます。
すぬけ君は、今動ける範囲のだいたい中心に移動するのが最適で、次にブロックを置いた後動ける範囲は、
\min(今動ける範囲の半分, 先ほどブロックを置いてから行われた操作の回数)
になります。この評価が入れ子になり、最初に動けた範囲がa、次にブロックを置くまでに行われた操作回数がb回、その次がc回だとすると、これらの操作が終わった後で動ける範囲は
\min(c,\left\lceil \frac{\min(b,\lceil \frac{a}{2} \rceil)}{2} \right\rceil)
となります。少し変形すると、
\min(c,\left\lceil \frac{b}{2} \right\rceil, \left\lceil \frac{\left\lceil \frac{a}{2} \right\rceil}{2} \right\rceil)
となり、後ろから見た際に、2で割る回数が、最後から数えて置いたブロックを置いた回数-2と一致します。
よって、22回ほどブロックを置いた時点で、先ほどの\minの値が1にならないパターンはなくなります。この\minが1になれば勝ちが決まるので、後ろから見ていき、決まった時点で除外してしまえば、常に勝利が決まっていないパターンのみを考えられそうです。\minは、ブロックを置いた回数ごとに独立に評価できるため、とても数えやすくなります。
dp[i][j] = i後ろから文字目まで見終えて、j回ブロックを置き、まだ勝利が確定していない(さきほどの\minが1でない)パターン数
とします。
j = 1の場合、i未満で Bが既に出ていたらdp[i][1] = 0、それ以外では B, ?の際にdp[i][1] = 1となります。
それ以外の場合、今回置いたブロックで勝利が確定するには、一つ前に置いた文字番号との距離が2^{j-2}文字以下であればよいです。
そのため、その範囲にあるようなdp[k][j-1]の総和を取ってきて、答えに加算してあげます(答えの部分は、 ? が来るたびに2倍します)。
それ以前に置いたブロックが一つ前の場合は、勝利が確定しないので、dp[i][j]に加算してあげます。
直近のBの文字よりも手前にあるものを加算しないように注意します。
あとは、総和の部分を累積和で高速化してあげれば、O(N \log N)でこの問題の答えがわかります。
-2があるせいで、ブロックを置く回数が22回であることを忘れ、20までの探索にしてペナを出しました。こういうミスを減らしたいです。

ARC075 F - Mirrored

問題
提出コード
初手の方針を外して大変な目に…
桁数を固定することを考えます。
abcde 、のような数字列があった際には、
edcbe - abcde = Dとなればよいです。
これは、9999(e-a) + 990(d-b) = Dのように式変形できます。
どのような長さでも、これに似た形に変形でき、全て9、0からできる数字の係数がついています。そのため、Dが9の倍数でなければ答えは0になります。
Dが9の倍数の場合、先ほどの式の全てを9で割ると、係数は01からなる数字になります。こうすると、下の桁から愚直に決めやすくなります。
最下位の数字に影響するのは、長さが5の場合、1111(e-a)のみです。そのため、e-aDの下一桁と一致している必要があります。
これを決めると、下から2番目の桁については、e-ad-bのみが影響しますが、e-aについてはもう値を決めてあるので、d-bのみを考えればよくなります。この際、d-bについて考えられる数字は2パターンしかありません(例えば、2と-8、のように、ある値Xか、X-10の2パターンです)。これを、今決めた桁数の半分まで繰り返すと、それぞれの桁について、正にするか/負にするかのビット全探索ができるようになります。
あとは、作成した数字列が本当にDに一致するかどうかをチェックすれば、答えが求まります。最上位のみ、0が使えないコーナーケースにも気を付ける必要があります。
実装自体は丁寧にサクっとかけた気がするので良かったです。

ARC093 E - Bichrome Spanning Tree

問題
提出コード
ここ一週間で解いた問題の中では一番解きやすかったです。天才パートが少なめ?
白黒を無視すると、最小全域木そのものになるので、まずはグラフ全体の最小全域木をベースに考えていきます。このときの重さの総和をBとします。
B = Xのとき、(2^{N-1} - 2) \times 2^{M - N + 1}通りの塗り方があります。最小全域木につかわれる辺で少なくとも1つずつ白黒を含むように塗り、それ以外の辺はどちらでも自由に塗ることができます。
それ以降、ある辺を最小全域木に含めたい、とします。すると、
少なくとも元々の最小全域木は全て同じ色で塗る必要があります。こちらを黒で塗り、新しく入れる辺を白で塗ることにしましょう(最後に2倍すれば逆も考慮できます)。
このとき、新しく(u,v,w)の辺を追加することにすると、Bから新しく増えるコストは以下のようになります:
w - (最小全域木のu,vパスの中で最大の辺のコスト)
後者の部分は、前計算O(NM)、本編O(1)で求めることができます。
上記のコストが今追加する辺よりも小さいものがある場合、その辺も黒に塗らなければなりませんが、自分より大きい辺については、自由に塗ることができます。
ということで、上記のコストで新たに辺をソートします。その後、Bにそのコストを追加した際に、Xと一致するものがあれば、2^{自分よりコストが大きい辺の本数} \times 2を答えに追加していけば良いです。     

キーエンス プログラミング コンテスト 2021 E - Greedy Ant

問題
提出コード
全然本質に気づけなくて悔しいです…
すぬけ君の操作は、「蟻と同様に区間の両端にあるアメしか取れないが、与えられた回数、好きなときに順番を割り込み取ることができる」とすることができます。回数は、初期で1回、蟻がアメを取るたびに1回増えます。
そうすると、
dp[l][r][k] = 次に取れる両端のアメがl,rで、すぬけ君がk回割りこめるとき、そこから操作をして得られるポイントの最大値
というDPを考えると、すぬけ君、蟻共にl,rのどちらかのアメを取る操作のみ考えれば良いので、この問題を解くことができます。
この形のDP自体は考えてみたのですが、そもそもすぬけ君の操作の言い換えができていなかったので、なかなか解くことができませんでした。

ABC197

バチャ。48分ノーペナ全完で50位ちょっとくらい相当でした。
問題 提出

C - ORXOR

DFSよりbit全探索の方が楽だと思い、そちらにしました。本当はN-1個の区切りの部分を探索しないといけませんが、N-1と書くのが面倒だったので、配列Aの右端にも区切り線があることにしてしまいました(最後の部分はあってもなくても、0のXORをするかしないかなので特に答えは変わりません)。
答えの比較の部分で、使う変数のミスをしてしまいタイムロスしました。

D - Opposite

幾何。中点と、中点からp_{0}へのベクトルを求め、ベクトルを\frac{2 \pi}{N}だけ反時計回りに回転させます。そして、そのベクトルを中点に足してあげれば答えです。
main関数にべた書きしてしまいましたが、どう書くのが綺麗なのでしょうか…

E - Traveler

それぞれの色のボールについて見ると、右端→左端か、左端→右端に移動するどちらかの2パターンのみを考えればよいので、あとはこの2通りでDPをします。左端、右端の座標を抽出(参照)するパートはありますが、基本的にはシンプルに書けました。
初期状態、最終状態も、"座標0にただ一つのボールがある"と考えると場合分けが不要になり楽になります。
バチャ中では左端、右端の情報をペアで書きましたが、ペアではなく長さ2のarrayで持っておけば、添え字もそのままループで書けたのでもっと楽に書けます。

F - Construct a Palindrome

両端から同じ文字を使う辺を同時に選び、BFSで距離の最短を求めていけば良いです。DPの添え字はN^{2}通りですが、遷移はO(M^{2})でちょっと不思議な問題でした。面白かったです。
両端から探索する方針を初手で考え、DPにすることを考えず捨ててしまいタイムロスをしましたが、はやい段階で戻ってこれたので助かりました。