「凸頂点の数」の実装例と、若干の解説解題

問題 http://nabetani.sakura.ne.jp/hena/orde03nofconv/
実装リンク集 http://qiita.com/Nabetani/items/b8bf742d278c6cf501aa
です。

解題

今回は珍しく、問題を考える前に図を書いた。
図を眺めながらどんな問題にしようか考えて、この問題に至った。
要するに、行き当たりばったりである。

マス目を歩くのはやったし、辺の数を数える問題も出した。
頂点の数は辺の数と同じだし、どうしよう。

そうだ。凸頂点にしよう。という具合。

行き当たりばったりである。

実装１

私が普通だと思っていた実装は

def neibour?(a,b)
  a,b=[a,b].sort
  dy = (b[1]-a[1])%20
  return [1,19].include? dy if a[0]==b[0]
  return [0,19].include? dy if a[0]+1==b[0]
  return false
end

def solve_impl( points )
  e = points.size*6
  points.combination(2) do |a,b|
    e -=4 if neibour?(a,b)
  end
  points.combination(3) do |a,b,c|
    e+=3 if [a,b,c].combination(2).all?{ |x,y| neibour?(x,y) }
  end
  e
end

def solve( src )
  cells=src.chars.each_slice(2).map{ |r,t| [r.to_i, t.ord] }
  center = [0, ?0.ord]
  if cells.include?( center )
    solve_impl( cells - [center] + (?a..?t).map{ |x| [0, x.ord] } ) - 20
  else
    solve_impl( cells )
  end.to_s
end

if $0==__FILE__
  $stdout.sync=true
  DATA.map{ |line|
    num, src, e0 = line.split(/\s+/)
    expected = e0.split(",").sort_by(&:to_i).join(",")
    actual = solve(src)
    ok=actual==expected
    if ok
      puts( "ok %s : %s" % [ num, actual ] )
    else
      puts("**NG** %s : %s / %s" % [ num, expected, actual ] )
    end
    ok
  }.all?(&:itself).tap{ |x| puts( x ? "Everything is okay!" : "something wrong..." ) }
end

__END__
0 1a2t3s2s  11  リンク
1 1a1c1d00  22  リンク
40  3m4d4e1i3t4f1f3n2p2g1q4g2c2m1s2r2i3f3o1h3g2e1o3a4r3h3r4o  75  リンク

こういうやつ。

• 領域の個数の6倍が、凸頂点の数だよね。
• でも、隣接しているペアがひと組あると、凸頂点が4つ減る
• それでもあわなくて、三つ巴がひと組あると、凸頂点を3つ減らしすぎていたので戻す
• まんなかの「00」があるときは、0a〜0t があるものとして計算してから 20 減らす。

という方針。計算量が $O(n^3)$ なので、遅いけど、今回の問題の範囲なら何も問題はない。

しかし。
当日これを書いてくるひとはひとりもいなかったのであった。

実装２

もう一つの方針は、頂点をひとつずつチェックする感じのやつ。

実装は C++ だとこんな感じ。

c++11

#include <vector>
#include <set>
#include <map>
#include <string>
#include <iostream>

using namespace std;

struct point
{
  int r, t;
};

bool operator==( point const & a, point const & b )
{
  return a.r==b.r && a.t==b.t;
}
bool operator<( point const & a, point const & b )
{
  return make_pair( a.r, a.t ) < make_pair( b.r, b.t );
}
bool operator!=( point const & a, point const & b )
{
  return !(a==b);
}

set<point>
parse( char const * src )
{
  set<point> points;
  for( char const * p = src ; *p ; p+=2 )
  {
    point pt = { p[0]-'0', p[1]%20 };
    points.insert( pt );
  }
  return points;
}

point center = { 0, '0'%20 };

vector<point>
neibours( point const & pt )
{
  vector<point> r;
  vector<point> cand{
    {pt.r-1,pt.t+1 },{pt.r-1,pt.t },{pt.r,pt.t-1 },
    {pt.r+1,pt.t-1 },{pt.r+1,pt.t },{pt.r,pt.t+1 }
  };
  for( point p : cand ){
    if ( p.r==0 ){
      r.push_back( center );
    } else {
      r.push_back( { p.r, (p.t+20) % 20 } );
    }
  }
  return r;
}

string solve_impl( set<point> const & src )
{
  int r=0;
  for( point const & pt : src ){
    if ( pt==center ){
      for( int i=0 ; i<20 ; ++i ){
        if ( src.find( { 1, i } )==src.end() && src.find( {1, (i+1)%20} )==src.end() ){
          ++r;
        }
      }
    } else {
      vector<point> neis = neibours( pt );
      for( int i=0 ; i<6 ; ++i ){
        if ( src.find( neis.at( i%6 ) )==src.end()
          && src.find( neis.at( (i+1)%6 ) )==src.end() ){
          ++r;
        }
      }
    }
  }
  return std::to_string(r);
}

void test( char const * src, char const * expected )
{
  set<point> points = parse( src );
  string actual = solve_impl( points );
  bool okay = ( actual == string( expected ) );
  cout << (okay ? "ok " : "***NG*** " ) << src << " " << actual << " " << expected << endl;
}

int main(){
/*0*/ test( "1a2t3s2s", "11" );
/*1*/ test( "1a1c1d00", "22" );
/*40*/ test( "3m4d4e1i3t4f1f3n2p2g1q4g2c2m1s2r2i3f3o1h3g2e1o3a4r3h3r4o", "75" );
}

• ある頂点を含む6角形がひとつだけなら、それは凸頂点。
• 「00」の凸頂点は、別に数える

という方針。
今回 C++ で書いたおかげで、「std::to_string()」という関数の存在を知ることが出きた。収穫。

もともとあった ruby はこんな具合

CENTER = [0, ?0.ord % 20]

def neibours(c)
  r,t=c
  [
    [r-1,t+1],[r-1,t],[r,t-1],[r+1,t-1],[r+1,t],[r,t+1]
  ].map{ |x|
    x[0]==0 ? CENTER : [x[0],x[1]%20]
  }
end

def solve_impl( cells )
  cells.inject(0) do |acc,cell|
    acc+if cell==CENTER
      20.times.count{ |x| [x,x+1].none?{ |xx| cells.include?([1,xx%20]) } }
    else
      r=neibours(cell)
      6.times.count do |ix|
        [ix,ix+1].none?{ |x| cells.include?(r[x%6])}
      end
    end
  end
end

def solve( src )
  cells=src.chars.each_slice(2).map{ |r,t| [r.to_i, t.ord%20] }
  r=solve_impl(cells)
  r.to_s
end

走らせる部分は省略。
これを C++ に移植すると先に挙げたソースになる。