1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

paizaの10万登録ありがとうスペシャルの始末記

Posted at

これはなにか

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が素なら中国の剰余定理が使えるんじゃね?と思って、興味が横道にそれた。
  • 基本ゴルファーでないのに、無理しすぎた。

現場からは以上です。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?