Official

D - ハイスコア/High Score Editorial by kyopro_friends


問題文にかかれている通り、各 \(K=1,\ldots,T\) に対して各科目の最高点を求めて和を取ればよいです。2 重ループないし 3 重ループを書くことになるので、添字などに注意しましょう。 計算量は \(O(NT^2)\) になります。

実装例(C)

#include<stdio.h>
#define max(p,q)((p)>(q)?(p):(q))

int p[1010][10];
int main(){
	int t,n;
	scanf("%d%d",&t,&n);
	for(int i=0;i<t;i++)for(int j=0;j<n;j++)scanf("%d",&p[i][j]);
	for(int k=0;k<t;k++){
		int c[10]={};
		for(int i=0;i<=k;i++)for(int j=0;j<n;j++)c[j]=max(c[j],p[i][j]);
		int ans=0;
		for(int j=0;j<n;j++)ans+=c[j];
		printf("%d\n",ans);
	}
}

実装例(Python)

import numpy as np
T,N=map(int,input().split())
P=np.array([list(map(int,input().split())) for i in range(T)])
for k in range(T):
  print(sum(max(P[:k+1,i]) for i in range(N)))

なお、この問題は適切な実装により \(O(NT)\) で解くことも出来ます。

posted:
last update: