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

夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

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

どーもー

今日の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が増えます。すると今まで1つ前と同じだったのが2つ周期になります。
よってnが4に2を足すたびにα=1になり、また3+2aの数においてはα=0になります。
そして今度はn=9になります。もうお分かりかと思いますがαはこうすると平方数だけみれば差が1の階差数列になることがわかります。
こうするとαに規則性が見いだせます。試しにn=16ぐらいまで確認してみるとよくわかります。

自信あったのですが、証明は雑になってしまいましたねw
でもこれよく考えてみると、階差数列の間に0からα-1までの階差数列2つが入っている構造ですから、だいぶいろんな解き方できますよね(笑)
ま、とりあえずプラクティスでちゃんと通ったインターミッション中の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);
            }
        }
    }
};

Xmas Contest 2011

こんなの知りません(笑)とりあえず感想だけ。

  1. A 出力にどういう制約があるのかが正しく把握できませんでした
  2. B とりあえず部分点狙いでワーシャルフロイドしました
  3. C なんかすごい問題だったけど難しいらしいです。といてません。
  4. D 文字列いじくりまわすやつです。やってません。
  5. E 一見簡単そうに見えてめちゃくちゃ満点とるの厳しいです。テストケースの8と10,11,14がコードによってACとWAが入れ替わるので萎えて25点
  6. F サンタさんがなにかやらかしました。
  7. G 難しいそうです。
  8. H なんで違うのか理解できません

まぁようするに無理でした(笑)

50点が限界です。暇になったら解説みます←
自力無理www

では
ばいちゃ

広告を非表示にする