geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 269 参加記録

ABC 等差数列

コンテストページ：

UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) - AtCoder

コンテスト中AC:A〜E
Fがあと一歩だったので、書いておきます。

F - Numbered Checker

長方形領域の列は以下の2つに大別されます。 ?には整数が入ります。

  • 0 ? 0 ? 0 ? ...
  • ? 0 ? 0 ? 0 ...

ここから0を抜いたものを考えます。

(1) 0 ? 0 ? 0 ?...の場合
行数をs、項数をp、1行目の最初の値をaとすると、以下のs個の数列の和を求める問題となります。

A_1 = \{a,\ a+2,\ a+4,...,\ a+2(p-1)\}
A_2 = \{a+2M,\ a+2+2M,\ a+4+2M,\ ...,\ a+2(p-1)+2M\}
... A_s = \{a+2(s-1)M,\ a+2+2(s-1)M,\ a+4+2(s-1)M,\ ...,\ a+2(p-1)+2(s-1)M\}

それぞれ和S_{A_i}以下のように考えます。

S_{A_1} = ap + 2\{1+2+...+(p-1)\} = ap+2\frac{p(p-1)}{2} = ap + p(p-1)
S_{A_2} = ap + 2\{1+2+...+(p-1)\}+2pM=ap + p(p-1) + 2pM
...
S_{A_s} = ap + 2\{1+2+...+(p-1)\}+2(s-1)pM=ap + p(p-1) + 2(s-1)pM

というわけで、ap + p(p-1)は、s個含まれ、\{ap + p(p-1)\}sです。
これを分離すると、残りの求めるべき和は、

2pM + 4pM + ... + 2p(s-1)M = 2pM\{1+2+...+(s-1)\} = 2pM\frac{s(s-1)}{2} = s(s-1)pM

となるので、長方形領域の求めるべき和S_aは、

S_a = \{ap + p(p-1)\}s + s(s-1)pM

です。

(2) ? 0 ? 0 ? 0 ...の場合
先ほどと全く同じです。
行数をt、項数をq、1行目の最初の値をbとすると、求めるべき和S_bは、

S_b = \{bq + q(q-1)\}t + t(t-1)qM

となります。

以上を求めれば、当初のクエリで求めるべき答えはS_a + S_bです。 後は、各クエリの長方形領域におけるs,t,p,q,a,bさえ求めれば答えを得ることができます。

まず、p,qはA,Cに依らず、以下の通り計算できます。

  • p = \lfloor \frac{(D-C+1)}{2} \rfloor
  • q = \lceil \frac{(D-C+1)}{2} \rceil

その他は場合分けが必要です。

(1) (A+C) \ mod\ 2 = 1の場合

0 ? 0 ? 0 ? ...
? 0 ? 0 ? 0 ...
...

というケースになります。

よって、

  • s = \lceil \frac{(B-A+1)}{2} \rceil
  • t = \lfloor \frac{(B-A+1)}{2} \rfloor
  • a = (A-1)\times M + C + 1
  • b = (A-1)\times M + C + M

(2) (A+C) \ mod\ 2 = 0の場合

? 0 ? 0 ? 0 ...
0 ? 0 ? 0 ? ...
...

というケースになります。

よって、

  • s = \lfloor \frac{(B-A+1)}{2} \rfloor
  • t = \lceil \frac{(B-A+1)}{2} \rceil
  • a = (A-1)\times M + C +M+ 1
  • b = (A-1)\times M + C

以上で各クエリをO(1)で解けます。

ちなみにコンテスト中は以下のミスで解けませんでした。
- 1+2+...+m = \frac{m(m-1)}{2}にしてしまっていた。
- a,bを逆にしていた。
- mod\ 998244353をとり忘れた。

Submission #34954104 - UNICORN Programming Contest 2022(AtCoder Beginner Contest 269)