1-250pt問題

Nコンタクトをうまくグループ分けしてコンタクトを見つけるまでにかかる時間を最小にしろという問題。nグループに分けた場合、まずグループを捜すのにn秒、そしてそのグループから実際のコンタクトを見つけるのにN/n秒かかる。例えば5コンタクトを2グループに分ける場合、2+ceil(N/2) == 5秒かかる。

groups.py:

from math import ceil

class IMGroups:
  def optimalTime(self, N):
    res = 1000000
    for i in range(1, N):
      tmp = int(i + ceil(float(N) / i))
      if tmp < res:
        res = tmp
    return res

1-750pt問題

N queensの変形。正方のチェスボードが与えらえれk個のビショップを置くパターンの数を計算して下4桁の数をかえせという問題。なおいくつかのセルは破壊されていてそこにビショップを置くことができないという制限がついている。僕が自分で解いた方法は総当たりによる方法で、わかりやすく直接的ではあるけど実行時間がかなりぎりぎりなので他の方法を紹介。簡単に説明するとビショップを置くパターンと置かないパターンでなめるようにdiagをスキャンしていくようになっている（たぶん）。memset(memo, -1, sizeof(memo))はなるほどと思った。

bishops.cpp:

#include <iostream>
#include <vector>
#include <string>

#define MOD 10000

using namespace std;

int n;
int memo[18][1 << 15];
vector<string> b;

int go(int k, int d1, int mask) {
    int& res = memo[d1][mask];
    if (res != -1) return res;

    if (k == 0) return res = 1;
    if (d1 >= 2 * n - 1) return res = 0;

    res = go(k, d1 + 1, mask) % MOD;
    for (int i = 0; i < n; i++) {
        int j = d1 - i;
        int d2 = n - 1 + i - j;

        if (i < 0 || i >= n || j < 0 || j >= n) continue;

        if (!(mask & (1 << d2)) && b[i][j] == '.') {
            res += go(k - 1, d1 + 1, mask ^ (1 << d2));
            res %= MOD;
        }
    }

    return res;
}
 
class Bishops {
public:
    int count(int k, vector<string> board) {
        n = (int)board.size();
         b = board;
        if (k > 2 * n - 1) return 0;
        memset(memo, -1, sizeof(memo));
        return go(k, 0, 0);
    }
};

#if 0

int main() {
    vector<string> board;
    board.push_back("........");
    board.push_back("......#.");
    board.push_back("........");
    board.push_back(".#......");
    board.push_back("........");
    board.push_back(".....#..");
    board.push_back("........");
     board.push_back("...#....");

    Bishops bishops;
    cout << bishops.count(7, board) << endl;

    return 0;
}

#endif

2-250pt問題

シャッフルする種をあたえられ、それを使って1, 2, 3, ..., nなデッキをn回シャッフルしろという問題。

shuffler.py:

class DeckShuffler:
  def getDeck(self, n, shuffled):
    res = range(1, len(shuffled) + 1)
    while n > 0:
      tmp = res[:]
      for i, x in enumerate(shuffled):
        tmp[i] = res[x - 1]
      res = tmp
      n -= 1
    return res

2-750pt問題

Qualification Set 1の750pt問題と同じ。

3-250pt問題

レフリーの全行動が[YR] MINUTES NAMEという形式であたえられるので、それの間違いを見付けて最も最初に間違った時間をかえせという問題。たとえば二回目のイエローカードなのに同時間にレッドカードがでてないなど。完璧なコードを書くのが結構むずかしい。と、思ってたら以下のようにすれば簡単にかつ完璧にできることが発覚。さすがですk.inabaさん、あとからレッドカードを検索する発想はなかったわ。なんていうかイエローカードのチェックのifの次にelifとして書きたい衝動にかられる。そっちのほうが美しいみたいな。でも実際そうすると逆に問題が難しくなる。いやはやアルゴリズムは奥が深い。

http://www.kmonos.net/wlog/sub/gcj06_q250.py

3-750pt問題

Permanentとかいうやつを計算しろという問題。The parmanent of nxn matrix A is equal to the sum of A[1][p[1]] * A[2][p[2]] * ... A[n][p[n]] over all permutations p of set {1, 2, ..., n}. ということらしい。前から思っていたんだけど、set {1, 2, ..., n}のall permutationsってなにかとても簡単な方法で生成できないのかな。結構用途多いわりにいざ作るとなると再帰やらスタックやらで生成しないといけなくて面倒くさい。で、問題は解けたんだけど遅すぎてtestとおらない。c++で書きなおす気もおこらず、上と同じようにk.inabaさんのコードを掲載。僕のpythonのプログラムにmemoizationつければk.inabaさんのと同じになるけど、面倒なのでいいや。

http://www.kmonos.net/wlog/sub/gcj06_q750.py

4-250pt問題

(n,m)のボードから最大の正方（含有可能な正方をはぶくという意味）を抽出してその数をかえせという問題。たとえば

AAB
AAB
BBB

は2x2のAの正方が1個、1x1のBの正方が5個で計6。Constraintsがゆるいのでごりごり処理しても余裕。まあ工夫するとしたらcoloringして四隅のcolorをチェックすることにより含有をチェックするようにするとか。追記、rは最大にしちゃだめだ。修正面倒なのでこのまま。

square.py:

class SquareCounting:
  def howMany(self, grid):
    w = len(grid[0])
    h = len(grid)
    sq = {}
    res = 0
    def row(c, l, t, r):
      while l < r:
        if grid[t][l] != c:
          return False
        l += 1
      return True
    def include(c, l, t, r, b):
      for s in sq.get(c, []):
        if s[0] <= l and s[1] <= t and s[2] >= r and s[3] >= b:
          return True
      return False
    for l in range(w):
      for t in range(h):
        c = grid[t][l]
        r = l + 1
        while r < w and grid[t][r] == c:
          r += 1
        b = t + 1
        while b < h and row(c, l, b, r):
          b += 1
        r = l + min(r - l, b - t)
        b = t + min(b - t, r - l)
        if not include(c, l, t, r, b):
          sq.setdefault(c, []).append([l, t, r, b])
          res += 1
    return res

4-750pt問題

Qualification Set 3の750pt問題と同じ。

5-250pt問題

y < x < zのf(x)がy, zのfに関してconvexになっている場合その総数をかえせという問題。convexというのはy, zの直線((y, f(y)), (z, f(z))より点(x, f(x))が上にある場合をいうらしい。y, zはつまりx - 1, x + 1ということだと決めつけて？になっていたことは秘密。上にあるかはy, zの傾きa1とx, yの傾きa2の比較でチェックできる。これもかなりごりごりと処理。floatいるかは不明。

convex.py:

class ConvexityIssues:
  def howMany(self, values):
    res = 0
    n = len(values)
    for i in range(n - 2):
      for j in range(i + 2, n):
        a1 = float(values[j] - values[i]) / (j - i)
        for k in range(i + 1, j):
          a2 = float(values[k] - values[i]) / (k - i)
          if a1 < a2:
            res += 1
    return res

5-750pt問題

Qualification Set 3の750pt問題と同じ。

Bishopsの問題が一番むずかしかった。でも一番収穫があったのもBishops。特にgo(k, ...)とgo(k - 1, ...)の使いわけによって配置パターンをすべて表現してしまうのには感心した。来年もがんばろう。

P.S. reStructured Textは使いにくくてしょうがない。