cafelier@SRM

SRM453.5

SRM | 03:22 |

SRM453.5 の成績・ソース (要ログイン) : AC/AC/- : 惜しかった

450開く

• 『頂点数V辺数Eの平面グラフはV*V*V+E*Eポイントです。ちょうどNポイントにするには何個平面グラフが要りますか』
  • 同じ形のグラフを何個使ってもいい
  • N<=50000

• えーと、V*V*V+E*E <= N の平面グラフ全部列挙して
• その幅で0からNまで何歩でいけるか幅優先探索で求めればいい

• 平面グラフは…
  • 連結でなくていいらしいので V*V*V+0*0 のは全部作れる
  • 頂点数Vに対して最大のEっていくつだろう。
  • V=3なら三角形のときのE=3
  • それより大きいときは、V-1の時の最大パターンの中の三角形の真ん中に頂点増やすとEは3増やせる、というのがきっと最大ぱたーんなので
  • Vを1増やすとEの最大値は3増える

• というわけで可能なN以下のV*V*V+E*Eを全列挙
  • Eの最大値を表す変数はEMaxだ。emacs!
  • けっこう候補多いなー。
  • 幅優先探索で最悪このサイズ×Nの時間かかるけど大丈夫かな
  • まあいいややってみよう
• やってみた
• 遅い
• V*V*V+E*E のうち大きい方から使うようにしてみるヒューリスティックス
• 速い

• ってかN=50000のとき2個で終わるらしい。
• これじゃ速すぎる。最悪ケースになってないかも…
• もっとステップ数がかかりそうな例は…
  • よくわからないから N=1～50000 まで全部動かしてみる
  • ...
  • まだ10000くらいまでしか終わってないけど、答えが全部 2 になってるなあ。
• ということは50000までやっても最悪でも答えは 10。
• たぶん大きいと常に答えは 2 になるっぽい。
• なら計算量は全然問題ないや

• しかし本当か、答えが全部 2 って。バグってないか
• でも小さいところではサンプルとあってるし
• まいっか、出しちゃえ。

250開く

• 『最大50x50の迷路があります。スタートは固定です。動けるマスは上下左右とかではなくて、(1,-3)または(40,0)ジャンプできる、みたいになんか変な動き方が与えられます。ゴールを好きな所に置いて、できるだけ脱出に時間がかかるようにしてください』
  • 脱出不能な出口を作れるならなおよい

• 幅優先するだけだ
• ガリガリガリガリ
• 書いた

• サンプル通った
• 出しちゃえ
• えーと50x50で、動き方候補も50だから、最悪でも50^3で終わるはず。問題ない

• しかしちょっとコード書くのに時間かけ過ぎた…
• みんな速いなあ
• BFSとかDFSはもっとライブラリ化しておこうかなあ
• 結構いつも不必要に手間取ってる気がするし

1000開く

• 『10進表記で全部の桁が4か7な数をLucky Number、その倍数をAlmost Lucky Numberといいます。与えられた区間 [a,b] にあるAlmost Lucky Numberの個数は何個でしょう』
  • 1≦a≦b≦100億

• 100億という見た目にだまされてはいけない
• Lucky Number は以外と少ないはずだ
• 10桁以下のを考えればいいので、d桁のLuckyNumberは2^d個だから…
• 2046個しかない！

• いやーでも Almost Lucky Number はやっぱり沢山あるよ

• 44 は 4 の倍数だから、
  • Almost Lucky を考えるときに 44 の倍数は考えなくても 4 の倍数に全部含まれる
• という風に純粋倍数を除いたら凄い少なくなるのでは
• 少なくとも下二桁が44のは全部消えるからまず3/4に…
• 半分強になった。でもまだ多いなあ。

• Lucky Number が少なければ包除原理でいいんですよ。
  • もし Lucky Number が 4 だけだったら、
    • 4の倍数の個数 = b/4 - (a-1)/4 で求まる
  • もし Lucky Number が {4,7} だけだったら、
    • 4の倍数の個数 + 7の倍数の個数 - 28の倍数の個数
  • これは O( 2^LuckyNumberの数 ) くらいの計算量
  • ちょっと1000も残ってると無理…

• あるいは、区間 [a,b] が狭ければエラトステネスの篩っぽく…というと違うかな、こんな風に…
  • Lucky Number が {v1, v2, ...} だったら、
  • for(n=a以上の最小のv1の倍数; n<=b; n+=v1) nをAlmostLuckyリストに追加
  • for(n=a以上の最小のv2の倍数; n<=b; n+=v2) nをAlmostLuckyリストに追加
  • ...
• こうやれば、O( |b-a| * LuckyNumberの数 ) くらい
• もっと小さく見積もれるか
• O( |b-a| * LuckyNumberの数 / 最小のLuckyNumber ) くらい
  • といっても最小のLuckyNumberは4だからせいぜい4倍くらい
  • 最悪|b-a|=100億だから、無理だなあ…

• ぴこーん！

• ２つ合わせればいいんじゃね？

• LuckyNumberのうち、小さい方4個{4,7,47,74}については包除原理で数える
• 残りは、エラトステネス風（？）で数える。
  • ただし
    • for(n=a以上の最小のv1の倍数; n<=b; n+=v1) if(nが最初の4個の倍数でなければ)nをAlmostLuckyリストに追加
  • こうする

• 5番目は、447だから、最悪計算ステップは
  • 2^4 + 100億*4 / 447
• くらい。
• うーん1億オーダ
• 4個なんて決め打たないで可変にして速そうなのを採用しよう
  • 2^M + 100億*M / (M+1番目に小さいLuckyNumber)
• くらい。

• 行ける！
• 実装！
• できた！
• 最悪ケースで！
• N=16～18 辺りが速いんだけど、4秒かかる！

• あと2倍の高速化を…
• うーん
• うーん

• vectorを配列に…
• % や / をできるだけいらない形に…
  • 等々思ったけど、ボトルネックそこじゃないな。setに挿入してる部分だ。

• ここはsetをvectorにしてみる！
  • 実はfindする必要はなくて最後に個数さえ数えられればいいので、
  • sorted vectorである必要すらない。挿入はpush_backで十分
  • ただ、重複をまったく除かないとメモリ食い過ぎるので
  • 要素数1000万を超えたら定期sortしてuniqueタイムとする！

• できた
• うおーあと20秒
• 手元で最悪ケース…2.05秒！これは勝つる
• compile！
• compileがおわらない！
• あと2秒！先行submitボタンを押すとどうなる！
• 「直前の操作が完了してませ～ん m9(^Д^)ﾌﾟｷﾞｬｰ」的なメッセージが
• そして「コンパイル終わったよ」と「コンテスト終了だよ」メッセージが立て続けに
• おわた...

撃墜フェーズ

• 450と1000が結構どんどん落ちてたので
• ろくにソース読まずに最大ケース投げつけてみる
• 2回失敗
• おわた…

感想

• 1000はpracticeに投げたら通りました。無念
• まあ、250と450のようなただの幅優先探索の実装に時間かけ過ぎてるのが良くない。要修行
• あと、こんなゴリ押しはそもそも想定解ではないような気もする。要修行
  • ※追記：
  • ※そうかー、単に包除原理だけでいいのか！
  • ※何個かlcmとるとすぐbを越えるから2^1000通り全部考える必要なんてなくて、
  • ※lcmでかすぎたらさっさと切ればいい。なるほどなー。
  • ※
  • ※そもそも、てことは、自分の16個のlcmってもしかしてオーバーフローしてるんじゃないのか
  • ※通るのはすごく偶々だったように思えてきた。うーむだめぽ

• ↓1000のソース

typedef long long LL;

LL gcd(LL a, LL b)
{
   while(a)
      swap(a, b%=a);
   return b;
}

LL lcm(LL a, LL b)
{
   return a/gcd(a,b)*b;
}

class TheAlmostLuckyNumbers { public:
   void genLuck(vector<LL>& v)
   {
      // lucky numbers
      vector<LL> u;
      for(int d=1; d<=10; ++d)
         genLuck(d, u);

      // filtering
      for(int i=0; i<u.size(); ++i)
      {
         for(int j=0; j<i; ++j)
            if( u[i] % u[j] == 0 )
               goto next;
         v.push_back( u[i] );
      next:;
      }
      sort(v.begin(), v.end());
   }

   void genLuck(int d, vector<LL>& v)
   {
      // d-digit lucky numbers
      for(int b=0; b<(1<<d); ++b)
      {
         LL n = 0;
         for(int i=0; i<d; ++i)
            n = n*10 + (b&(1<<i) ? 4 : 7);
         v.push_back(n);
      }
   }

   long long count(long long a, long long b) 
   {
      vector<LL> v;
      genLuck(v);

      static const int M = 16;

      // inclusion-exclusion
      LL cnt = 0;
      {
         for(int m=1; m<(1<<M); ++m)
         {
            int bc = 0;
            LL n = 1;
            for(int i=0; i<M; ++i)
               if( m & (1<<i) )
                  ++bc, n=lcm(n, v[i]);
            cnt += (bc&1) ? (b/n-(a-1)/n) : -(b/n-(a-1)/n);
         }
      }

      // sieve
      vector<LL> aml; // almost lucky numbers
      for(int i=M; i<v.size() && v[i]<=b; ++i)
      {
         LL u = v[i];
         for(LL s=a%u?(a/u+1)*u:a; s<=b; s+=u)
         {
            for(int k=0; k<M; ++k)
               if( s%v[k]==0 )
                  goto next;
            aml.push_back(s);
         next:;
         }
         if( aml.size() > 10000000 ) {
            sort(aml.begin(), aml.end());
            aml.erase(unique(aml.begin(), aml.end()), aml.end());
         }
      }

      sort(aml.begin(), aml.end());
      aml.erase(unique(aml.begin(), aml.end()), aml.end());
      return cnt + aml.size();
   }
};