【プログラミングコンテスト】全国統一プログラミング王決定戦予選②
完膚なきまでに期末試験を撃破してきました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/nikkei2019-qual)にて開催されました、全国統一プログラミング王決定戦予選の第二回目です。
今回は、第二問「B - Touitsu」の問題と僕との戦闘記です。
0.はじめに
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); } }