精進メモ 2021/09/13~ - ツバサの備忘録

AOJ-ICPC、350が埋まったのでだんだん辛くなってきました。

AOJ-ICPC
- 1399 Sixth Sense
- 1337 Count the Regions
Northern Eurasia Finals Online 2020
ABC219
ARC126

AOJ-ICPC

1399 Sixth Sense

suzuken君に投げられました。
辞書順が無ければソートして小さい方から貪欲に詰めていってOKです。
そのときのスコアを計算する関数を作っておきます。
答えの数列を前から決めていきます。
ある箇所について、まず $p_{i}$ より大きいか、そうでないかを選択します。どちらも、条件を満たす中で最小のものを選びます。
そのときのスコアを計算し、最終的に大きくなる方を選びます。同じであれば辞書順が大きくなる方です。
その後、条件を満たすなかで辞書順が最大になるような値を探します。
ここは二分探索で求めることができます。
これを繰り返すことで答えが求まります。

1337 Count the Regions

$n \leq 50$ を完全に失念していました。
座標圧縮すると、マス目上でUnionfindを行って連結成分の個数を数える問題になります。

Northern Eurasia Finals Online 2020

絶不調でした。

Geometrical Combinatorics

諸悪の根源です。一問目に開いたのが運のつきでした。
斜めの直線ごとに見ていけば、公式を使って計算できるはず…なのですが、結局最後まで通りませんでした。誤差なのか、考慮もれなのかはいまだわかってないです。

A. Almost Balanced Tree

2を優先的に使います。
2と1の個数を基本的に半分になるように分けます。ズレる部分は1を移動させて微調整します。

Lookup Performance

ある頂点にいるとき、クエリ $L,R$ に対して再帰を行わない条件は、今いる頂点のminとmaxが $(l,r)$ であるとき、
$R \lt l, r \lt L, L \leq l \leq r \leq R$ のいずれかの条件を満たすことが必要です。
また、ある頂点でこれらを満たした時、その部分木における頂点全てが上記の条件を満たします。
ということで、(上記の条件を満たさない頂点の個数)×2 + 1が答えです。
1,2番目の条件は簡単に数えることができます。
3番目は、suzuken君にwavelet treeで殴ってもらいました。

ABC219

爆死しました。ICPCチームメンバーが温まっているのでヨシとします。

D - Strange Lunchbox

$dp[i][j] = i$ 個使って $j$ 個の鯛焼きを買えるときに購入できるたこ焼きの最大値、としてDPをします。
初期値を間違えて2ペナしました…

E - Moat

あなぽこは含むものだと思っていたら、Clarで含みませんと言われて泣きました。
結局そこからバグり続けて終わりました。
囲まれているかどうかをビット全探索すればOKです。
村を全て含むか、連結であるかどうかは簡単に判定できます。後者はUnionfindでＯＫです。
あなぽこ判定は、白のマスが外側と全て繋がっているか判定すればいいです。途中から実装をしたため、手抜き実装をしたら

のケースで落ちるような実装になっていました。

F - Cleaning Robot

日曜日に解きました。
文字列一回分を1セットとし、到着するマス目を洗い出します。
そして、1セット単位で移動する距離 $(p,q)$ も計算します。
これらが共に0であった場合は1セット分のマス目の個数が答えです。
$p,q$ のうち片方が0であった場合( $p$ が0であるとします)、重なるパターンは、到着するマス目 $(a,b),(c,d)$ に対し、 $(a,b \mod{q})$ と $(c,d \mod {q})$ が一致し、 $b / q + i = d / q + j$ となる場合です( $i,j$ は操作回数)。
なので、 $(a,b \mod{q})$ ごとに $b / q$ をメモしていき、 $[b/q,b/q + K)$ の区間の共通部分を全体で考え、区間の幅を計算すると答えになります。
$p,q$ どちらも0でなかった場合は、
$(a \mod p,b \mod q,a/x - b/x)$ に対する $a/x$ をメモすると、同様の計算で答えが求まります。

ARC126

不調の後には好調がやってきます。

A - Make 10

FAまであと少しでした。
長さ3のものは優先的に使います。
それが終わったら、4を優先的に使います。
あとは2だけで作って終わりです。

B - Cross-free Matching

LISに気づきませんでした。
$dp[i][j] = i$ 個めの線分まで見終えて、最後に選んだ線分の $a$ が $j$ であるときに選べる線分の最大値
とします。 $a_{i}$ で線分をソートしておくと、上記のDPをセグ木で更新できるようになります。
$a_{i}$ が同じものは同時に更新する必要があります。

C - Maximize GCD

とても好きな問題です。 $M = \max(A_{i})$ とすると、全部の要素を $M$ 以上にできる場合は答えが簡単に求められます。余った操作回数を均等に割り振るようにすればよいです。
そうでない場合を考えます。
$\gcd$ が $x$ にできるかどうかを考えた時、それぞれの要素は $x$ の倍数でなければなりません。 $A_{i}$ について、その値以上の $x$ の倍数は一意に定まり、 $A_{i}$ をソートしておくと、目標となる $x$ の倍数が同じ要素については連続して並んでくれます。
ということで、境界を二分探索やしゃくとりで求められれば、必要な操作回数が求まります。
$x$ の倍数のみ調べるので、全体で調べる回数は調和級数で収まります。

D - Pure Straight

はじめに嘘DPを書いていて時間をロスしました。
$dp[i][S] = i$ 番目が右端で、集合 $S$ に含まれる要素が $i$ 番目から順に左側にならぶように操作したときの操作回数の最小値、とします。ただし、 $i$ 番目までの要素のみを用います。このDPは、 $i$ 番目の要素を用いない場合
$dp[i][S] = dp[i-1][S] + |S|$ という遷移になります。
用いる場合、 $dp[i-1][S \setminus \{i\}]$ に、 $i$ 番目の要素を正しい位置へ移動するコストを足したもので更新させます。
これを、右側のみの要素のみで構築するパターンについてもどうようにDPで計算します。
最後に、両方のパターンをマージして、ちょうど $S$ が全体になるようなものを計算し、答えを求めればOKです。