精進メモ 2021/03/22~
更新は飽きたらやめます。クオリティも気分次第です。
- Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round) C. Skyline Photo
- ARC115 E - LEQ and NEQ
- ARC115 D
- ARC111 E - Simple Math 3
- AGC052 B - Tree Edges XOR
- AGC050(Good Bye rng_58 day 1) C - Block Game
- ARC075 F - Mirrored
- ARC093 E - Bichrome Spanning Tree
- キーエンス プログラミング コンテスト 2021 E - Greedy Ant
- ABC197
Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round) C. Skyline Photo
問題
提出コード
番目の写真まで取り終えた時点でのスコアの最大値
として最大化します。
という遷移ができるので、これを遅延セグ木で高速化します。
DP配列を遅延セグ木にし、そのノードには、の値、今番目を見ている際、をまとめて一枚に収めるときに加算されるの値、を持たせます。
区間更新で、を更新します(どこからどこまで更新するかは、二分探索で求められます)。
DPの遷移を、の最大値を取るような区間取得と遅延セグ木の set_val()
で更新します。
あとはこれを繰り返せば、が答えです。
の更新に使う作用素の単位元をにしていたため、が存在するケースで壊れてシステス落ちしました。
ARC115 E - LEQ and NEQ
問題
提出コード
↑の問題とほぼ同じ形で解けます。
番目の要素まで見て、違反が少なくとも回(偶奇)あるような数列のパターン数、とすると、包除原理で答えが求められます。
遷移は、
となります(は偶奇を適宜調整します)。
の部分は、↑の問題と同じ形をしているので、全く同じ更新ができます。DPの値も、こちらは数え上げですが、を総和に置き換えてあげれば大丈夫です。
の値がとなるように区間和を取っていく必要がありますが、これはの偶奇で、DP配列そのものを01反転させてしまえば、綺麗に区間和が取れるようになります。
あとは遅延セグ木にのせてあげることで、この問題を解くことができます。
ARC115 D
問題
提出コード
コンテスト中にDFS木を取った直後にEへ逃亡した問題です。
まず、連結成分ごとに個数とパターンを数えていけば良いです。連結成分ごとのマージは、二乗の木DPの要領で計算量が落ちるので、3重ループのDPを書けば良いです。
それぞれの連結成分は、DFS木を取って、元の無向グラフとDFS木の差を見てみる(辺の使う/使わないを全探索する実験コードを書けばいいです)と、木の状態から、
だけ増えていることがわかります(解いた際は証明していないですが…)。
木の場合は、頂点以下の部分木について、に直接つながっている辺で使った本数が (偶奇)であり、次数が奇数の頂点が個
というDPを計算すればよいです(については、親に繋がる辺を使うかどうか、というフラグで利用する場合もあります)。
あとは、先ほどの冪乗をかけてあげた後、マージすれば答えがもとまります。
ARC111 E - Simple Math 3
問題
提出コード
の場合、答えでカウントされることはありません。
とすると、答えは未満です。
この範囲で、答えとしてカウントされない条件を見てみると、
です。
この値が2以上ズレることはありません(上記の条件に反するため)。
よって、取り得るについて、上記の不等式の差があるかどうかを見ればよいのですが、その個数は
となります。これをから引けば答えになります。
AGC052 B - Tree Edges XOR
問題
提出コード
次数が1の頂点を根とし、それぞれの頂点にパスに含まれる数字の総XORを書き込むことにします。
そうすると、根に繋がる辺以外を選んだ場合、根以外の頂点にある数字をスワップする操作に対応します。この時点で、どの頂点に数字があるか、は関係なくなり、数字の集合が目標のものと一致すればいいことがわかります。
そして、根に繋がる唯一の辺を選んだ場合、その辺に繋がっていない全頂点の値を、元の値を今選んだ辺の値とのXORに置き換える、という操作を行います。
結局、集合A,Bが与えられるので、以下の操作を任意回数行い、AをBと一致させることができるかどうか判定する問題となります。
- Aから要素を一つ選ぶ。他の全要素について、選んだ要素とのXORで置き換える。
ここで、が奇数なので、集合の要素は、根の頂点を除くと個あります。このことから、答えは以下のようになります(証明をする際にこの偶奇がきいてきます)。
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で割る回数が、最後から数えて置いたブロックを置いた回数-2と一致します。
よって、22回ほどブロックを置いた時点で、先ほどのの値が1にならないパターンはなくなります。このが1になれば勝ちが決まるので、後ろから見ていき、決まった時点で除外してしまえば、常に勝利が決まっていないパターンのみを考えられそうです。は、ブロックを置いた回数ごとに独立に評価できるため、とても数えやすくなります。
後ろから文字目まで見終えて、回ブロックを置き、まだ勝利が確定していない(さきほどのが1でない)パターン数
とします。
の場合、未満で B
が既に出ていたら、それ以外では B
, ?
の際にとなります。
それ以外の場合、今回置いたブロックで勝利が確定するには、一つ前に置いた文字番号との距離が文字以下であればよいです。
そのため、その範囲にあるようなの総和を取ってきて、答えに加算してあげます(答えの部分は、 ?
が来るたびに2倍します)。
それ以前に置いたブロックが一つ前の場合は、勝利が確定しないので、に加算してあげます。
直近のB
の文字よりも手前にあるものを加算しないように注意します。
あとは、総和の部分を累積和で高速化してあげれば、でこの問題の答えがわかります。
-2があるせいで、ブロックを置く回数が22回であることを忘れ、20までの探索にしてペナを出しました。こういうミスを減らしたいです。
ARC075 F - Mirrored
問題
提出コード
初手の方針を外して大変な目に…
桁数を固定することを考えます。
abcde
、のような数字列があった際には、
となればよいです。
これは、のように式変形できます。
どのような長さでも、これに似た形に変形でき、全て9、0からできる数字の係数がついています。そのため、が9の倍数でなければ答えはになります。
が9の倍数の場合、先ほどの式の全てを9で割ると、係数は01からなる数字になります。こうすると、下の桁から愚直に決めやすくなります。
最下位の数字に影響するのは、長さが5の場合、のみです。そのため、がの下一桁と一致している必要があります。
これを決めると、下から2番目の桁については、、のみが影響しますが、についてはもう値を決めてあるので、のみを考えればよくなります。この際、について考えられる数字は2パターンしかありません(例えば、2と-8、のように、ある値か、の2パターンです)。これを、今決めた桁数の半分まで繰り返すと、それぞれの桁について、正にするか/負にするかのビット全探索ができるようになります。
あとは、作成した数字列が本当にに一致するかどうかをチェックすれば、答えが求まります。最上位のみ、0が使えないコーナーケースにも気を付ける必要があります。
実装自体は丁寧にサクっとかけた気がするので良かったです。
ARC093 E - Bichrome Spanning Tree
問題
提出コード
ここ一週間で解いた問題の中では一番解きやすかったです。天才パートが少なめ?
白黒を無視すると、最小全域木そのものになるので、まずはグラフ全体の最小全域木をベースに考えていきます。このときの重さの総和をとします。
のとき、通りの塗り方があります。最小全域木につかわれる辺で少なくとも1つずつ白黒を含むように塗り、それ以外の辺はどちらでも自由に塗ることができます。
それ以降、ある辺を最小全域木に含めたい、とします。すると、
少なくとも元々の最小全域木は全て同じ色で塗る必要があります。こちらを黒で塗り、新しく入れる辺を白で塗ることにしましょう(最後に2倍すれば逆も考慮できます)。
このとき、新しくの辺を追加することにすると、から新しく増えるコストは以下のようになります:
後者の部分は、前計算、本編で求めることができます。
上記のコストが今追加する辺よりも小さいものがある場合、その辺も黒に塗らなければなりませんが、自分より大きい辺については、自由に塗ることができます。
ということで、上記のコストで新たに辺をソートします。その後、にそのコストを追加した際に、と一致するものがあれば、を答えに追加していけば良いです。
キーエンス プログラミング コンテスト 2021 E - Greedy Ant
問題
提出コード
全然本質に気づけなくて悔しいです…
すぬけ君の操作は、「蟻と同様に区間の両端にあるアメしか取れないが、与えられた回数、好きなときに順番を割り込み取ることができる」とすることができます。回数は、初期で1回、蟻がアメを取るたびに1回増えます。
そうすると、
次に取れる両端のアメがで、すぬけ君が回割りこめるとき、そこから操作をして得られるポイントの最大値
というDPを考えると、すぬけ君、蟻共にのどちらかのアメを取る操作のみ考えれば良いので、この問題を解くことができます。
この形のDP自体は考えてみたのですが、そもそもすぬけ君の操作の言い換えができていなかったので、なかなか解くことができませんでした。
ABC197
バチャ。48分ノーペナ全完で50位ちょっとくらい相当でした。
問題
提出
C - ORXOR
DFSよりbit全探索の方が楽だと思い、そちらにしました。本当は個の区切りの部分を探索しないといけませんが、と書くのが面倒だったので、配列の右端にも区切り線があることにしてしまいました(最後の部分はあってもなくても、0のXORをするかしないかなので特に答えは変わりません)。
答えの比較の部分で、使う変数のミスをしてしまいタイムロスしました。
D - Opposite
幾何。中点と、中点からへのベクトルを求め、ベクトルをだけ反時計回りに回転させます。そして、そのベクトルを中点に足してあげれば答えです。
main関数にべた書きしてしまいましたが、どう書くのが綺麗なのでしょうか…
E - Traveler
それぞれの色のボールについて見ると、右端→左端か、左端→右端に移動するどちらかの2パターンのみを考えればよいので、あとはこの2通りでDPをします。左端、右端の座標を抽出(参照)するパートはありますが、基本的にはシンプルに書けました。
初期状態、最終状態も、"座標0にただ一つのボールがある"と考えると場合分けが不要になり楽になります。
バチャ中では左端、右端の情報をペアで書きましたが、ペアではなく長さ2のarrayで持っておけば、添え字もそのままループで書けたのでもっと楽に書けます。
F - Construct a Palindrome
両端から同じ文字を使う辺を同時に選び、BFSで距離の最短を求めていけば良いです。DPの添え字は通りですが、遷移はでちょっと不思議な問題でした。面白かったです。
両端から探索する方針を初手で考え、DPにすることを考えず捨ててしまいタイムロスをしましたが、はやい段階で戻ってこれたので助かりました。