【AtCoder】ABC058C

まだまだエラーはでますが、C#も少し慣れてきたので、C問題中心に戻します。

――――――――――――――――――――――――

問題文
すぬけ君は、文字列の書かれた紙から文字をいくつか切り抜いて、並び替えて別の文字列を作るのが好きです。
明日になると、すぬけ君は文字列 S1,...,Snのうちどれか 1つが書かれた紙がもらえます。 すぬけ君は文字列を作る事をとても楽しみにしているので、どんな文字列を作るか計画を立てることにしました。 ただし、すぬけ君はまだどの文字列が書かれた紙がもらえるかを知らないため、 どの文字列が書かれていた場合にも作れる文字列を考えることにしました。
S1,...,Snのどの文字列が書かれていても作れる文字列のうち、最長のものを求めてください。 最長のものが複数ある場合は、辞書順で最小のものを求めてください。
制約
• 1≤n≤50
• i=1,...,n に対して、 1≤|Si|≤50
• i=1,...,nに対して、 Si は小文字のアルファベット( a - z )からなる文字列

入力
入力は以下の形式で標準入力から与えられる。
n
S1
......
Sn
出力
条件を満たす最長の文字列のうち、辞書順で最小のものを出力せよ。 そのような文字列が空文字列である場合は、空行を出力せよ。

――――――――――――――――――――――――

要するにS1～Snに共通する文字を昇順で出力することを求められている。

考え方

共通の文字をどう探すかを考えた。

１．それぞれの文字列Sに各英小文字が何文字ずつ含まれているかを調べ、その結果を2次元配列(文字列数n × 英小文字26)に格納していく。

２．2次元配列から共通する英小文字を探す。各英小文字に対して、文字列ごとに含まれている数を比較し、一番少ないものが共通する英小文字の数になる。

３．aから順に、共通する英小文字をその数だけ出力する。

コード

using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

class Program{
 public static void Main(){

   int n = int.Parse(Console.ReadLine());
   
//英小文字の文字列を用意
   char[] alph = new char[26]{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//英小文字の数を格納する2次元配列   
   int[,] table = new int[n,26];
   
//2次元配列を埋めていく、文字列の各文字を英小文字の配列とひとつずつ比較する
//共通する文字が見つかったら、１カウント
   for(int i=0; i<n; i++){
     string st = Console.ReadLine();
     for(int j=0; j<st.Length; j++){
       for(int k=0; k<26; k++){
         if(st[j] == alph[k]){
           table[i,k]++;
           break;
         }
       }
     }
   }
   
//各英小文字で最小の数を取り出し、その数だけ英小文字を出力する
   for(int i=0; i<26; i++){
     int min = table[0,i];
     for(int j=0; j<n; j++){
       if(min > table[j,i]) min = table[j,i];
     }
     while(min>0){
       Console.Write(alph[i]);
       min--;
     }
   }
 }
}

ループ回しまくりの力業だったけど、とりあえずAC！なんかもっとスマートに解ける方法があるんだろうか…。今回nも|Si|も50以下だったからよかったけど、O(n|Si|*26)だから、nと|Si|が10^4くらいだと通らない。が、いったん力づくで解けたっということで今回は良しとしよう。

(最後の出力whileじゃなくて普通にminかければよかった)

C#でタグつけたいんだけど、タグの文字に#が使えないんだよなー。(小言)