これはなにか
paizaの10万登録ありがとうスペシャルWキャンペーンというのがありました。
総括するのが流行っているみたいなので、俺も俺も。
ちなみに、おじさんはC言語のみです。
アルゴリズム
- デカイ配列を用意しておく
- 読み込んだs_i*s_jにマークを付ける
- p_iから数えて、マークまで進んだ数を出力
コード
書き散らかして、どれを提出したのかわからなくなったので(ぉ
多分これだと思うやつ。
i,j,S[1<<20],F[4096];
main(X)
{
for(;~scanf("%d",F+i++);)
for(j=*S=*F+2;j<i;S[X<S-F?X:0]=1)
X=F[i-1]*F[j++];
for(i=1;++i-*S;printf("%d\n",j-X))
for(X=j=F[i];!S[j];++j);
}
fuyutsubakiさんのと基本同じですな。
解説という名の蛇足
- 配列FにM, N, p_m, s_nを読み込む。
- M = F[0], N = F[1], p_m = F[2 ..F[0]+2], s_n = F[F[0]+2 .. F[1]+2]に入っていることになります。
(*SにF[0]+2 == s_0の添字を入れてます) - 読み込んでいる最中に、X = s_i * s_jを計算して、デカイ配列Sに入るようならS[X]を1にします。
(入るかどうかチェックするのに、デカイ配列SのサイズをS-Fで計算していますが、逆(F-S)じゃないかと思われますが、手元のgccがそーいうコードを落とすのだから、しょうがない。) - p_mに対して、デカイ配列S[p_m]から0以外が出るまでの数を数えて出力します。
自己批判
- 最初、コードサイズのことを、「実行ファイルのバイト数」だと思いこんで、printfをputcharに書き換えたりして、考えすぎた。
- 1000000にこだわりすぎた。
- qsort関数で副作用をうまく利用してやろうと考えて、考えすぎた。
- 配列をcharとして扱って、マークまでの数をstrlen関数で求めようなどとして、考えすぎた。
- s_iとs_jが素なら中国の剰余定理が使えるんじゃね?と思って、興味が横道にそれた。
- 基本ゴルファーでないのに、無理しすぎた。
現場からは以上です。