[yukicoder] No.73 helloworld
問題
問題文を見ても解説文を読んでも何のことかさっぱりでしたが、数式を見ているうちになんとか理解できました。
下のサイトが参考になりました。 mmxsrup.hatenablog.com
考え方
d e h l o r w以外の文字は無視していいことは何となく理解できたんですが、問題文の1と2の条件が何を指しているのかが分かりませんでした。
問題文を解釈すると、与えられたアルファベットを並び替えて、そこから条件を満たすhelloworldという文字が作れるかということです。
例えば、与えられたアルファベットを並び替えて、hellowworlxxxxxxxdとしたときの答えは1となります。
lとo以外を無視して考えると、条件を満たす文字列の並びは、
h h ... h h e e ... e e w w ... w w r r ... r r d d ... d d
と並べるのが条件を満たす最大の値となります。このときの選び方は、上記の文字の種類の個数を掛け合わせた値が最大となります。
次に、oについて考えます。
oは二回出現するので、oの個数を とすると、 通りの分け方が考えられます。
例えば、 のときの並び方の一つは、
h e l l o o o w o o o o l d
のようになります。
この考えの元にlについて考えると、lは前半に2個以上、後半に1個以上必要です。
前半のlの個数を とすると、選び方は、
となります。 個から2つ選ぶということです。
後半は残りの個数から選ぶので、hやeとかの選び方と同様に、残りの個数が選び方の数になります。
コード
import java.util.Scanner; public class Exec0073 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int[] C = new int[26]; for(int i = 0; i < 26; i++) { C[i] = scan.nextInt(); } scan.close(); // d e h l o r w // 3 4 7 11 14 17 22 long ans = (long)C[3] * C[4] * C[7] * C[17] * C[22]; long max1 = 0; for(int i = 2; i < C[11]; i++) { long t = (i * (i - 1))*(C[11] - i) / 2; max1 = Math.max(max1, t); } long max2 = 0; for(int i = 1; i < C[14]; i++) { long t = i * (C[14] - i); max2 = Math.max(max2, t); } ans = ans * max1 * max2; System.out.println(ans); } }
感想
解法のアルゴリズム自体は簡単なんですが、問題を理解するのに非常に苦労しました。コンテスト中でしたらパニックになっていたと思います。