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)$ となる．

cLay（version 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: 2024年04月26日09時14分57秒
Last modified: 2017年04月30日01時33分40秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：