https://csacademy.com/contest/round-12/summary/
2つの整数$A, B$が与えられる。区間$[A, B]$に含まれる整数のなかで約数を奇数個もつものの数を出力せよ。
実際に、$A$から$B$までのすべての整数の約数の個数を数えればよい。
自力AC。初のDiv.2コンテストの最初の問題だけあって、簡単。ちなみに解説によると、約数の数が奇数の整数は平方数しかないらしい。考える前に愚直を通してしまった。
1桁の整数が$N$個与えられる。この数列の連続な部分列の中で、積が0より大きいものの数を出力せよ。
0がない場合は、$\frac{N(N+1)}{2}$が答えとなる。0があるなら、0で区切ったそれぞれの数列に対して同じことをして、足し合わせたものが答えとなる。
自力AC。典型的な問題。
$N$この長方形について、幅$w$と高さ$h$が与えられる。ある長方形$i$について、$w_i\lt w_j$かつ$h_i\lt h_j$であるような長方形$j$が1つも存在しないとき、長方形$i$はindependentであるという。independentな長方形の数を出力せよ。
最初に長方形を$w$で降順ソートして前から順番にチェックする。このとき、$i$番目の長方形よりも$w, h$が共に大きい長方形は$i$番目より前に出てきているはずである。座標圧縮などをして、各$w$について自分より$w$が大きい長方形がもつ$h$の最大値を記録しておけば、independentな長方形をO($N\log N$)で数えることができる。
自力AC。かなり見えやすい問題。
整数$a, b, x$で表されるクエリが$Q$個が与えられる。$a\leq y\leq b$であって、$x\ and\ y = x$であるような整数$y$の個数を出力せよ。
$y$の上限を$2^{64}-1$とすると、$a, b$の条件を無視したとき、andの条件を満たす$y$は$x$を2進数で表したときに1になっているbitの数$n$に対して$2^{64-n}$個であることがわかる。
$y$のなかで$a$よりも小さい / $b$より大きいものを数えるには、桁DPを用いればよい。
$DP_A[i][a$より小さいことが確定していない/している$]=$上から$i$桁を見たときにandの条件を満たす$y$の数
$DP_B[i][b$より大きいことが確定していない/している$]=$上から$i$桁を見たときにandの条件を満たす$y$の数
最後に、すべての$y$から$a$より小さいものと$b$より大きいものを引けばよい。
自力AC。これもかなり典型的な問題だと思う。
2つの大きな整数$N, M$が与えられる。$M$の桁数を$K$とするとき、$[1, N]$の整数のなかで、そのprefixとsuffix$K$桁がともに$M$であるようなものの数を$10^9+7$で割ったあまりを出力せよ。
解法は、全体で2つのパートに分けることができる。
前半は、桁数が$2K$未満の整数を見つけるパートである。長さが$i\ (K\leq i\lt 2K)$であるような整数のなかでprefixとsuffixがともに$M$であるようなものが存在するかどうかは、Z-Algorithmを使ってそれぞれO(1)で求めることができる。$i\lt \min(|N|, 2K)$の場合をこの方法でカウントし、$i=N$の場合は愚直に構成して比較すればよい。(ここで$|N|$は、$N$の桁数)
$2K\leq N$の場合には、MxxxxxxxMのような形の整数をさらに数える必要がある。$|N|$桁未満の場合には、xに0から9のすべての整数を入れてよいので、簡単に数えられる。$|N|$桁ちょうどの場合には、桁DPを使って$N$以下の整数の数を数えることができる。DPテーブルは、1つ前の問題と同じものが使える。
自力AC。editorialではZ-Algorithmの代わりにKMPを使っていた。