SRM diary(Sigmar)

SRM478 Div1 250 CarrotJumping

SRM478, Div1 | 00:12 |

Problem Statement

問題を見る

→Hanako・・？これがいわゆるrngさんというやつだろうか

→普通に探索すると、2^10万？？うむ・・何だこれは・・・全然分からない

→DPか・・？うーん状態数が多すぎる・・違う・・逆方向に探索？・・・意味ないな・・分からん・・

→（20分くらい悩む）

→というか250点なんだから、何か簡単に解く方法があるはずだ

→こういう分からないときはとりあえずシミュレーションしてみるに限る

→えーと・・4x+3を2回適用すると16x+15、3回で64x+63

→8x+7を2回適用すると64x+63・・・

→・・・ん？

→全然分岐しないじゃないか

→4x+3を15万回くらい繰り返して適当に帳尻合わせれば解ける気がしてきた

→書く→サンプル合わない

→4x+3だけ適用しているから、8x+7を1回適用でOKの場合が探索できないのがまずいみたい

→4x+3と8x+7はどちらから適用しても32x+31となり、順番には依存しないので、探索の途中で毎回8x+7追加適用を試すように変更

→書く→サンプル通る

→サンプルが網羅的な感じのケースで親切だから問題なさそうかな

→提出

チャレンジフェーズ

→みんな色んな解き方してるみたいだなぁ

→何か良く分からない。サンプル親切だし落とせそうなケースも思いつかないな

→何もせず

システムテスト

→Passed

以下、ソースです。

25分くらいかかってしまったので、もっと早くシミュレーションすれば良かった・・・

const int MOD=1000000007; 

class CarrotJumping { 
public: 
  int theJump(int init) { 
    if(init==0) return 0; 
    for(int i=1; i<=150000; i++) { 
      int tmp=((ll)init*8+7)%MOD; 
      if(tmp==0) { 
        if((i-1)/3*2+(i-1)%3+1>100000) return -1; 
        return (i-1)/3*2+(i-1)%3+1; 
      } 
      init=((ll)init*4+3)%MOD; 
      if(init==0) { 
        if(i/3*2+i%3>100000) return -1; 
        return i/3*2+i%3; 
      } 
    } 
    return -1; 
  } 
}; 

SRM478 Div1 500 KiwiJuice

SRM478, Div1 | 00:12 |

Problem Statement

問題を見る

→いかにもDPな感じ

→とりあえず、1回pourすると最低1本は満タンか空になるので、それはSellする

→うーむ・・・もう1本新たな量のボトルができてしまうので、状態数が膨大になってしまう。

→分からん・・・

→グラフ・・？違う・・マッチング・・？違う・・・ツリー？違う・・・

→（ひとしきり堂々巡りする）

→やっぱりDP以外では解けないだろう。何か部分的にGreedyにするとか、もっと計算量を減らす方法があるはずだ。

→例えば、ボトルをグループ化するとか・・でも、グループ分けの状態数はすごく多くなるから無理か・・

→いや、グループ化は使える気がする・・

→あるボトルの組み合わせを選んだとき、それらを全て互いにpourしてしまうと、最大1本だけ満タンでも空でもないボトルができて、あとのボトルは満タンか空になる

→ボトルの組み合わせが一緒なら、どんな順番でpourしても必ず最終的な状態は同じになるのでは・・

→うん・・なる気がする

→ということは、全部互いにpourするボトルの組み合わせを選んでsellし、残りを再帰的に計算すれば良いのでは

→計算量が最悪2^15*2^15で10億くらいになる気がするが・・再帰的にする以上ボトルは減っていくのでそんなに大きくならないはず

→正確には計算量は分からないけど、もう時間がない。これで解くしかない。

→書く→無限ループする

→ボトル組み合わせの選び方が間違ってる

→直す→ローカルでサンプル3まで通るが4が終わらない

→アリーナで4をテスト

→通った！→提出

→残り30秒だったのでほとんどコーナーケースとかチェックできてない・・通ったらラッキーくらいかな・・

チャレンジフェーズ

→500は自分含め4人しか出てない

→一人は速攻で撃墜される

→他の人を見ると、一人は自分と同じような感じ、もう一人は・・ちょっとやり方が違うみたいだけど・・よく分からない

→サンプルケースが親切なようだから、突っ込みどころが思いつかない

→自分のプログラムの検証でもするかな

→以外とミスが見当たらない。もしかして行けるかも。

システムテスト

→Passed

やった・・終了30秒前に提出してPassとか奇跡的すぎる・・

以下、ソースです。

どたばたしていたので読みづらい感じ。

（8/5 23:05追記）

計算量ですが残りボトルを表す(maskの)ビットが1のときのみ、pourするボトルとする(useに1を立てる)かどうかを選択するので、実質ループ数は3^15になりますね。

内部でも足し算15回のループを回しているので、足し算は2億回くらい。ぎりぎり間に合うようなレベルです。

ビットDPで部分集合を全て選択するような更新をする場合の計算量は3^nと覚えよう。。

int memo[1<<16];

class KiwiJuice { 
public: 
  vector <int> b, p; 
  int bsz; 
  int C; 

  int rec(int mask) { 
    int res=0; 

    if(mask==0) return 0; 
    if(memo[mask]>=0) return memo[mask]; 
    for(int use=mask; use>0; use--) { 
      int tmp=0; 
      use&=mask; 
      if(use==0) break; 
      int tot=0; 
      //pourするボトルのトータルのジュース量から販売額を求める
      //ここはできればメモ化したほうが良かったかもしれない
      for(int i=0; i<bsz; i++) { 
        if(use&(1<<i)) tot+=b[i]; 
      } 
      int fullb=tot/C; 
      tmp+=fullb*p[C]; 
      tmp+=(__builtin_popcount(use)-fullb-1)*p[0]; 
      tmp+=p[tot%C]; 
      tmp+=rec(mask^use); 
      res=max(res, tmp); 
    } 

    memo[mask]=res; 
    return res; 
  } 

  int theProfit(int _C, vector <int> bottles, vector <int> prices) { 
    int res=0; 

    memset(memo, -1, sizeof(memo)); 
    C=_C; 
    //sortしているが余り意味はない
    sort(bottles.begin(), bottles.end()); 
    p=prices; 
    b.clear(); 
    //何となく最初から空と満タンのボトルは抜いておいた
    for(int i=0; i<(int)bottles.size(); i++) { 
      if(bottles[i]==0 || bottles[i]==C) { 
        res+=prices[bottles[i]]; 
        continue; 
      } 
      b.push_back(bottles[i]); 
    } 
    bsz=b.size(); 

    res+=rec((1<<bsz)-1); 

    return res; 
  } 
};