3匹の猫

みみねこの競プロ精進メモ

AtCoder Regular Contest 113参加記(~D問題)

いろいろ悔しい
f:id:mmnkblog:20210221230637p:plain

A - A*B*C

最初、ABC=Kと誤読していた。サンプルで気付くまで15分かかった。ダメ。

Kは定数なので、たとえばAを固定すると条件式がBC\le \dfrac{K}{A}となる。この式を満たす正の整数の組(B, C)の個数は、\dfrac{K}{A}以下の整数それぞれの約数の個数の総和に等しい。

よって、1からKまでの整数それぞれの約数の個数が高速に求められれば良い。これは計算量O(K\log K)で求められる。これらの結果に累積和を適用することで、答えが求まる。

計算量は、O(K\log K)

B - A^B^C

10進法での1の位というのは、\bmod 10の値のことを指す。なので、はじめにAの値は\bmod 10で持って良い。

ここからの議論があいまいだが、ある程度大きい定数kに対して
A^k \equiv A^{k+4} \pmod{10}
である。よって、B^C\bmod 4の値がいくつか分かれば答えが求まることになる。具体的には、

  • B \equiv 0 \pmod{4} ならば B^C \equiv 0 \pmod{4}
  • B \equiv 1 \pmod{4} ならば B^C \equiv 1 \pmod{4}
  • B \equiv 2 \pmod{4} かつ C=0 ならば B^C \equiv 2 \pmod{4}
  • B \equiv 2 \pmod{4} かつ C\neq 0 ならば B^C \equiv 0 \pmod{4}
  • B \equiv 3 \pmod{4} かつ C\equiv 0 \pmod{2} ならば B^C \equiv 3 \pmod{4}
  • B \equiv 3 \pmod{4} かつ C\equiv 1 \pmod{2} ならば B^C \equiv 1 \pmod{4}

となる。あとは計算して、最後に10で割った余りを出力すればよい。例外的に、B\le 8かつC\le 8の場合は場合分けを通さずに実際にA^{B^C}を計算した。

計算量は、O(1)

C - String Invasion

手元で実験してみると、ある場所でaabのような並びがあった場合連鎖的に操作が行え、文字列の末尾まですべてaで置き換えることができる。また、aab...ccd...というように2か所以上操作が行える箇所が存在した場合、より後ろにあるものから操作しても解は悪化しない。よって、文字列を後ろから見ていくことにする。

ある文字が連続していた場合、基本的にはその箇所より後ろにある文字全てが操作によって置き換わることになる。1回の操作で1文字置き換わるので、i文字目とi+1文字目が連続していた時、|S| - i - 1回操作を行える。
ただし、連続している文字より後ろに、その文字と同じ種類の文字が存在していた場合は操作を行えない。ただしそこで操作の連鎖がストップするわけではなく、それより後ろにある違う種類の文字に対しては操作できる。つまり、「i+1文字目より後ろにある文字のうち、文字s_iと文字の種類が同じである文字の個数」回は操作を行えない。この文字の個数は、「文字の種類」から「個数」を引ける構造を用意しておくことで簡単に調べられる。

以上の操作を文字列の後ろから実行して答えをカウントしていく。計算量は、文字の種類数をCとしてO(|S|C)

D - Sky Reflector

列A、Bを決めたときに矛盾なく数を埋められるか?を考えるとわかりやすい(と個人的に感じた)。

問題文の条件を言い換えると、

  • iに書き込める整数はA_i以上K以下
  • jに書き込める整数は1以上B_j以下

となる。さらにまとめると、

  • マス(i, j)に書き込める整数の範囲はA_i以上B_j以下

であることがわかる。

つまり、列Aの最大値をA_{\max}と固定すれば、各jに対してA_{\max}\le B_j \le Kが成立する。M個ある要素B_jはそれぞれ独立である。よって、最大値がA_{\max}であるような列Aの個数をC_{A_{\max}}とすると、C_{A_{\max}}\times (K - A_{\max} + 1)^MをすべてのA_{\max}に対して求め、その総和を取ったものが答えとなる。ここでの計算量は、O(K\log M)

C_{A_{\max}}を求める。A_iの値は1以上A_{\max}以下なら何でもよいが、どれか1個以上はA_i = A_{\max}でなければならない。よって、
1\le k \le Kを満たすkに対して、C_k = k^N - (k-1)^Nが成り立つ。ここでの計算量は、O(K\log N)

まとめると、全体の計算量は、O(K(\log N + \log M))となる。


…ただし、N=1(またはM=1)の場合は例外で、マス(1, j)に書かれた整数はB_jなので、B_jがすべて決まればA_1の値も決まる。よってこの場合の答えはK^Mとなる。この場合分けを忘れて、コンテスト時間内のACを逃した…。(コンテスト後に気付いて場合分けを追加して提出したところ、ACした)くやしい。くやしい!!!!


感想

マジで悔しい~~~~