2019-2020 ACM-ICPC Latin American Regional Programming Contest バチャ参加記

Dashboard - 2019-2020 ACM-ICPC Latin American Regional Programming Contest - Codeforces

なんか解法書こうと思ったんですけど時間かかりそうなのでそこは暇だったらにします
しろくんとsuta君と出ました。

流れ

開始後

僕がAから、suta君がDから、しろくんがMから読むことになりました。順位表からもMがまず解けそうということで、しろくんがそのままACです。
続いて、Eも解けそうということで、suta君がそのままACしました。
suta君がEの実装をしている間に、僕としろくんはGの考察をしていました。
じつは、Gはほぼ似たような問題を解いたことがあり、そこでsuffix arrayとlcpの使い方を一応学んでいたので、頑張って思い出しました。
そのままGをACしました。

https://t.co/k5zMqIA5ng

今日のGの簡単ばーじょんです、復習していてよかったぁ
— ツバサ (@emtsu_ba) 2020年2月12日

僕がGの実装をしている間に、2人がIの考察を行い、Gの実装と平行してIも実装してもらっていたため、直後にIもACしました。

中盤～終盤

次に解けそうなのがK, Lだろう、ということでsuta君がLの読解をしている間に僕としろくんがKを考察しました。
しろくんが「因数分解できたらいいですよね」みたいな感じのことを言い、
$(x-a)(x-b)...$ という式を見せてきたときに僕がいい感じに閃き、解法を思いつきました。
同時にバチャを並走してくださっていたチームメンバーのツイートでもちらほら見かけた、「 $2^{63}$ 未満になることが保証されている」を読み間違えて「 $2^{63}$ 未満にしなければいけない」にした結果、時間を食いましたが無事AC。
Lは、suta君が問題の読解を終えて聞いたところ、これのちょっとした応用ですね～、つい最近講義でやりました！って言いつつ自分が実装をしました。

最後は、皆でFをやっていました。
考察は終わった(一応コンテスト後に通しました)のですが、実装が残り5分しかなくて間に合いませんでした。
途中、DPが3乗(残り個数と、1つ隣の高さを状態に持たせる)から落ちない～って言っていて、3人でEDPCの雑談をしていたのですが、その際に急に解法を思いつきました。

結果

6完です。

Fの考察が(多分)終わって実装が間に合わず@shiro537 くんと @suta28407928 くんの3人で出ました pic.twitter.com/bjDVboJLxo
— ツバサ (@emtsu_ba) 2020年2月12日

雑な解法

F

1行ずつ、下からブロックを積み重ねていきます。次にブロックを置く際は、1つ前の操作でブロックを置いた列にしか置かない、とします。
$dp[i][j] =$ 現在使える幅が $i$ 、残りブロック数が $j$ の際の、そこからの置き方
とします。 $dp[i][j] = \sum_{k = 1}^{i}(i-k+1)dp[k][j-k]$
となります。
このΣの部分を分解します。
$sum_{1}[i][c] = \sum_{k = 1}^{i}dp[k][c-k]$
$sum_{2}[i][c] = \sum_{k = 1}^{i}k \times dp[k][c-k]$
として、この累積和も同時並行で求めていくと、上手く計算できます。

G

調べたい文字列を $T_{i} (1 \leqq i \leqq N)$ 、元の文字列を $S$ とすると、
$T_{1} X T_{2} X T_{3} ... X T_{N} X S$ という文字列(ただし $X$ はダミー文字)を作成し、これに対してのsuffix arrayおよびlcp配列を構築します。
すると、調べたい文字列の任意の部分を始点とする、 $S$ との最長一致部分が、前計算 $O(\sum |T_{i}| + |S|)$ で求まります。
あとは、 $dp[i] = i$ 文字目までの最小コスト、としていい感じに更新します(自分は配るDPをしました)

K

与えられる文字列を、 $AH$ の切り替わりで区切ります。そのときの区切りの個数が、多項式の係数の最大です。
求める多項式を $P(x) = (x-a)(x-b)...$ とします。 $(x-a)$ の $a$ の部分を、 $AH$ の区切れ目の値(例えば、 $i$ 人目が $A$ 、 $i+1$ 人目が $H$ ならば $2i+ 1$ )に設定すると、うまく問題の条件を満たす多項式になります。 $P(2i)$ を計算する際に、 $(x-a)$ が、 $a \lt 2i$ ならば正、 $a \gt 2i$ ならば負になるので、いい感じになります。

L

そもそもBGの入れ替えが行われない時、最大正方形のDPは、
$dp[i][j]= (i,j)$ を右下とする最大正方形の1辺の長さ
と定義して、 $dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1$ となります(そこが $B$ ならば0です)。
これを、入れ替えたパターンの行に対しても行い、
$dp[t][i][j] = (i,j)$ を右下とする最大正方形の1辺の長さ( $t = 1$ ならば行のBGを入れ替え)
とすると、上のDPとほぼ同じ遷移で解くことができます。