DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Swap and Matrix Multiplication

問題に戻る

解説

연산 전의 값을 S0S_0S0​이라 하자. Ax,k=aA_{x,k}=aAx,k​=a와 Bk,x=bB_{k,x}=bBk,x​=b를 교환하고 d=b−ad=b-ad=b−a라 하자. 교환 후 Ax,kA_{x,k}Ax,k​는 ddd만큼 증가하고 Bk,xB_{k,x}Bk,x​는 ddd만큼 감소한다.

SSS에 포함된 원소 중 xxx번째 행에서 대각선 오른쪽에 있는 원소의 변화량 합은

d∑j=x+1NBk,jd\sum_{j=x+1}^{N}B_{k,j}dj=x+1∑N​Bk,j​

이고, xxx번째 열에서 대각선 위쪽에 있는 원소의 변화량 합은

−d∑i=1x−1Ai,k-d\sum_{i=1}^{x-1}A_{i,k}−di=1∑x−1​Ai,k​

이다. 대각 원소에서는 Ax,kBk,x=abA_{x,k}B_{k,x}=abAx,k​Bk,x​=ab가 교환 후에도 ba=abba=ab이므로 변화량이 이다. 따라서 전체 변화량은

Δx,k=(Bk,x−Ax,k)(∑j=x+1NBk,j−∑i=1x−1Ai,k)\Delta_{x,k}=(B_{k,x}-A_{x,k})\left(\sum_{j=x+1}^{N}B_{k,j}-\sum_{i=1}^{x-1}A_{i,k}\right)Δx,k​=(B

이다.

AAA의 열별 앞쪽 누적합과 BBB의 행별 뒤쪽 누적합을 다음과 같이 정의한다.

Pi,k=∑r=1iAr,k,Qk,i=∑c=iNBk,cP_{i,k}=\sum_{r=1}^{i}A_{r,k},\qquad Q_{k,i}=\sum_{c=i}^{N}B_{k,c}Pi,k​=r=1

P0,k=0P_{0,k}=0P0,k​=0, Qk,N+1=0Q_{k,N+1}=0Qk,N+1​으로 두면 각 변화량은

Δx,k=(Bk,x−Ax,k)(Qk,x+1−Px−1,k)\Delta_{x,k}=(B_{k,x}-A_{x,k})(Q_{k,x+1}-P_{x-1,k})Δx,k​=(Bk,

로 O(1)O(1)O(1)에 계산할 수 있다.

초기 합도 행렬곱 전체를 만들 필요 없이 합의 순서를 바꾸어 계산한다.

S0=∑i=1N∑k=1NAi,kQk,iS_0=\sum_{i=1}^{N}\sum_{k=1}^{N}A_{i,k}Q_{k,i}S0​=i=1∑N​

연산을 하지 않는 경우를 포함해야 하므로 정답은

S0+max⁡(0,max⁡1≤x,k≤NΔx,k)S_0+\max\left(0,\max_{1\leq x,k\leq N}\Delta_{x,k}\right)S0​+max(0,1≤x,k≤N

이다. 시간 복잡도와 공간 복잡도는 모두 O(N2)O(N^2)O(N2)이다.

Solution written by GPT6

ba
=
ab
000
k,x
​
−
Ax,k​)(j=x+1∑N​Bk,j​−i=1∑x−1​Ai,k​)
∑
i
​
Ar,k​
,
Qk,i​
=
c=i∑N​Bk,c​
=
0
x
​
−
Ax,k​)(Qk,x+1​−
Px−1,k​)
k=1∑N​
Ai,k​
Qk,i​
max
​
Δx,k​
)