SRM513

出ました。
久しぶりに500が解けたので大満足。
そして無事に黄色に戻りました。

◯◯× 407.35pt
Rating: 1416 -> 1545

250 YetAnotherIncredibleMachine

問題が非常に読みにくかった。
何かのゲームに基づいているらしいが、そのゲームを知らなかったので大変だった。

要約すると
何個か棒が別の高さにあって、それらは決められた範囲内で横にスライドできます。
上からボールを幾つか、場所固定で落とします。
ボールが棒に乗らない配置は何通りできるでしょう。
という問題。

各棒は独立に、そこにスライドしても問題無いかが決まるので、それぞれの棒の取れる位置の個数を掛ければ良い。
計算量的に問題なさそうだったので、全通り試した。
ちゃんとやりたければ、どこまで左に行けるかとどこまで右に行けるかを計算してごにょごにょすればいいと思う。

実装時に#defineに()をつけてなかったり、returnするのを忘れたりといった細かいミスをいろいろしたのですごく時間がかかってしまった。
これからはconst intにするべきか。そしてコンパイル時には-Wallオプションをつけろという教訓。

#include <iostream>
#include <sstream>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;

class YetAnotherIncredibleMachine {
public:
  int countWays(vector <int> platformMount, vector <int> platformLength, vector <int> balls);
  

};

#define MAX (20000 * 2 + 100)
int cnt[MAX];
const int base = MAX / 2;
const int mod = 1000000009;

int YetAnotherIncredibleMachine::countWays(vector <int> platformMount, vector <int> platformLength, vector <int> balls){
  long long ans = 1;
  int n = platformMount.size();

  REP(i, MAX) cnt[i] = 0;

  REP(i, balls.size()){
    for(int j = balls[i] + base; j < MAX; j++)
      cnt[j]++;
  }

  REP(i, n){
    int tmp = 0;
    const int pos = platformMount[i];
    const int len = platformLength[i];

    for(int j = pos - len; j <= pos; j++){
      const int left = j + base;
      const int right = j + len + base;


      if(cnt[left-1] == cnt[right]) tmp++;
    }

    ans = (ans * tmp) % mod;
  }

  return ans;
}

500 PerfectMemory

N*Mに敷き詰めたカードで神経衰弱するとき、完璧な記憶力を持っている場合にゲーム終了までの手数の期待値を求める問題。

一回も開いていないカードの枚数と一回でも開いたカード(でペアーになっていない)枚数でメモ化しながら全通り試すだけ。ただし、一回開いたカード同士でペアーは存在しないという制約をつける。
場合分けに手間取って結構時間がかかってしまった。
場合分けは、一回も開いていないカードを開いたときに

• 一回開いたカードと同じのを引く(ペアーを揃えれば良い)
• 一回も開いてないカードを引く(もう一枚引く)
  • たまたま揃う
  • 一回も開いていないカードを引く(単純に一回開いたカードが増える)
  • 一回開いたことあるカードを引く(制約を満たすように次のターンではそのカードを揃えたことにする)

という感じ。
以下コード。

#include <iostream>
#include <string>
#include <sstream>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;

class PerfectMemory {
public:
  double getExpectation(int N, int M);
};

double memo[2510][1260];

double solve(int unknown, int known){
  if(unknown == 0) return 0.0;
  if(unknown == 1) return 1.0;
  if(known == unknown) return static_cast<double>(known);
  if(memo[unknown][known] > -1.0) return memo[unknown][known];

  double ret = 0.0;

  double kp;

  if(unknown <= known) kp = 1.0;
  else kp = static_cast<double>(known) / unknown;

  // chose known one
  if(known > 0){
    ret += kp * ( 1 + solve(unknown - 1, known - 1) );
  }
  // chose unknown one
  if(unknown > known){
    double pp = 1.0 / (unknown - 1);
    
    // unknown one => same one
    ret += (1 - kp) * pp * (1 + solve(unknown - 2, known));

    if(unknown >= 2){
      double kpp = static_cast<double>(known) / (unknown - 1);

      if(known > 0){
	// unknown one => known one
	ret += (1 - kp) * kpp * (2 + solve(unknown - 2, known));
      }

      if(unknown - 1 > known){
	// unknown one => unknown one
	ret += (1 - kp) * (1 - (pp + kpp)) * (1 + solve(unknown - 2, known + 2));
      }
    }
  }

  return memo[unknown][known] = ret;
}

double PerfectMemory::getExpectation(int N, int M){
  int all = N * M;
  REP(i,all+1) REP(j,all/2+1) memo[i][j] = -2.0;
  return solve(N*M, 0);
}

まとめ

英語が若干読みづらかったのと、細かいミスの積み重ねで結構ロスしてしまった。
それがなければ結構いい順位にいけてただけにもったいない。
細かいミスに関しては、最近あんまり練習していなかったのでしょうがないかも知れないが頑張りたいところ。

あんまり関係ないがKUPCは非常に楽しみ。
オンサイトに申し込んだのにレスポンスがないのは仕様だろうか、ちょっと心配。