AtCoder ARC120 個人的メモ

所感

ab2完
highest更新した

A - Max Add

N=3、数列a=(A,B,C)の場合を考える。
このときの各iでの解は、最大値を$m_i$とすると以下の通りになる。

• i=1
  $a=(A + m_1)$
  $f(a)=A+m_1$
• i=2
  $a=(A + m_2,\ B+(A+m_2))$
  $f(a)=2A+B+2m_2$
• i=3
  $a=(A + m_3,\ B+(A+m_3),\ C+(B+A+m_3))$
  $f(a)=3A+2B+C+3m_3$

というわけでk番目のf(a)を$f_k(a)$とすると以下のように表せそうと分かる。

$$f_k(a)=km_k+\sum_{i=1}^k (k-i+1)a_i$$

さらに$f_k(a)-f_{k-1}(a)$は以下のように求まる。

$$\begin{aligned} f_k(a)-f_{k-1}(a)&=km_k-(k-1)m_{k-1}+a_1+a_2+\cdots+a_{k-1}+a_k\\ &=km_k-(k-1)m_{k-1}+\sum_{i=1}^ka_i \end{aligned}$$

aの累積和を事前に計算しておけば$\sum_{i=1}^ka_i$はO(1)で求められる。
$m_k$についても、kを0~Nまで探索する過程でそれぞれO(1)で求められる。
よって、各kについてO(1)で解が得られるので、全体でO(N)となる。

from itertools import accumulate

N = int(input())
A = list(map(int, input().split()))

cumsum = list(accumulate(A))
ans = 0
maximum = 0
for i in range(N):
    maximum = max(maximum, A[i])
    ans += cumsum[i]
    print(ans + maximum * (i + 1))

B - Uniformly Distributed

色が塗られていないマスに色を塗って、どの経路でも赤を踏む回数が同じ場合の数を求める。

この条件を満たすためには、下図の各斜線上のマスの色(RかB)がそれぞれ1種類になっている必要がある。
この問題での移動できる方向は(i+1)の方向か、(j+1)の方向のみである。
よって、移動するとi+jは1増加する。
下図の斜線の端の番号は各斜線上のマスのi+jを表す。
つまり、下図の斜線上のマスをそれぞれ1回ずつ通ると分かる。
同じ斜線上で異なる色に塗られているマスがあると、それぞれのマスを踏む場合で赤を踏む回数が異なってしまう。
だから、斜線上のマスは全て同じ色になる必要がある。

というわけで、各斜線上で以下のように処理すればおｋ。

• 斜線上に赤と青で塗られたマスがある。
  既に条件を達成できない。
• 斜線上に色が塗られていないマスのみがある。
  全部赤で塗る場合と全部青で塗る場合の2つの場合があり得る。
• 斜線上に赤か青のどちらか1種類のマスと色が塗られていないマスのみがある。
  色が塗られていないマスは塗られているマスと同じ色で塗らないといけないので1つの場合があり得る。

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
MOD = 998244353

slant_seen = [set() for _ in range(H + W)]
for i in range(H):
    for j in range(W):
        slant_seen[i + j].add(S[i][j])

ans = 1
for seen in slant_seen:
    if "R" in seen and "B" in seen:
        ans *= 0
    if seen == {"."}:
        ans *= 2
    ans %= MOD

print(ans)