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

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

【プログラミングコンテスト】全国統一プログラミング王決定戦予選②

完膚なきまでに期末試験を撃破してきました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/nikkei2019-qual)にて開催されました、全国統一プログラミング王決定戦予選の第二回目です。

今回は、第二問「B - Touitsu」の問題と僕との戦闘記です。

0.はじめに

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

1.問題文

三つの文字列 A , B , C が与えられます。これらはそれぞれ、英小文字からなる長さ N の文字列です。

私たちの目標は、これら三つの文字列をすべて等しくすることです。そのために、あなたは次の操作を繰り返し行うことができます。

操作: 文字列 A , B , C のうち一つを選び、さらに 1 以上 N 以下の整数 i を指定する。そして、選んだ文字列の先頭から i 文字目を別の何らかの英小文字に変更する。 目標を達成するためには最小で何回の操作が必要でしょうか?

2.入力例

入力

入力は以下の形式で標準入力から与えられる。

N
A
B
C

出力

必要な最小の操作回数を出力せよ。

入力例 1

4
west
east
wait

出力例 1

3

入力例 2

9
different
different
different

出力例 2

0

入力例 3

7
zenkoku
touitsu
program

出力例 3

13

3.初見の感想

  • 入力の分割とパースが必要
  • 2つの文字列では1文字ずつ比較を行い、異なる回数を調べる必要がある(ハミング距離)
  • 3つの文字列のうち2つ選ぶ必要がある…
  • 全ての組み合わせでハミング距離を計算し、少ない2パターンの和を取る

4.実際解いた時の感想

特に問題なく20分ぐらいで解けました!

5.コード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

    class Program
    {
        static void Main(string[] args)
        {
        int N_length=int.Parse(System.Console.ReadLine());
        string A = (System.Console.ReadLine());
        string B = (System.Console.ReadLine());
        string C = (System.Console.ReadLine());
        int difference = 0;
        for(int i = 0; i < N_length; i++)
        {
            if (A[i].Equals(B[i])&& A[i].Equals(C[i])) { }
            else if(A[i].Equals(B[i])|| A[i].Equals(C[i])|| C[i].Equals(B[i])) { difference++; }
            else { difference += 2; }
        }
        System.Console.WriteLine(difference);
    }
    }