cafelier@SRM

SRM494

SRM | 13:37 |

SRM494 の成績・ソース (要ログイン) : AC/AC/- : 花を摘んで花びら千切りながら「期待値、線形性、期待値、線形性、…」と占いを始めなければいけないレベル

500

• 『木がN本ならんでます。i本目の木の高さ a[i] は、low[i] から high[i] の間のランダムな整数で決まります。a[0]＜a[1]＞a[2]＜a[3]＞... または a[0]＞a[1]＜a[2]＞... のように高さが交互に増減してたら Σ|a[i]-a[i+1]| がスコアで、そうなっていなければ交互になるように木を何本か引っこ抜いた時の最大スコアがスコアです。スコアの期待値を求めよ。』
  • N≦50、high[i]≦10万

• ポイントとしては、「交互に増減」とか引っこ抜くかは罠で、常に単純に
  • Σ|a[i]-a[i+1]|
• がスコアになるのですね。
• 交互になってなかったら a＜b＜c みたいなのの b を引っこ抜いてスコアを |a-c| にするだけなので、|a-b|+|b-c| と変わらない

• というわけで答えは
  • E( Σ|a[i]-a[i+1]| )
• なのだけど、これは
  • Σ E(|a[i]-a[i+1]|)
• に等しい。(期待値の性質)
• というわけで、各区間毎に E(|a[i]-a[i+1]|) を求めて和をとるだけ。
  • E(|a[i]-a[i+1]|) は本当に定義通り計算すると 10万^2 で間に合わないけど
  • 定数時間で求めるように頑張る必要まではないので適当に

class AlternatingLane { public:
   double expectedBeauty(vector <int> low, vector <int> high) 
   {
      double eSum = 0.0;
      for(int i=1; i<low.size(); ++i)
      {
         // ランダムに
         //   h ∈ [low[i-1], high[i-1]]
         //   g ∈ [low[i],   high[i]  ]
         // を取ってきたときの、|h-g| の期待値…
         double e = 0;
         for(int h=low[i-1]; h<=high[i-1]; ++h)
            if( h <= low[i] )
               e += sequenceSum(low[i]-h, high[i]-h);
            else if( high[i] <= h )
               e += sequenceSum(h-high[i], h-low[i]);
            else
               e += sequenceSum(0, h-low[i]) + sequenceSum(0, high[i]-h);
         eSum += e / (high[i]-low[i]+1) / (high[i-1]-low[i-1]+1);
      }
      return eSum; // …の和、が答え
   }

   LL sequenceSum(LL a, LL b) // a+(a+1)+...+b
   {
      return (a+b) * (b-a+1) / 2;
   }
};

• 本番提出したコードもだいたいほぼ同じ。
• 期待値の問題が出たら、「何も考えずDPを始める」んじゃなくて、「まず期待値の性質をつかって問題を簡単にする」方向を真っ先に考えるようにしないとダメだなあ…

250

• 『最大50×50の２次元グリッドがあります。各マスは、黒く塗りたいか白いまま残したいかどっちかです。S×S サイズの正方形黒塗りスタンプだけを使って、白領域にはみ出ないようにちゃんと塗れる最大の S は？』

• 本番は「for each マス: それを覆える正方形の最大サイズを計算 → その最小値」
• と考えていて50の6乗以上のオーダのものしか思いつかず七転八倒していました。

• 考えてみれば、盤面サイズ N × N とすると
  • スタンプの置き方は (N-S+1)(N-S+1) 通り
  • そこを塗れるかどうか(白がないか)判定して塗るのは S^2 時間
  • Sはせいぜい最大でもN
• なので、地道に全部塗っても
  • Σ_{S=1～N} (N-S+1)(N-S+1)S^2 ＜ N^5/3
• 行ける

class Painting { public:
   int largestBrush(vector <string> picture) 
   {
      const int Y = picture.size();
      const int X = picture[0].size();

      int best = 1;
      for(int S=2; S<=min(Y,X); ++S)
      {
         vector<string> duty = picture;
         for(int y=0; y+S<=Y; ++y)
         for(int x=0; x+S<=X; ++x)
            if( all<'B'>(picture, y, x, y+S, x+S) ) // SxS の範囲が全部黒なら
               fill<'W'>(duty, y, x, y+S, x+S); // ここは塗れる
         if( all<'W'>(duty, 0, 0, Y, X) )
            best = max(best, S); // 全部塗れてたらベストスコア更新
      }
      return best;
   }

   template<char color>
   bool all(const vector<string>& p, int ys, int xs, int ye, int xe)
   {
      int cnt = 0;
      for(int y=ys; y<ye; ++y)
      for(int x=xs; x<xe; ++x)
         cnt += (p[y][x]==color);
      return cnt == (ye-ys)*(xe-xs);
   }

   template<char color>
   void fill(vector<string>& p, int ys, int xs, int ye, int xe)
   {
      for(int y=ys; y<ye; ++y)
      for(int x=xs; x<xe; ++x)
         p[y][x] = color;
   }
};

• 反省点としては、前回に引き続き
  • for(S=min(Y,X); S>=2; --S) {if(canPaint)return S;} return 1; や
  • bool all(){ for(y) for(x) {if(p[y][x]!=color) return false; } return true; }
• みたいな、データによって時間がかわるコードを本番で書いてしまったことで
• 「50^5 の時間はキツそうに見えるが定数係数小さいので余裕なはず」
• という状況なんだから、一目で最悪ケースがわかるコードを書かないとダメでした…
• 焦るとロクなことがない。

• ところで、色々考えても正解がなかなか思い浮かばない…という状況は悪いことばかりでもないなあ、とプラス思考で思ってみたのは
• ニセ解法を色々考えて「これは行けるか？」「こういう反例がある。ダメだ」を繰り返すので
• つまり、撃墜用データが手元に溜まる

WWBBWW
WBBBBW
BBWWBB
BBWWBB
WBBBBW
WWBBWW

• 今回は「縦と横別々に見て、一番"細い"ところの細さが答え？」を自己撃墜した↑でチャレンジフェーズで+100ゲット。やったね！