yukicoder : No.2229 Treasure Searching Rod (Hard)

こちらも割とすんなり解けた。
https://yukicoder.me/problems/no/2229

問題

H*WのグリッドにN個のお宝がある。
各お宝の位置と価値が与えられる。

あるマス(i,j)に対し操作を行ったとする。
お宝が(x,y)にあり、かつ

• x+y≧i+j
• x-y≧i-j

を満たすとき、お宝を取得できる。

H*Wの各マスで操作を行ったとき、それぞれ得られるお宝の価値の総和を求めよ。

解法

お宝ごとに、それが得られる操作位置のマス数を数えよう。
お宝が(x,y)にあるなら、

• y≧-x+(i+j)
• y≦x-(i-j)

を満たすマス(i,j)で操作を行えば、お宝を取得できる。
この領域は、三角形と矩形の共通部分で容易に数え上げられる。

int H,W,K;
ll X,Y,V;
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	ll ret=0;
	FOR(i,K) {
		cin>>Y>>X>>V;
		X--;
		ll num=0;
		ll Y2=max(0LL,Y-X);
		ll Y3=max(0LL,Y-(W-1-X));
		num+=(Y+Y2)*(Y-Y2+1)/2;
		num+=(Y+Y3)*(Y-Y3+1)/2;
		num-=Y;
		ret+=num%mo*V%mo;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

★2.5位でもいいかも。