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); } } }