SRM643D1Med TheKingsArmyDiv1
大昔に解いてたけど解き直した
問題概要(原文)
$2$ 行 $N(1 \leq N \leq 200)$ 列の文字列がある．文字列は 'S','H' の $2$ 種類の文字からなる．以下の操作を繰り返して，全ての文字が 'H' であるようにしたい．最小何回操作が必要か？不可能なら $-1$ を返せ．
- 隣り合う文字に文字をコピーする
- ある行のある連続した区間を選んでもう $1$ つの行にコピーする
- ある列を選んで隣接した列にコピーする
考察
自明な考察
- 全て 'S' なら答えは $-1$
- 全て 'H' なら答えは $0$
その他の考察
- 'H' が並んだ行は答えに関係ない．
- 'S' が並んだ行は列コピーが必要
- 隣り合った行の文字同士が同じなら縮約できる
以上のような考察をすると以下のケースだけ考えればよくなる．
HSHSHSHS...HSHS SHSHSHSH...SHSH少ない方を行コピーでブロック数回かける．のこりはまとめて $1$ 回でできる．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class TheKingsArmyDiv1
{
public int getNumber(string[] state)
{
if (state.SelectMany(x => x).All(x => x == 'S')) return -1;
if (state.SelectMany(x => x).All(x => x == 'H')) return 0;
var n = state[0].Length;
var c = 0; var h = 0;
var pre = -1;
for (int i = 0; i < n; i++)
{
var k = 0;
if (state[0][i] != 'S') k |= 1;
if (state[1][i] != 'S') k |= 2;
if (k == 0) { c++; continue; }
if (k == 3) continue;
if (pre == k) continue;
pre = k; h++;
}
if (h == 0) return c;
return c + h / 2 + 1;
}
}
コメント
考察をしてgreedyにやるだけの問題
