1年間隔ぐらいで思い出したように参加している。

結果

oo-

Easy - TestTaking

class TestTaking {
public:
  int findMax(int _questions, int _guessed, int _actual) {
    return _questions - abs(_actual - _guessed);
  }
};

Medium - GridSort

ソート可能 \(\iff\) 全ての列で各要素を\(m\)で割った余りが同じ、かつ全ての行内で(各要素 - 1) / \(m\)が同じ

class GridSort {
public:
  string sort(int n, int m, vector<int> grid) {
    for(int i = 0; i < n; i++) {
      int div = (grid[i*m] - 1) / m;
      for(int j = 0; j < m; j++) {
        if((grid[i*m + j] - 1) / m != div) return "Impossible";
      }
    }
    for(int j = 0; j < m; j++) {
      int rem = grid[j] % m;
      for(int i = 0; i < n; i++) {
        if(grid[i*m + j] % m != rem) return "Impossible";
      }
    }
    return "Possible";
  }
};

Hard - SubsetSubExtreme

方針

各試行が独立で、プレーヤーがスコアの期待値を最小にするように振る舞うことを考えると、
ブロックの集合が\(B\)の時の期待値を\(E(B)\)とすると、
$$ E(B) = \frac{1}{N_{face}} \sum_{i=1}^{N_{face}} min(\lbrace sum(B) \rbrace \cup \lbrace E(B-S) \mid S \in \mathfrak{P}(B), sum(S) = face[i] \rbrace) $$

ただし\(\mathfrak{P}(B)\)は\(B\)のべき集合。

集合は\(i\)番目のbitが1なら含まれていて、0なら含まれていないという形でintにエンコードする。

時間計算量

ひとつのBに対しては、サイコロの面で\(N_{face}\)、掛ける、べき集合を回すので\(2^{N_{block}}\)。それをメモ化すれば与えられたブロックの全部分集合に対して1度ずつ計算することになるので、\( O(N_{face} \times 2^{N_{block}} \times 2^{N_{block}}) \)で、最大で10^8ぐらい。

コード

class SubsetSumExtreme {
public:
  vector<int> block;
  vector<int> face;
  vector<double> memo;
  vector<double> subsetSum;

  double getExpectation(vector<int> _block, vector<int> _face) {
    block = _block, face = _face;
    memo = vector<double>(1 << block.size(), -1.0);
    subsetSum = vector<double>(1 << block.size(), 0.0);
    for(int s = 0; s < (1 << block.size()); s++) {
      for(int j = 0; j < block.size(); j++) {
        if(s & (1 << j)) subsetSum[s] += block[j];
      }
    }
    return exp((1 << block.size()) - 1);
  }

  double exp(int blocks) {
    if(memo[blocks] != -1.0) return memo[blocks];
    double res = 0.0;
    for(int i = 0; i < face.size(); i++) {
      double subres = 0.0;
      for(int j = 0; j < block.size(); j++) if(blocks & (1 << j)) subres += block[j];
      for(int s = 0; s < (1 << block.size()); s++) {
        if(((blocks & s) == s) &&  subsetSum[s] == face[i]) subres = min(subres, exp(blocks &~ s));
      }
      res += subres;
    }
    res /= face.size();
    memo[blocks] = res;
    return res;
  }
};

感想

Hardは方針まではほとんどたっていたんだけど、細かい部分を詰めるところ、集合周りの実装で手間取って解ききることができなかった。悔しい。

コンテストに参加はしていなかったけど、MIT OCWのIntroduction to Algoriththmsの講義ビデオを眺めたりはしていて、少しは地力があがっているかもしれない。