山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.73 helloworld

問題

No.73 helloworld - yukicoder

問題文を見ても解説文を読んでも何のことかさっぱりでしたが、数式を見ているうちになんとか理解できました。

下のサイトが参考になりました。 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の個数を a とすると、 a(a - 1) 通りの分け方が考えられます。

例えば、 a = 7 のときの並び方の一つは、

h e l l o o o w o o o o l d

のようになります。

この考えの元にlについて考えると、lは前半に2個以上、後半に1個以上必要です。

前半のlの個数を b とすると、選び方は、

 {}_b \mathrm{C}_2

となります。 b 個から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);
    }
}

感想

解法のアルゴリズム自体は簡単なんですが、問題を理解するのに非常に苦労しました。コンテスト中でしたらパニックになっていたと思います。