gyouzasushi’s diary

競プロとか

今日の競プロ(2020/4/7)

Codeforces 2問

Educational Codeforces Round 44 E - Pencils and Boxes

解説AC。

$dp[i]=i$ 本目までの色鉛筆を正しく箱に入れられるか、のbool。
遷移は、 $a_i - d \leq a_j$ かつ $j \leq i-k+1$ をみたすある $j$ で $dp[j]=1$ なら $dp[i+1]=1$ 。 $j$ 本目未満を正しく箱に入れられて、かつ $j$ 本目から $i$ 本目までが一つの箱に入るなら、 $i$ 本目までの色鉛筆全てが正しく箱に入る、みたいな。セグ木とかで高速にできる。

Educational Codeforces Round 44 F - Isomorphic Strings

文字列 $s$ に対して、文字列 $s_a$ を

$s[i]=$ 'a' のとき $s_a[i]=$ '1'
そうでないとき $s_a[i]=$ '0'

と定める。 $s_b, s_c, \ldots, s_z$ も同様。このとき、文字列 $s$ と文字列 $t$ がIsomorphicであるとは、 $\{s_a, s_b, \ldots , s_z\}$ をソートしたものと $\{t_a, t_b,\ldots , t_z\}$ をソートしたものが一致するということ。あとはRolling Hashでがんばる。

最初WAやったけど、Rolling Hashの基数を変えたら通った…。この辺よくわかってないのでまた勉強する。

ARC051 A - 塗り絵

バチャ。

ARC051 B - 互除法

ARC051 C - 掛け算

操作の回数 $B$ がとても多いので、周期性をみつけたいなあ、と考える。

$a$ がもし $min\{a_i\} \times A \geq max\{a_i\}$ という条件をみたすなら簡単で、 $N$ 回の操作でそれぞれの要素が $1$ 回ずつ $A$ 倍されるというわかりやすい周期をもつ（ $a=\{1,2,3\},A=10$ なら $\{1,2,3\}$ → $\{10,2,3\}$ → $\{10,20,3\}$ → $\{10,20,30\}$ → $\{100,20,30\}$ →… みたいに）。

そして、上の条件を満たさないうちは数列の最大値が更新されないため、どのような数列 $a$ が与えられたとしても少ない操作（高々 $O(N \log max\{a_i\})$ 回）で条件をみたす瞬間が訪れることがわかる。

よって、愚直にシミュレーションしたあと周期を利用して適当に掛け算すれば完成。

ギリギリ時間内に解けた…。

コメント

Congratulations — you've qualified for Round 1 of Code Jam 2020!

Tシャツほしい〜〜〜がんばります