結果
問題 | No.150 "良問"(良問とは言っていない |
ユーザー |
![]() |
提出日時 | 2024-10-10 22:57:09 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 65 ms / 5,000 ms |
コード長 | 4,857 bytes |
コンパイル時間 | 1,160 ms |
コンパイル使用メモリ | 108,032 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-10-10 22:57:12 |
合計ジャッジ時間 | 2,917 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;class Program{static string InputPattern = "InputX";static List<string> GetInputList(){var WillReturn = new List<string>();if (InputPattern == "Input1") {WillReturn.Add("3");WillReturn.Add("veryverygoodproblem");WillReturn.Add("goodexcellentproblems");WillReturn.Add("problemgood");//0//0//10//この入力例において//S1 = "veryverygoodproblem"//S2 = "goodexcellentproblems"//S3 = "problemgood"//である。このとき、//S1は最初から良問//S2も最初から良問//S3は3文字目('o')以外の文字を修正して、S3="goodproblem"とすれば良問//になる。したがって、K1 = 0、K2 = 0、K3 = 10となる。}else if (InputPattern == "Input2") {WillReturn.Add("2");WillReturn.Add("goodproblem");WillReturn.Add("agdddekproblemsdl");//0//2//操作回数が最小となる最終的な文字列(良問)には、以下のようなものがある。//S1 = "goodproblem"//S2 = "agoodekproblemsdl//ただし、同じ操作回数でできる最終的な文字列(良問)は、複数存在することがあるので注意。}else if (InputPattern == "Input3") {WillReturn.Add("9");WillReturn.Add("geodaaaproblem");WillReturn.Add("goodproblen");WillReturn.Add("badendlessprobrem");WillReturn.Add("podpdpprrobleem");WillReturn.Add("problemgoodprobremgood");WillReturn.Add("smallproblem");WillReturn.Add("proproprefurohobbyhobby");WillReturn.Add("gooeproblemd");WillReturn.Add("itisproblemcoolgoodproblem");//1//1//4//5//1//4//8//1//0}else if (InputPattern == "Input4") {WillReturn.Add("5");WillReturn.Add("problemgoodproblem");WillReturn.Add("problemproblem");WillReturn.Add("goodgoodgood");WillReturn.Add("xxxxxxxxxxxxx");WillReturn.Add("badendlessproblemactivetogood");//0//3//6//11//3}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}static void Main(){List<string> InputList = GetInputList();string[] SArr = InputList.Skip(1).ToArray();Array.ForEach(SArr, X => DeriveCost(X));}//GoodProblemに変換する際の最小コストを求めるstatic void DeriveCost(string pBeforeStr){//Goodに変換するコストの配列int[] CostGoodArr = DeriveNeedCostArr(pBeforeStr, "good");//Problemに変換するコストの配列int[] CostProblemArr = DeriveNeedCostArr(pBeforeStr, "problem");//Console.WriteLine("{0}のGoodへのコスト", pBeforeStr);//Array.ForEach(CostGoodArr, X => Console.Write(X));//Console.WriteLine();//Console.WriteLine("{0}のProblemへのコスト", pBeforeStr);//Array.ForEach(CostProblemArr, X => Console.Write(X));//Console.WriteLine();//最小のコスト合計を求めるint Answer = int.MaxValue;for (int I = 0; I <= CostGoodArr.GetUpperBound(0); I++) {//下限値枝切りif (Answer < CostGoodArr[I]) continue;int StaInd = I + "good".Length;for (int J = StaInd; J <= CostProblemArr.GetUpperBound(0); J++) {int CostSum = CostGoodArr[I] + CostProblemArr[J];if (Answer > CostSum) {Answer = CostSum;}}}Console.WriteLine(Answer);}//指定文字列の各Indから指定文字列に変換する際のコストの配列を返すstatic int[] DeriveNeedCostArr(string pBeforeStr, string pNeedStr){var WillReturnList = new List<int>();for (int I = 0; I <= pBeforeStr.Length - 1; I++) {if (I + pNeedStr.Length > pBeforeStr.Length)break;int Cnt = 0;for (int J = 0; J <= pNeedStr.Length - 1; J++) {if (pNeedStr[J] != pBeforeStr[I + J])Cnt++;}WillReturnList.Add(Cnt);}return WillReturnList.ToArray();}}