ARC练习记录

AFO

4 / 15

最近开了好多坑,决定在做题方面先填完这一个坑.

目前计划是先写15场ARC,从ARC58写到ARC072.

在没填完这个坑之前不会开别的坑,水题记录(五)和USACO计划都死了..

这个坑要开始认真填了.


做题方法 and 做题速度 and 合格标准

C题不能看题解,切掉不能超过20分钟,最多WA1次.

D题不能看题解,思考时间不能超过60min.

E题如果超过45~60分钟才能看题解.

F题如果超过30~60分钟没有思路才能看题解.

整套题做的时间和写博客时间不得超过3天


AtCoder Regular Contest 058

Title
C – こだわり者いろはちゃん / Iroha’s Obsession
D – いろはちゃんとマス目 / Iroha and a Grid
E – 和風いろはちゃん / Iroha and Haiku
F – 文字列大好きいろはちゃん / Iroha Loves Strings

こだわり者いろはちゃん / Iroha’s Obsession

300pts

题意:给出$0 \sim 10$中的数字拿些不能选,求出大于等于$n$的最小满足条件的数.

  • $1≦N<10000$
  • $1≦K<10$
  • $0≦D_1<D_2<…<D_K≦9$
  • ${D_1,D_2,…,D_K}≠{1,2,3,4,5,6,7,8,9}$

题解:$n$很小,直接枚举到99999.

いろはちゃんとマス目 / Iroha and a Grid

400pts

题意

给出$n\times m$的矩阵,左下的$a\times b$不能走.问总左上走到右下的方案数.

  • $1≦H,W ≦ 100,000$
  • $1≦A<H$
  • $1≦B<W$

题解

$nm$小的时候直接$DP$就好.$nm$无限制答案是$C(n+m-2,n-1)$,因为对于第$n-a + 1$行的第$b+1 \sim m$个方块只能从它上面的那个方块转移过来.

对于一个$t=(b+1) \sim m$,答案是从$(1,1)$到$(n-a,t)$的方案乘上从$(n,m)$到$(n-a+1,t)$的方案的和.

和風いろはちゃん / Iroha and Haiku

700pts

题意

对于一个串,如果在把它一个连续的段分为三个连续的段,每段的和为给出的$x,y,z$,那么这个串合法.问有多少个长度为$n$的这个样的串.串的每个位置只能填1~10.

  • $3≦N≦40$
  • $1≦X≦5$
  • $1≦Y≦7$
  • $1≦Z≦5$

题解

最开始写了个DP是$f[i][k]$表示$i$位可以组成的答案为$k$的方案.然后算.打完才发现过不了第三个样例,一想发现自己会算重.

然后加了一点.$dp[i]$表示前$i$位的答案,写了以后发现会算少.

自己复杂度太小了,这个数据范围就很玄学,所以我一定是错的.

题解告诉我是状压DP.

因为直接算会重复,那么直接考虑不满足条件的方案数.

由于$5+7+5=17$,所以只需要考虑$17$位数字就行了.

把每一个数字对应每一位.

比如说把(1,2,3)就是$(1,10,100) \rightarrow 110100$.

如果是$(a,b)​$,那么$(a+b)​$就是$(1<<(a-1)|(1<<a+b-1))​$,会包含$1<<(a+b-1)​$

推广可得$(a,b,c)$同理.

令$f[i][j]$表示前$i$个数字,后$17$位的状态.

转移时枚举这一位填什么数.如果转移的状态不包含$x,y,z$用$f[i-1][k]$更新.

文字列大好きいろはちゃん / Iroha Loves Strings

1500pts

题意

给出$n$个字符串,求出一些串顺次接起来,要求长度为$k$,输出字典序最小的答案

题解

这个题想了一个星期…最后还是抄了大佬的题解才会做.

先预处理一下后$n-i$个串是否可以构成长度为$k$的子串.转移的时候先判断这个.

暴力的DP应该是$O(nk\cdot \sum Len)$的,无法通过.

那么考虑一个贪心,顺次加入字符串.

每次保留一个最优的串.用SA算一下LCP然后判断字典序.

打了一般.发现有很多问题.

对于两个真包含的串情况好多,不知道怎么特判了.

题解的做法太神奇.就学了一下能A的暴力.

就是每次用F[i]记录下所有满足条件的状态.转移的时候取一个最优的.

然后如果这个子串用完了,就暴力把后面的所有满足条件的放进去.

要用滚动数组滚一下.

其实随便卡一下就T了,但是数据不强就没有卡掉.

不知道为什么用std::vector就会TLE.

原因是因为vector.clear()是O(n)的,因为std::vector的数组不是连续的.所以其实到不了$n$,但是理论是$O(n)$,不是$O(1)$,可能就会T.(之前一直以为是O(1)的…)

AtCoder Regular Contest 059

Title
C – いっしょ / Be Together
D – アンバランス / Unbalanced
E – キャンディーとN人の子供 / Children and Candies
バイナリハック / Unhappy Hacking

いっしょ / Be Together

200pts

题意

定义把$a$变为$b$的花费为$(b-a)^2$,给出$n$个数,询问把所有数变为同样的数的最小花费

  • $1≦N≦100$
  • $−100≦a_i≦100$

题解

最开始没看范围,不太清楚怎么做,感觉可以取平均数然后再平均数附近取到最小值,后来看了下范围就发现直接暴力枚举最后要成为什么数,然后取最小值.

アンバランス / Unbalanced

400pts(200pts)

题意

定义长度大于1,其中相同字符出现次数大于串长的一半的串为unbalanced.询问一个长串中是否有一个子串时unbalanced的,输出位置.

题解

我的方法比较复杂.后来看了别人的代码发现写的很蠢.复杂度要高一个字符集大小.

对于单个字母考虑,把等于这个字母的变为1,不等于的变为-1,那么要求一段的和大于0就是答案.

用前缀和维护,具体方法是维护最小值和最小值的位置.如果当前的前缀和大于了前面的最小值$Sum[i]-Sum[Pos]>0$,就找了答案.

看了别人的做法.

虽然跑得不慢,但是方法差太多了.QAQ

因为满足条件的答案里面一定有这两种情况,那么直接判断一下就好了.

キャンディーとN人の子供 / Children and Candies

800pts(400pts)

题意

有$C$颗糖,$N$个小朋友.每个小朋友有一个兴奋值$X_i$,如果给他$a$颗糖,那么它的开心值是$X_i^a$,幼儿园的活泼度为每个人开心值的和,记为$F(X_1,X_2,…X_N)$,现在要求
$$
\sum_{x_1=A_1}^{B_1}\sum_{x_2=A_2}^{B_2}…\sum_{x_N=A_N}^{B_N}F(X_1,X_2…,X_N)
$$
题解

令$f[i][j]$表示前$i$个小朋友,给了$j$颗糖的答案,DP算一下.
$$
f[i][j]=\sum_{k=1}^{j}\sum_{p=a_i}^{b^i}f[i-1][k] \times p^{j-k}\
$$

这样做的复杂度是$O(400^4)​$的.不能过.但是可以过$A_i=B_i​$的400分

那么这个时候要转换一下转移的方法,枚举当前给这个人$k$颗糖.

$$
f[i-1][j-k] \rightarrow f[i][j]\\
\forall f[i][j] = \sum_{j=k}^{C}\sum_{p=a_i}^{b_i} f[i – 1][j-k] \times p^{k}\\
\forall f[i][j] = \sum_{j=k}^{C} f[i – 1][j-k] \times \sum_{p=a_i}^{b_i}p^{k}
$$

这样就可以省去一层循环了.复杂度O(400^3),可以AC.

启发

有时候同一种DP,换一种转移方式可以省去一层循环,大大节省时间复杂度.

バイナリハック / Unhappy Hacking

800pts(400pts)

题意

给出$n$次操作,最开始有一个空字符串,每次可以在最后面加入一个’0′,’1′,或者删除最后的字符,(如果为空就不删).然后给出一个串$S$,询问$n$次操作以后字符串为$S$的方案数.

题解

想了好久QAQ.最开始想了一个DP,$f[i][j][0/1]$表示前$i$次操作,匹配的长度为$j$,上一次操作是否对匹配数有贡献的方案数.打的时候发现好多情况很麻烦,而且对于连删多次和连加多次就会算错.

最暴力的DP是$f[i][j][k]$表示前$i$次,匹配了$j$个,总长为$k$的方案数.转移的时候分为$j=k$和$j\neq k$的转移,复杂度$O(n^3)$,可以过部分分.

然后就不会做了…

题解告诉我.其实和’01’没有关系,只要$S$的长度不变,01不论怎么排列都有相同的方案数.

那么直接算所有的方案数然后除$2^m$就好了.

突然恍然大(雾).感觉自己收到了深深的欺骗.思维陷入了01排列的定式.

直接用$f[i][j]$表示前$i$个操作,长度为$j$的方案数.答案便是$\frac{f[n][len]}{2^m}$

这样复杂度$O(n^2)$.

启发

如果多个$DP$状态答案时一样的话,可以把它们和在一起算,可能就可以减少一些限制,降低算法复杂度,最后除掉相同的个数.

AtCoder Regular Contest 060

Title
高橋君とカード / Tak and Cards
桁和 / Digit Sum
高橋君とホテル / Tak and Hotels
最良表現 / Best Representation

高橋君とカード / Tak and Cards

300pts

题意

给出$n$个数可以选或者不选,求平均数是A的方案数

  • $1≤N≤50$

题解

$dp[i][j][k]$表示前$i$个数选了$j$个,和为$k$的方案数,复杂度为$O(n^4)$,可以过

如果把$x_i$变为$x_i-A$,那么求的是”和为$0$”的方案数.那么此时和选的数的个数无关,省去一维.$dp[i][j]$表示前$i$个数,和为$j$的方案数,复杂度为$O(n^3)$

桁和 / Digit Sum

500pts

题意

求满足$n$在$b$进制下的数位和为$x$的最小$b$.

题解

考虑$b\leq \sqrt n$,枚举即可

考虑$b > \sqrt n$
$$
n=pb+q\\
s=p+q\\
n-s=(b-1)q
$$
枚举$n-s$的约束,复杂度$\sqrt n$

高橋君とホテル / Tak and Hotels

700pts

题意

给出直线上$n$个点,每天可以走$L$,$Q$次询问,询问从$x$走到$y$的天数

题解

倍增预处理,感觉比上面两题还简单.

AtCoder Regular Contest 061

Title
たくさんの数式 / Many Formulas
すぬけ君の塗り絵 / Snuke’s Coloring
すぬけ君の地下鉄旅行 / Snuke’s Subway Trip
3人でカードゲーム / Card Game for Three

たくさんの数式 / Many Formulas

题意

すぬけ君の塗り絵 / Snuke’s Coloring

すぬけ君の地下鉄旅行 / Snuke’s Subway Trip

给出$n$个点$m$条边的一张图,每条双向边都有一个赞助公司,可以从一个点通过边到另一个点.如果要去的边和来的边赞助公司不同,费用加一,问从$1$到$n$的最小费用.

题解

最开始想的是跑最短路转移的时候记录一下来的公司是什么,问了下cxy,发现这样的复杂度时不对的.

中间的点有$\frac{m}{4}$条入边,$\frac{m}{4}$个出边.转移的时候,可能要保存所有入/出边,复杂度就不对了.

红太阳cxy给出的方法是把一个点拆成$\deg[n]$条边,没有限制的新开一个,其他的每一个点表示从$a_i$号公司出来.然后最短路.

这个做法会有些复杂.事实上,有更优秀的方法.(膜了某神仙的代码…)

还是上面的思路,我们发现对于图中的点,只需要维护它的入边的公司的编号.

举个栗子,现在想用$(u \rightarrow v,c)$更新$v$的值.

当前的收益是”在所有合法的转移到$u$的边中不存在和$c$相同的公司”

如果对于$v$可以更新成功,清空$v$的那个堆.在$v$的堆中放入新的边$c$.

一,清空堆不会使答案变劣.

这样做是因为既然$v$的答案被更新了,就算$v$的出边中有一个点和被删除的公司相同,花费0.但是从现在的边走过去.费用1,而$now>old \rightarrow now + 1 \geq old + 0$.所以一定不会比之前劣.也就说可以清空$v$的堆.

二,不清空堆会使答案非法.

如果不清空,从堆中保留的边的公司的答案不一样,但是此时的算出来的值表示的是最优的答案,如果$v$连入和连出的边有$s$,而从$s$转移到$v$的时候并不是最优解.被保存在了答案中更新,会计算错误.

如果要更新答案和现在的最优值一样,则把$c$放入$v$的堆中

这个不必多说,对于一种最优解法,需要保存所有可以产生这种情况的边,在下次转移的时候需要用到.

然后建出图以后用最短路更新.用$Dijkstra$,因为转移的复杂度为$O(logn)$,总时间复杂度$O(nlog^2n)$,空间复杂度和边同级$O(M)$.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*