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にやるだけの問題