精進メモ 2021/09/06~

Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma

suzuken君に投げられました。最初の実装に15分、そこからバグを取るのに15分でした。
セグ木に必要な要素をのせてがんばります。
答え、左端の値、右端の値、左端から続く広義単調増加な列の長さ、右端から続く広義単調増加な列の長さ、全体が単調増加かどうかのフラグ
を持たせると計算できます。
[1,2,3,4]と[5,6,1,2]をマージする場合に注意。

ICPC Central Russia Regional Contest (CRRC 18)

難読問題セットでした。つらい。

B. Gremlins attack!

通れるようになる家を順にUnionfindで繋いでいき、端とグレムリンの家が連結になるまで繰り返します。

D. We were trying to share an orange ...

全探索すればいいのですが、OEISが見つかったので埋め込みです。
多倍長が必要なのでpythonでした。

E. Hanoi Tower

愚直にシミュレートすればOKです。実はもっと簡単らしいです。

H. A self-describing sequence

他のチームは最近既出で秒殺だったらしいです。問題文が読めず無限に時間が溶けました。
7以上は似たような構築方法でいけるので、6までは埋め込みです。

J. R u really ready?

= p]の文字目、の文字目でちょうど終わりになるようなパターンの適用方法があるか？でDPしました。バチャ込みで現時点FAっぽいです。

ABC218

最近2桁順位が安定している気がします。対してARCは…
Aでななめよみした問題文が全然違うものになっており1ペナしました。
相変わらずHは解けません。

C - Shapes

一番難しいです。90度回転の関数を作って、チェック→回転→チェック…と4回繰り返します。
チェックは、左上の位置をS,Tそれぞれメモして、そこからチェックします。
左上の位置から右下方向だけ見てしまい、サンプルがずっとあっていませんでした(サンプル1のようなケースで落ちます)

D - Rectangles

縦の直線を全部作り、そこから数を数えました。
直線の端点のy座標のペアごとに個数を数え、そこから2つ選ぶパターンを答えに追加すればOKです。

E - Destruction

基本的に最小全域木を行い、使わなかったコストの総和が答えです。 コストが負の辺は全て繋いでおきます。残りはコストの昇順に辺を見ていきます。

F - Blocked Roads

全ての辺が使える状態での距離を求めます。距離は以下になっているはずです。つまり、最初の状態でのルートに含まれる辺を取り除く場合のみ、愚直にBFSで最短距離を計算すれば良いです。 面白かったです。

G - Game on Tree 2

最小値、最大値を選ぶパートはよくあるゲームの木DPと同じです。
中央値は、値を座圧し、BIT上で二分探索することで求められます。

AOJ-ICPC

1401 Estimating the Flood Risk

これ難しかったです…(本番、自分担当にならなくてよかった)
すでに決まっている位置の値に対し、全てのマスについて、Manhattan距離を足し引きしたものをメモすることで、それぞれのマスでの上限と下限が求まります。
あとは下限を全て足すと答えです。

2783 Parentheses

()()()...の状態から一番右側にある開き括弧を動かしていくと辞書順最小のものが作成できます。
それぞれの長さで作れる最大値は決まっているので、長さを決めた後は、答えと一致するように移動させればOKです。

2723 Surface Area of Cubes

外側の表面積を足します。その後、6×抜く個数を足しておきます。
ここから、余分に足した値を引いていきます。まずは、元々外側にある立方体を抜くケースで、これは表面に存在する面×2を引きます。
そして、抜く立方体同士が接している場所で、ここも接している箇所×2を引けばよいです。

2684 RLE Replacement

2乗が通るので、愚直に一致する箇所を調べ、置換すれば良いです。
置換元の文字が1種類の場合に注意です(この場合、置換前の文字列の長さが長い時は置換先の文字列より後ろに残ります)。

2599 Idempotent Filter

19個のマスの01パターンを全て試し、2回適用することを愚直にシミュレートします。

2857 Tournament Chart

構文解析です。形がかなり決まっているので、実装はかなり軽いです。
優勝者の勝利回数チェックが抜けており1ペナしました。

2858 Prime-Factor Prime

2から順番に、で割れる場所を割っていきます。の素数まで見ればOKです。
素因数の倍数だけきちんと見るようにすれば、調和級数によりで収まります(長さが )。
残った数が1より大きければ素因数をもう一つ足し、あとは問題の条件に合ってるかどうか判定していけばいいです。
難しかったですが面白いですね。

2913 Prime Routing

それぞれの頂点に偶数距離で到着する場合と奇数距離で到着する場合の最小値を両方メモします。
偶数距離が2であれば答えは2ですし、そうでなければ、奇数距離以上の最小の素数が答えです。