ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです!

【プログラミングコンテスト】早稲田大学プログラミングコンテスト2019②

明日は福岡から実家の滋賀に帰省することにしたのでキャリーバッグに物を詰める作業をこれからします、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/wupc2019/tasks/wupc2019_b)にて開催されました、早稲田大学プログラミングコンテスト2019の第2回目です。

今回は、B問題「B - 10 puzzle」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語C#を使用しています。

1.問題文

高さ H 、幅 W のマス目がある。はじめ、 i 行 j 列のマスには 0 以上 9 以下の数 A i , j が書かれている。マス目中のマスは辺を共有するマスに隣接している。ここで、あるマスの部分集合が「連結」であるとは、集合中の全てのマスのペアについて、集合中の隣接するマスに移動することを繰り返して行き来できることを指す。

カトーくんは以下の操作を 0 回以上行うことができる。

  • ある「連結」なマスの部分集合を選び、集合中のマスに書かれている数の最大値を M とした時、その集合の全てのマスに書かれている数を 2 × M を 10 で割ったあまりに書き換える。

カトーくんはマス目の全てのマスに書かれた数を 0 にすることができるか判定せよ。 また、 0 にすることができる場合、これを達成するために必要な最小の操作回数を求めよ。

2.入力例

  • 入力
5 3
6 6 6
6 5 5
6 6 6
6 5 6
6 6 6
  • 出力
Yes 2

例えば、はじめに 6 が書かれている全てのマスを集合として選び(これは「連結」です)これに対して操作を行った後、全てのマスを集合として選び操作を行うと 2 回の操作で目的を達成できます。

3.初見の感想

  • 二次元配列保存
  • 連結を判定して再帰的に関数を回すのがよさそう
  • 5と書かれたマスは残す方が良い
  • 連結部分では最大値しか意味がない

(最大値*2%10ですべてのマスが書き換えられるため)

4.学びポイント

  • 本当に連結判定する必要があるのか?

→2行2列以上なら少なくとも5と書かれたマスを一つ残した状態で残りのマス全てを連結で選択できる

  • 1行もしくは1列の場合

→5と書かれたマスを一つ選び、その両側で別々に連結部分を作成する

5.コードの簡単な解説

  • まず、入力の値のパースを行う
        string[] temp = Console.ReadLine().Split(' ');
        int N = int.Parse(temp[0]);
        int M = int.Parse(temp[1]);
        int[,] A = new int[N, M];
        int[] C = new int[10];
        for (var i = 0; i < N; i++)
        {
            string[] str2 = Console.ReadLine().Split();
            for (var j = 0; j < M; j++)
            {
                A[i, j] = int.Parse(str2[j]);
                C[A[i, j]]++;
            }
        }
  • 解けないパターン(5がない・全て0)を事前にはじいておく
        if (C[1] == 0 && C[2] == 0 && C[3] == 0 && C[4] == 0 && C[5] == 0 && C[6] == 0 && C[7] == 0 && C[8] == 0 && C[9] == 0)
        {
            ans = 0;
        }
        else if (C[5] == 0)
        {
            ans = -1;
        }
  • 2行2列以上の場合はマスの数値の最大値を探して回数計算
        else
        {
            if (C[9] > 0)
            {
                ans = 4;
            }
            else if (C[8] > 0)
            {
                ans = 3;
            }
            else if (C[7] > 0 || C[6] > 0)
            {
                ans = 2;
            }
            else
            {
                ans = 1;
            }
  • 一行や一列しかない場合、5のマスの両側で連結成分を作成する
            if (N == 1 && M >= 2)
            {
                ans = int.MaxValue;
                for (var i = 0; i < M; i++)
                {
                    if (A[0, i] == 5)
                    {
                        int m1 = 0;
                        for (var j = 0; j < i; j++)
                        {
                            if (A[0, j] >= 9)
                            {
                                m1 = Math.Max(m1, 3);
                            }
                            else if (A[0, j] >= 8)
                            {
                                m1 = Math.Max(m1, 2);
                            }
                            else if (A[0, j] >= 6)
                            {
                                m1 = Math.Max(m1, 1);
                            }
                        }
                        int m2 = 0;
                        for (var j = i + 1; j < M; j++)
                        {
                            if (A[0, j] >= 9)
                            {
                                m2 = Math.Max(m2, 3);
                            }
                            else if (A[0, j] >= 8)
                            {
                                m2 = Math.Max(m2, 2);
                            }
                            else if (A[0, j] >= 6)
                            {
                                m2 = Math.Max(m2, 1);
                            }
                        }
                        ans = Math.Min(ans, m1 + m2 + 1);
                    }
                }
            }
            if (M == 1 && N >= 2)
            {
                ans = int.MaxValue;
                for (var i = 0; i < N; i++)
                {
                    if (A[i, 0] == 5)
                    {
                        int m1 = 0;
                        for (var j = 0; j < i; j++)
                        {
                            if (A[j, 0] >= 9)
                            {
                                m1 = Math.Max(m1, 3);
                            }
                            else if (A[j, 0] >= 8)
                            {
                                m1 = Math.Max(m1, 2);
                            }
                            else if (A[j, 0] >= 6)
                            {
                                m1 = Math.Max(m1, 1);
                            }
                        }
                        int m2 = 0;
                        for (var j = i + 1; j < N; j++)
                        {
                            if (A[j, 0] >= 9)
                            {
                                m2 = Math.Max(m2, 3);
                            }
                            else if (A[j, 0] >= 8)
                            {
                                m2 = Math.Max(m2, 2);
                            }
                            else if (A[j, 0] >= 6)
                            {
                                m2 = Math.Max(m2, 1);
                            }
                        }
                        ans = Math.Min(ans, m1 + m2 + 1);
                    }
                }
            }
        }
  • 表示処理
        if (ans == -1)
        {
            Console.Write("No");
        }
        else
        {
            Console.Write("Yes " + ans);
        }
    }
}

6.全コード

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

class Program
{
    static void Main(string[] args)
    {
        string[] temp = Console.ReadLine().Split(' ');
        int N = int.Parse(temp[0]);
        int M = int.Parse(temp[1]);
        int[,] A = new int[N, M];
        int[] C = new int[10];
        for (var i = 0; i < N; i++)
        {
            string[] str2 = Console.ReadLine().Split();
            for (var j = 0; j < M; j++)
            {
                A[i, j] = int.Parse(str2[j]);
                C[A[i, j]]++;
            }
        }
        int ans = 0;
        if (C[1] == 0 && C[2] == 0 && C[3] == 0 && C[4] == 0 && C[5] == 0 && C[6] == 0 && C[7] == 0 && C[8] == 0 && C[9] == 0)
        {
            ans = 0;
        }
        else if (C[5] == 0)
        {
            ans = -1;
        }
        else
        {
            if (C[9] > 0)
            {
                ans = 4;
            }
            else if (C[8] > 0)
            {
                ans = 3;
            }
            else if (C[7] > 0 || C[6] > 0)
            {
                ans = 2;
            }
            else
            {
                ans = 1;
            }
            if (N == 1 && M >= 2)
            {
                ans = int.MaxValue;
                for (var i = 0; i < M; i++)
                {
                    if (A[0, i] == 5)
                    {
                        int m1 = 0;
                        for (var j = 0; j < i; j++)
                        {
                            if (A[0, j] >= 9)
                            {
                                m1 = Math.Max(m1, 3);
                            }
                            else if (A[0, j] >= 8)
                            {
                                m1 = Math.Max(m1, 2);
                            }
                            else if (A[0, j] >= 6)
                            {
                                m1 = Math.Max(m1, 1);
                            }
                        }
                        int m2 = 0;
                        for (var j = i + 1; j < M; j++)
                        {
                            if (A[0, j] >= 9)
                            {
                                m2 = Math.Max(m2, 3);
                            }
                            else if (A[0, j] >= 8)
                            {
                                m2 = Math.Max(m2, 2);
                            }
                            else if (A[0, j] >= 6)
                            {
                                m2 = Math.Max(m2, 1);
                            }
                        }
                        ans = Math.Min(ans, m1 + m2 + 1);
                    }
                }
            }
            if (M == 1 && N >= 2)
            {
                ans = int.MaxValue;
                for (var i = 0; i < N; i++)
                {
                    if (A[i, 0] == 5)
                    {
                        int m1 = 0;
                        for (var j = 0; j < i; j++)
                        {
                            if (A[j, 0] >= 9)
                            {
                                m1 = Math.Max(m1, 3);
                            }
                            else if (A[j, 0] >= 8)
                            {
                                m1 = Math.Max(m1, 2);
                            }
                            else if (A[j, 0] >= 6)
                            {
                                m1 = Math.Max(m1, 1);
                            }
                        }
                        int m2 = 0;
                        for (var j = i + 1; j < N; j++)
                        {
                            if (A[j, 0] >= 9)
                            {
                                m2 = Math.Max(m2, 3);
                            }
                            else if (A[j, 0] >= 8)
                            {
                                m2 = Math.Max(m2, 2);
                            }
                            else if (A[j, 0] >= 6)
                            {
                                m2 = Math.Max(m2, 1);
                            }
                        }
                        ans = Math.Min(ans, m1 + m2 + 1);
                    }
                }
            }
        }
        if (ans == -1)
        {
            Console.Write("No");
        }
        else
        {
            Console.Write("Yes " + ans);
        }
    }
}

7.最後に

これは昨日と同じ100点問題なのですが、難易度に差がある気がしますね(^-^;