本稿はCodeIQで2015年1月22日～2015年2月16日に出題された「わんにゃんキャッスル」という問題の解法に関する記事です。

わんにゃんキャッスル【解説】

◆高速に解を得るアルゴリズム

1000×1000の正方形があるかどうかを調べ、なければ999×999の正方形があるかを調べ…というふうに、考え得る最大のサイズから順に調べていけば、最初に見つかった正方形が最大サイズになります。しかし正方形のサイズが小さくなる度に、正方形の個数はどんどん増えて行きますし、サイズが変わるたびに正方形ができているかを調べるため、同じような計算を繰り返してしまうことになります。

そこで、少し数え方を工夫します。map上の隅の部分から順番に調べる際、その地点を角とした正方形の最大サイズがいくつになるかを記録しながら調べていきます。具体的な例を見てみましょう。

このmapで、「W」の正方形でサイズが最大になるものを見つけてみましょう。

まず一番上の行を見て、{ W -> 1 }, { N -> 0 }と置き換えていきます。

2行目からは、次のようなルールで置き換えます。

(1)Nの場合: 0とする

(2)Wの場合: 上・左上・左のマスがすべて1になら2に、そうでければ1にする

このようなルールで2行目を数値に置き換えていくと次のようになります。

1か所だけ「2」になっている部分があります。これは、その地点から左上に向かって2×2の正方形を作ることができるという意味になります。3行目以降も、同様にして数字を割り当てていきます。3行目以降は0と1以外の数も出現しますので、先程のルールを少し変更します。

(1)Nの場合: 0とする

(2)Wの場合: 上・左上・左の、『各マスの最小値 + 1』にする

上図は3行目の途中の状態ですが、上に1×1の正方形・左上に2×2の正方形・左に1×1の正方形があります。水色の部分から黄色い部分を含む正方形を作ると2×2のサイズになっていることがわかります。このルールで最後まで走査すると、次のようになります。

一番右下の部分に「4」という数があり、4×4の正方形を作ることができるという意味ですので、最大の正方形サイズは4ということになります。

このように、左上から右下に向かって1巡走査するだけで最大の正方形を見つけることができました！このアルゴリズムを、C++で次のように次のように実装してみました。

/*
   g++ solve.cpp -std=c++11
*/
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

void solve(vector<string> &v, char c)
{
  int n = v.size();
  vector< vector<int> > z(n);
  int m = 0;

  for(int y=0; y<n; ++y){
    z[y].resize(n, 0);
    for(int x=0; x<n; ++x){
      if( c != v[y][x] ) continue;
      z[y][x] = 1;
      if( y>0 && x>0 ) z[y][x] += min({ z[y-1][x-1], z[y-1][x], z[y][x-1] });
      m = max( m, z[y][x] );
    }
  }
  cout << c << ": " << m << endl;
}

int main()
{
  vector<string> v;
  // cinの代わりにscanfを使うと速いよ！
  for(string s; cin>>s; ) v.emplace_back(s);
  solve(v, 'W');
  solve(v, 'N');

  return 0;
}

mapデータを実際に数値で潰してしまうわけではなく、別に配列を用意して数値を埋めていきます。数値で埋めつつ最大値を更新するようなプログラムになっています。

◆ビット演算を利用した高速解法

map上で、数えたい勢力を1、そうでないものを0とすると当然01の表現になるわけで、ビット演算を利用することも可能です。ただし、本問ではmapのサイズが1000×1000ですので、多倍長演算が容易である言語を選択する必要あります。

次のようなビット列で具体的に考えてみましょう。

「1」が4つ連続した部分と、2つ連続した部分があります。このビット列と同じものをもう1つ用意し、1ビットずらします。

これらの論理積を取り、上下ともに「1」になっているビットは「1」、それ以外は「0」になるようにします。

するとこのように、連続する「1」が1ずつ減っていることがわかります。さらにこの操作を、もう一度行います。

今度は左側の「1」の並びが2個に、右側の「1」は消えてしまいました。2回この操作を行って1が消えたのは、連続する「1」は2個だったからです。残りの「1」も、この操作をあと2回行えば消えます。

つまり、「ビットシフト＋論理積」を繰り返し、完全に「1」が消えるまでの演算回数をカウントすることで連続する「1」の最大値を得ることができます。正方形の最大サイズを得る方法も同様な操作を縦方向・横方向に行うことで実現できます。

この方法では、正方形の最大サイズがあまり大きくない場合はすぐに計算が終了するため、テストケースによっては非常に高速に動作します。

このアルゴリズムを用いて、高速かつ簡潔なコードを書いてくださった挑戦者のコードを紹介しておきます。まずはMuさんのRubyのコードから。

#! /usr/bin/ruby
# CodeIQ q1022 わんにゃんキャッスル
# 犬または猫の位置をビットベクトルの配列で表現し、
# ビット演算でixiの正方形の有無を求める（i=1,2,...）

MAP=$<.map(&:chomp)

# 1のビットの最大正方形サイズ取得
def maxsq( m)
  i=0
  while m
    m.pop while m[-1]==0
    m.shift while m[0]==0
    break if m.size == 0
    i+=1
    m = m.map{|l|l&=l>>1}
    m = m.each_cons(2).map{|i,j| i&j}
  end
  return i
end

puts 'W: %d' % maxsq(MAP.map{|l|l.tr('WN','10').to_i(2)})
puts 'N: %d' % maxsq(MAP.map{|l|l.tr('WN','01').to_i(2)})

単に短く書いているわけではないので、可読性も抜群です。本問のテストケースなら、mapサイズが1000×1000ではありますが、正方形のサイズが100程度にしかなっていないので、瞬時に解が得られます。

続いてangelさんによるPerlのコード。

#!/usr/bin/perl

use strict;
use warnings;

# nyan-wan symbol characters
my @sym = qw(W N);

# load the map data, and count cols ( only from the 1st line )
chomp(my $first=<>);
my $cols = 1 + length $first;
my $buf = join "\0", $first, map { chomp; $_ } <>;

# prepare a hash to store results
my %sqsize = ();
@sqsize{@sym} = (0)x@sym;

# map data reduction
for ( my @left = @sym; @left = grep { -1 != index $buf, $_ } @left; )
{
  $sqsize{$_}++ for @left;
  $buf &= substr $buf, $cols;
  $buf &= substr $buf, 1;
}

print "$_: $sqsize{$_}\n" for @sym;

こちらは2進化の処理を行わず、入力の文字列をそのまま利用しているので、Perlにもかかわらず瞬時に解が得られる爆速コードです。Perlの場合、文字列の論理積を取ると各文字のasciiコードの論理積を取ります。この仕様のおかげで、「W」と「N」のみで表される文字列の論理積は、「W」同士なら「W」のまま、「N」同士なら「N」のままで、互いに異なる文字の場合は

'W'     = 87(1010111)
'N'     = 78(1001110)
'W'&'N' = 70(1000110) = 'F'

で、別の文字に変換されます。この性質を利用し、「W」と「N」について同時に処理することが可能となり、非常に高速になっています。これは素晴らしいですね！

最後はantimon2さんによるJuliaの解答です。

# ===== DEFINITIONS =====

# 与えられた2次元配列（行列）data に含まれる値 c の正方形領域の最大サイズを検索する関数
function findblocksize(data::Array{Array{Char, 1}, 1}, c::Char)
    h, w = length(data), length(data[1])    # ※ Julia は 1-origin
    max_size = min(h, w)
    # bitpack は、数値配列（行列）を 1要素1ビットからなる配列 BitArray にパッキングする関数
    src = bitpack([data[j][i] == c for j=1:h, i=1:w])
    # typeof(src) => BitArray{2}  # src は h行w列の真偽値行列になる。
    for k = 0:max_size-2
        if !any(src)
            # 全て false になったら k を返して終了
            return k
        end
        # 左上・右上・左下・右下の (w-k-1)x(h-k-1) の矩形を & したものを新しい src として次へ
        # ※ 行列の element-wize な演算がかなり高速
        src = src[1:h-k-1, 1:w-k-1] & src[1:h-k-1, 2:w-k] & src[2:h-k, 1:w-k-1] & src[2:h-k, 2:w-k]
    end
    # 最後まで1つでも true が残っていれば max_size を返す
    any(src) ? max_size : max_size - 1
end

# ===== MAIN =====
# @time begin   # ←実行時間計測用

# データを標準入力から読込・整形
data = collect(Array{Char, 1}, map(line -> collect(chomp(line)), eachline(STDIN)))
# typeof(data) => Array{Array{Char, 1}, 1}

# 求解・結果表示
println("W: $(findblocksize(data, 'W'))")
println("N: $(findblocksize(data, 'N'))")

# end   # 上方の「@time begin」に対応する「end」。