プロコンなクリスマス・イブ

どーもー

今日のTopCoderは一完の1043->1021でした。
まぁ、緑キープできたというだけでも、だいぶ安心感ありましたわな。

いや、そうとうまずったというか惜しいするめでしたが・・・

MagicStonesStore

ゴールデンバッハ予想です。
問題真面目に読んでたら、早解きはできませんでしたorz

class MagicStonesStore {
public:
   string ableToDivide( int n ) {
    bool p[5000];
    fill(p, p+5000, true);
    p[0]=p[1]=false;
    for (int i=2; i<5000; i++) {
        if (p[i])
            for (int j=i*2; j<5000; j+=i) p[j]=false;
    }
    for (int i=n; i>=n/2; i--) {
        if (p[i]&&p[(n-i)+n]) return "YES";
    }
    return "NO";
   }
};

MagicCandy

これです。
インターミッション中に正解という（汗）
僕は

入力をn,n以下の最大かつ1を0番目としたときk番目の平方数をpとすると
1.nが平方数のとき
result=n-k
2.n-pがk+1で割り切れるとき
result=n-k+1
3.n-p%k+1=xのとき
result=n-x+1

であることを利用してときました。
でもいざChallengeみてみるとこの解き方してる人が一人もいない(^_^;)

で、おとせませんでした・・・
ちなみに僕の解法は簡単に証明できます。

まずn=1の答えは1です。この時nと答えの差は0になっています。これからこの差をαと呼びます。
僕の解法ではこれを場合分けしながら計算しています。
まずnが平方数でない場合を考えます。これは、最初に平方数を引くとより小さい数の場合に帰着します。
この時nより小さい平方数の数がk+1なのでnはn-k-1と同じです。
ここでdpが思いつくと思いますが（実際僕もこれを思いつきました)nがとても大きいので無理です。
というわけでαを考えるわけです。
当然3まではすべてα=0になります。そしてn=4になって初めてこれが変わります。
この時αは1になりますが、これは4自身が最初になくなってしまうからです。
すると今度はkが増えます。すると今まで１つ前と同じだったのが２つ周期になります。
よってnが4に2を足すたびにα=1になり、また3+2aの数においてはα=0になります。
そして今度はn=9になります。もうお分かりかと思いますがαはこうすると平方数だけみれば差が1の階差数列になることがわかります。
こうするとαに規則性が見いだせます。試しにn=16ぐらいまで確認してみるとよくわかります。

自信あったのですが、証明は雑になってしまいましたねｗ
でもこれよく考えてみると、階差数列の間に0からα-1までの階差数列２つが入っている構造ですから、だいぶいろんな解き方できますよね（笑）
ま、とりあえずプラクティスでちゃんと通ったインターミッション中のACコードを

class MagicCandy {
public:
    int whichOne( int n ) {
        int i;
        vector<ll> sq;
        for (i=1; i*i<=LIM; i++) sq.push_back(i*i);
        sq.push_back(i*i);
        for (i=0;; i++) {
            if (sq[i]==n) {
                return n-i;
            } else if (sq[i]>n) {
                if ((n-sq[i-1])%i==0) return n-i+1;
                else return n-((n-sq[i-1])%i-1);
            }
        }
    }
};