読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.390 最長の数列

問題はこちら
No.390 最長の数列 - yukicoder

コンテスト中にはO(N^2)解しか思いつかずに撃沈。解説を見た
(以下maxφ=0とする)
・O(N^2)解
xiが小さい方から順に、dp[i]=1+max{dp[j]|xjはxiの約数}としてmax{dp[i]}が答え
配るDPに書き換えて、iが小さい方から、xjがxiの倍数であるようなjに対し、dp[j]=max(1+dp[i],dp[j])
・O((max xi)logN)解
初期値としてdp[xi]=1を与えておき、iが小さい方から順に「dp[i]=1+max{dp[j]|jはiの約数、かつ、dp[j]>0}」としてmax{dp[i]}が答え
配るDPに書き換えて、iが小さい方から、jがiの倍数かつdp[j]>0であるようなjに対し、dp[j]=max(1+dp[i],dp[j])

要するに、「xのindexであるi」に対してじゃなくて、「xの要素であるi」に対して操作をしろ、という話
前者だと毎回xi~xNまでN個全部調べる必要があるのに対し、後者だとk回目に調べるのは(k以上の数だから)max{xi}/k個以下で済む

#define max(p,q)(p>q?p:q)
main(){
	int b[1000010]={},n,i,j,t,s;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&t);
		b[t]=1;
	}
	for(i=0;i<1e6;i++)if(b[i])for(j=i+i;j<=1e6;j+=i)if(b[j])b[j]=max(b[j],b[i]+1);
	for(i=0;i<1e6;i++)s=max(s,b[i]);
	printf("%d",s);
	return 0;
}

見た目のわかりやすさのために取り敢えずmaxは残しておいて、最初の読み飛ばしと、最後のsを探す部分を上手くまとめるとこうなる

#define max(p,q)(p>q?p:q)
b[1<<21],s,i,j;
main(n){
	for(;~scanf("%d",&n);s=1)b[n]=s;
	for(;i<1e6;i++)for(j=i;b[i]&&j<1e6;s=max(s,b[j]))b[j+=i]?b[j]=max(b[j],b[i]+1):0;
	s=!printf("%d",s);
}

maxを普通に書いて、真ん中のfor文を圧縮

b[1<<21],s,i,j;
main(n){
	for(;~scanf("%d",&n);s=1)b[n]=s;
	for(;b[i]&&j<1e6?b[j+=i]?b[j]=b[j]>b[i]?b[j]:b[i]+1:0,s=s>b[j]?s:b[j]:(j=++i)<1e6;);
	s=!printf("%d",s);
}

さらにもう1つのfor文も合体

b[1<<21],s,i,j;
main(n){
	for(;~scanf("%d",&n)?b[n]=s,s=1:b[i]&&j<1e6?b[j+=i]?b[j]=b[j]>b[i]?b[j]:b[i]+1:0,s=s>b[j]?s:b[j]:(j=++i)<1e6;);
	s=!printf("%d",s);
}

153B
更に出力もまとめると、2B縮むがREになってしまう。うーん

b[1<<21],s,i,j;
main(n){
	for(;s=~scanf("%d",&n)?b[n]=s,1
			      :b[i]&&j<1e6?b[j+=i]?b[j]=b[j]>b[i]?b[j]:b[i]+1:0,s>b[j]?s:b[j]
					  :(j=++i)<1e6?s
						      :!printf("%d",s)
	   ;);
}

16/07/30追記
fmax

b[1<<21],s,i,j;
main(n){
	for(;~scanf("%d",&n)?b[n]=s,s=1:b[i]&&j<1e6?s=fmax(s,b[j+=i]?b[j]=fmax(b[j],b[i]+1):0):(j=++i)<1e6;);
	s=!printf("%d",s);
}

143B