Codingame『Genome Sequencing』クリア

DNA / MIKI Yoshihito (´･ω･)

　散り散りになったDNAの破片を回収して、長さを測るゲーム。
個人的には破片の結合よりも、どうやって組み合わせを作るのかの方が難しかった。

最短ばかり選ぶとハマる

　複数のシーケンスから2つを選択→マッチング→結合
複数できた結合シーケンスから最短のものを選んで、またマッチング～
とやっていくとハマる。ハマりまくった。

　最終的にできあがる結合シーケンスが最短のものを探さないといけないので、
出そろうまで保持しないといけなかった。

Source Code

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    static void Main(string[] args)
    {
        DNA d = new DNA();

        d.Main();

        // Write an action using Console.WriteLine()
        // To debug: Console.Error.WriteLine("Debug messages...");

        Console.WriteLine(d.Length);
    }

    /// <summary>
    /// シーケンス結合状態クラス
    /// </summary>
    public class CSP
    {
        //組み合わせ
        public bool[] C;
        //シーケンス
        public string Seq;

        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="n">シーケンス数</param>
        public CSP(int n)
        {
            this.C = new bool[n];
            this.Seq = "";
        }

        /// <summary>
        /// コンストラクタ2
        /// </summary>
        /// <param name="n">シーケンス数</param>
        /// <param name="p">ONにするシーケンス番号</param>
        /// <param name="s">シーケンス</param>
        public CSP(int n, int p, string s)
        {
            this.C = new bool[n];
            this.C[p] = true;
            this.Seq = s;
        }

        /// <summary>
        /// コンストラクタ3
        /// </summary>
        /// <param name="n">シーケンス数</param>
        /// <param name="p">ONにするシーケンス番号</param>
        /// <param name="s">シーケンス</param>
        /// <param name="c">シーケンス結合状態</param>
        public CSP(int n, int p, string s, bool[] c)
        {
            this.C = new bool[n];
            c.CopyTo(this.C, 0);
            this.C[p] = true;
            this.Seq = s;
        }
    }

    /// <summary>
    /// DNAクラス
    /// </summary>
    public class DNA
    {
        private int N;
        //観賞用シーケンス
        private string[] seq;
        //結合シーケンス
        private List<CSP> matchSeq;

        //DNAの全長
        public int Length { get { return _length; } }
        private int _length;

        /// <summary>
        /// コンストラクタ
        /// </summary>
        public DNA()
        {
            //シーケンス数を読み込む
            N = int.Parse(Console.ReadLine());

            seq = new string[N];
            matchSeq = new List<CSP>();

            for (int i = 0; i < N; i++)
            {
                seq[i] = Console.ReadLine();
                matchSeq.Add(new CSP(N,i,seq[i]));
            }
        }

        /// <summary>
        /// シーケンスが１つだけの場合
        /// </summary>
        /// <returns>true/false</returns>
        private bool IsOneSequence()
        {
            if (N == 1)
            {
                _length = seq[0].Length;
                return true;
            }
            return false;
        }

        /// <summary>
        /// 現在の結合状態を表示する(デバッグ用)
        /// </summary>
        /// <param name="n">結合回数</param>
        private void ShowAllCombineSequences(int n)
        {
            Console.Error.WriteLine("***"+n+ "Sequences***" + matchSeq.Count);
            foreach (CSP ms in matchSeq)
            {
                foreach (bool b in ms.C)
                {
                    if (b == true) Console.Error.Write("1");
                    else Console.Error.Write("0");
                }
                Console.Error.WriteLine(" " + ms.Seq);
            }
        }

        /// <summary>
        /// シーケンスの結合
        /// </summary>
        /// <param name="l">結合回数</param>
        private void CombiningSequences(int l)
        {
            //RemoveAtするので、結合シーケンスを最後から見ていく
            for (int i = matchSeq.Count - 1; i >= 0; i--)
            {
                //結合状態をスキャン
                for (int j = 0; j < N; j++)
                {
                    //結合してない被結合シーケンスがあれば
                    if (matchSeq[i].C[j] == false)
                    {
                        //マッチング処理
                        string str = Match(matchSeq[i].Seq, seq[j]);
                        //処理結果が文字無し(長さ0)でなければ
                        if (str.Length != 0)
                        {
                            //新しく追加
                            matchSeq.Add(new CSP(N, j, str, matchSeq[i].C));
                        }
                    }
                }
                //結合シーケンスが古くなったので消去
                matchSeq.RemoveAt(i);
            }
        }

        /// <summary>
        /// DNAの復元
        /// </summary>
        public void Main()
        {
            //シーケンスが一つだけの場合
            if (this.IsOneSequence() == true) return;

            this.ShowAllCombineSequences(0);

            //シーケンス数分まわして結合状態を全部埋める
            for (int l = 0; l < N - 1; l++)
            {
                //シーケンス結合処理
                this.CombiningSequences(l);
                this.ShowAllCombineSequences(l + 1);
            }

            //シーケンス長を昇順ソート
            matchSeq.Sort((f, n) => f.Seq.Length - n.Seq.Length);

            //最も長いシーケンスの、長さを得る
            _length = matchSeq[0].Seq.Length;
        }


        /// <summary>
        /// 結合処理
        /// </summary>
        /// <param name="s1">前側</param>
        /// <param name="s2">後側</param>
        /// <returns>最短結合シーケンス</returns>
        private string Match(string s1, string s2)
        {
            //普通に中にあれば長い方を返す
            if (s1.Contains(s2) == true) return s1;
            else if (s2.Contains(s1) == true) return s2;

            //順方向の結合結果
            string r1 = Search(s1, s2);
            //逆方向の結合結果
            string r2 = Search(s2, s1);

            //結合部分が無ければ
            if (r1 == "" & r2 == "") return string.Format("{0}{1}", s1, s2);

            //片方が文字無し(長さ0)ならば
            if (r1.Length == 0) return r2;
            else if (r2.Length == 0) return r1;

            //結合シーケンスの短い方を返す
            if (r1.Length > r2.Length) return r2;
            else return r1;
        }

        /// <summary>
        /// マッチング～結合操作
        /// </summary>
        /// <param name="s1">前側</param>
        /// <param name="s2">後側</param>
        /// <returns>結合結果</returns>
        private string Search(string s1, string s2)
        {
            //文字列長の短い方を検索終了に設定
            int endLimit = s1.Length < s2.Length ? s1.Length : s2.Length;
            //結果の保存
            string result = "";

            for (int i = 0; i < endLimit; i++)
            {
                //s1の先頭とs2の末尾が等しければ
                if (s1[0] == s2[s2.Length - 1 - i])
                {
                    //重なってる部分を切り出し
                    string ss1 = s1.Substring(0, i + 1);
                    string ss2 = s2.Substring(s2.Length - 1 - i, i + 1);
                    //切り出し部分が等しければ
                    if (ss1 == ss2)
                    {
                        //結合処理
                        ss1 = s1.Substring(i + 1, s1.Length - 1 - i);
                        string tmp = string.Format("{0}{1}", s2, ss1);
                        // 候補から短い方を選択する
                        if (result.Length == 0)
                        {
                            result = tmp;
                        }
                        if (result.Length > tmp.Length)
                        {
                            result = tmp;
                        }
                    }
                }
            }

            //短い奴を返す
            return result;
        }

    }
}