yukicoder No.509 - 塗りつぶしツール

Source

ニコニコミュニティ
問題文

問題概要

白地の背景に黒字で整数 $N$ が書かれている.
ペイントの塗りつぶしツールのみを用いて,黒字の背景に白地で整数 $N$ が書かれている状態にしたい.
何回塗りつぶせばよいか,最小値を求める問題.
ただし,用いることができる色は白・黒・青の $3$ 色のみであるとする.
フォントは問題原文に書かれているフォントであり,数字の4は真ん中に囲まれた空間がある.
また,連続する2文字はどんな状況でもくっつかないとする.

解法

$x$ を文字の数,$y$ を最初の白の連結成分の数とする.
つまり,穴の数を,数字 0, 4, 6, 9 に関しては1個,数字 8 に関しては2個としたら,穴の数の合計 + 1 (背景)が $y$ である.
戦略は2通りあり,

  1. 全ての文字を青にし,白い部分を全て黒にし,文字を白にする
  2. 白い部分を全て青にし,文字を白にし,全ての青い部分を黒にする

なので,答えは $\min(2x+y, 2y+x) = x+y+\min(x,y)$ となる.

cLayversion 20170430-1)のコード

C++に変換後のコードはこちら

{
  int i, area = 1, len, res;
  int hole[10] = {1,0,0,0,1,0,1,0,2,1};
  char A[12];

  rd(A@len);
  A[0..len-1] -= '0';
  area += hole[A[0..len-1]];

  res = min(2*len + area, len + 2*area);
  wt(res);
}

Current time: 2017年11月18日04時29分07秒
Last modified: 2017年04月30日01時33分40秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: