重複組み合わせ問題と勘違いして死んだ件（ABC 089: C – March）

今日の反省。

最近、問題の意味を勘違いして時間溶かすパターンが多い気がする。 表題に上げたこの問題（ABC 089: C – March）がその最たる例である。

この問題文を読んで、いろはすはこう考えた。 まず、重要なのは'M','A','R','C','H'それぞれの文字を頭文字とする文字列がいくつずつあるかである。 これらを数えて配列に格納したら、あとはその中から３つの文字列を選び取る場合の数を数えればいい。

これは蟻本で見た気がするなあ・・・・・・そうだ、あれだ、重複組み合わせ問題だ。 そう思って、蟻本に載ってる漸化式を使ってDPを書いた。

サンプルの入力で試してみると、何故か一つだけ出力が合わない。 どこが間違っているかとソースコードを見直したり、ログを仕込んでみたりしたが一向に間違いは見つからず、そのまま１時間近く経過してしまった。

実は、この問題は重複組み合わせ問題ではなかったのである。 気づいたきっかけは、ログに吐き出された中に明らかにおかしい値が混じっていたことだった。 そもそもサンプルもそうだったが、手計算してもおかしいと分かる。 しかしDPの漸化式は何度見直しても蟻本のそれと同じだったし、その式は自分で確かめたことがある式だから、誤植ということもありえない。

そこで初めて、「あれ、これって本当に重複組み合わせ問題か・・・・・・？」という疑念が湧いた。 そしてよくよく今回の問題と、蟻本の例題を見比べてみて、疑念は確信に変わったのだった。

いろはすは、重複組み合わせ問題の意味を勘違いしていたのである。 今解くべき問題は、

n種類のボールが、それぞれa_1,...,a_n個ずつある。このn種類の中からm種類を選んで、その各種類から一個ずつボールを取り出すときの取り出し方はいくつか。

であるのに対して、重複組み合わせ問題とは、

n種類のボールが、それぞれa_1,...,a_n個ずつある。同じ種類のボールを区別しないとき、これらの中からm個のボールを取り出す取り出し方はいくつか。

という問題である。こうしてきちんとステートメントを書き下してみると、両者は全く違う問題であることがわかる。

というわけで、今回の教訓は

問題設定を正しく理解せよ。アルゴリズムを使うときも、その背景となる設定が本当に今の状況に適用できる設定なのか確かめよ

である。

〜おまけ〜

あと、配列の要素の型をint型にしていたらWAになってしまった。 確かに要素の大きさとしては10⁵なのでintで十分なのだが、後にこの要素を３つ掛け算するところがあり、そのときにキャストをしていなかったせいでオーバーフローが起きたものと思われる。 [式の代入先の変数がlong long型だったので、勝手にキャストしてくれるから大丈夫だと思っていたのだが、そうでもなかったようである。式の途中でオーバーフローしてたら駄目ということだろうか。] 最終的に、配列の要素の型もlong long型にしたら通った。

Submission #4187839 - AtCoder Beginner Contest 089

こういう気づきにくいミスにも気をつけなければと思った。