AtCoder Regular Contest 113参加記(~D問題)
いろいろ悔しい
A - A*B*C
最初、と誤読していた。サンプルで気付くまで15分かかった。ダメ。
は定数なので、たとえばを固定すると条件式がとなる。この式を満たす正の整数の組の個数は、以下の整数それぞれの約数の個数の総和に等しい。
よって、からまでの整数それぞれの約数の個数が高速に求められれば良い。これは計算量で求められる。これらの結果に累積和を適用することで、答えが求まる。
計算量は、。
B - A^B^C
進法でのの位というのは、の値のことを指す。なので、はじめにの値はで持って良い。
ここからの議論があいまいだが、ある程度大きい定数に対して
である。よって、の値がいくつか分かれば答えが求まることになる。具体的には、
- ならば
- ならば
- かつ ならば
- かつ ならば
- かつ ならば
- かつ ならば
となる。あとは計算して、最後にで割った余りを出力すればよい。例外的に、かつの場合は場合分けを通さずに実際にを計算した。
計算量は、。
C - String Invasion
手元で実験してみると、ある場所でaab
のような並びがあった場合連鎖的に操作が行え、文字列の末尾まですべてa
で置き換えることができる。また、aab...ccd...
というように2か所以上操作が行える箇所が存在した場合、より後ろにあるものから操作しても解は悪化しない。よって、文字列を後ろから見ていくことにする。
ある文字が連続していた場合、基本的にはその箇所より後ろにある文字全てが操作によって置き換わることになる。1回の操作で1文字置き換わるので、文字目と文字目が連続していた時、回操作を行える。
ただし、連続している文字より後ろに、その文字と同じ種類の文字が存在していた場合は操作を行えない。ただしそこで操作の連鎖がストップするわけではなく、それより後ろにある違う種類の文字に対しては操作できる。つまり、「文字目より後ろにある文字のうち、文字と文字の種類が同じである文字の個数」回は操作を行えない。この文字の個数は、「文字の種類」から「個数」を引ける構造を用意しておくことで簡単に調べられる。
以上の操作を文字列の後ろから実行して答えをカウントしていく。計算量は、文字の種類数をとして。
D - Sky Reflector
列A、Bを決めたときに矛盾なく数を埋められるか?を考えるとわかりやすい(と個人的に感じた)。
問題文の条件を言い換えると、
- 行に書き込める整数は以上以下
- 列に書き込める整数は以上以下
となる。さらにまとめると、
- マスに書き込める整数の範囲は以上以下
であることがわかる。
つまり、列の最大値をと固定すれば、各に対してが成立する。個ある要素はそれぞれ独立である。よって、最大値がであるような列の個数をとすると、をすべてのに対して求め、その総和を取ったものが答えとなる。ここでの計算量は、。
を求める。の値は以上以下なら何でもよいが、どれか1個以上はでなければならない。よって、
を満たすに対して、が成り立つ。ここでの計算量は、。
まとめると、全体の計算量は、となる。
…ただし、(または)の場合は例外で、マスに書かれた整数はなので、がすべて決まればの値も決まる。よってこの場合の答えはとなる。この場合分けを忘れて、コンテスト時間内のACを逃した…。(コンテスト後に気付いて場合分けを追加して提出したところ、ACした)くやしい。くやしい!!!!
感想
マジで悔しい~~~~