読者です 読者をやめる 読者になる 読者になる

AOJ 2717 Where is the Boundary

問題

Where is the Boundary | Aizu Online Judge

直線状にn個の県が並んだ国がある。
m種類の分類法があり、これによって各県は、'E'または'W'に分類することができる。
今、この国を'E'と'W'に分ける境界を決める。
m種類の分類法に対する誤差が最小になるような境界位置を求めよ。

解法

全探索する。
境界線を決めたとき、境界の左側にあるEの数と、境界の右側にあるWの数の和を求める。
この和が最小になる境界線が答えとなる。

ソースコード(C#)

using System;
using System.Collections.Generic;
using System.Linq;

namespace _2717
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] nm = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int n = nm[0];
            int m = nm[1];
            string[] d = new string[m];
            for (int i = 0; i < m; i++)
            {
                d[i] = Console.ReadLine();
            }

            int[,] e = new int[m, n + 1];
            int[,] w = new int[m, n + 1];
            for (int y = 0; y < m; y++)
            {
                for (int x = 0; x < n; x++)
                {
                    e[y, x + 1] = e[y, x];
                    if (d[y][x] == 'E') e[y, x + 1]++;
                }
            }
            for (int y = 0; y < m; y++)
            {
                for (int x = n - 1; x >= 0; x--)
                {
                    w[y, x] = w[y, x + 1];
                    if (d[y][x] == 'W') w[y, x]++;
                }
            }
            int ans = int.MaxValue;
            int bound = 0;

            for (int x = 0; x < n + 1; x++)
            {
                int tmp = 0;
                for (int y = 0; y < m; y++)
                {
                    tmp += e[y, x] + w[y, x];
                }
                if (tmp < ans)
                {
                    ans = tmp;
                    bound = x;
                }
            }

            Console.WriteLine("{0} {1}", bound, bound + 1);
        }
    }
}