0

下記アットコーダーの問題がわかりません。
https://atcoder.jp/contests/agc031/tasks/agc031_a

解説やACの方のコードを見てみましたが26サイズのint配列にc[各文字 - 'a']++を
し、A.答え *= c[i]を繰り返すと求めるべき出力になるのか理解できませんでした。
噛み砕いて解説いただけると幸いです。

ーー
問題文
長さ Nの文字列 Sが与えられます。
Sの部分列であって、すべて異なる文字からなるものの数を 10^9+7で割った余りを答えてください。文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。

ただし、文字列の部分列とは、文字列から文字をいくつか 正の個数 取り出し、もとの文字列から順序を変えずにつなげたものを指します。

制約
1≤N≤100000
Sは英小文字からなる

入力
入力は以下の形式で標準入力から与えられる。

N

S

出力
異なる文字からなる部分列の個数を
10
9
+
7
で割った余りを出力せよ。

入力例 1
4
abcd
出力例 1

--
▼解説

同じ文字列でも、異なる位置から作られたものは区別するため、2N − 1 通りのすべての部分列が区別され ることになります。
条件より、同じ文字を 2 度使ってはいけないため、ある文字 c について colorful の条件を壊さないとり方 は (c の出現回数 + 1) となります (どれか 1 つを取るケース及び文字 c を一切取らないケース)
すべての文字 c についてのこのとり方の積を求め、空文字列の分の 1 を引いた数が答えとなります。

参照:AtCoder Grand Contest 031

2
  • 1
    問題にリンクしてくださっているなか申し訳ないのですが、リンク先がリンク切れになっても質問として成り立つように、問題の要約を上手く書いて頂けるとありがたいです。質問文下の「編集」からお願いいたします。
    – nekketsuuu
    Commented 2019年3月16日 21:07
  • @nekketsuuu すいません。ありがとうございます。
    – sample
    Commented 2019年3月17日 1:32

1 件の回答 1

2

正直、「解説」は一体何を言いたいのかよくわからないですね。内容が理解できるまでは一旦無視した方が良いでしょう。


まず、出題中の出力例1(全ての文字が異なる場合)では、2^N-1 (^はXORではなく、べき乗)で与えられることは理解できるでしょうか。

例の場合、N=4ですから、2^4-1=15 が答えとなります。

この考え方ですが、

この出題における「部分列」(通常のよく使われる意味の「部分列」とは異なります)は、

a,b,ab,c,ac,bc,abc,d,ad,bd,abd,cd,acd,bcd,abcd

の15通りがあるわけですが、この15通りを実際に作らなくても、考え方がわかれば数だけは出せるわけです。

a    (a使う  , b使わない, c使わない, d使わない)
 b   (a使わない, b使う  , c使わない, d使わない)
ab   (a使う  , b使う  , c使わない, d使わない)
  c  (a使わない, b使わない, c使う  , d使わない)
a c  (a使う  , b使わない, c使う  , d使わない)
 bc  (a使わない, b使う  , c使う  , d使わない)
abc  (a使う  , b使う  , c使う  , d使わない)
   d (a使わない, b使わない, c使わない, d使う  )
a  d (a使う  , b使わない, c使わない, d使う  )
 b d (a使わない, b使う  , c使わない, d使う  )
ab d (a使う  , b使う  , c使わない, d使う  )
  cd (a使わない, b使わない, c使う  , d使う  )
a cd (a使う  , b使わない, c使う  , d使う  )
 bcd (a使わない, b使う  , c使う  , d使う  )
abcd (a使う  , b使う  , c使う  , d使う  )
-------------------------------------------
     (a使わない, b使わない, c使わない, d使わない) この出題の「部分列」の定義に当てはまらない

a,b,c,d それぞれの文字について(使う, 使わない)の2通りの選択があって、それが4文字ですから、総数は、2×2×2×2=16通り。ただ、それだと全部「使わない」が含まれてしまっているので、1を引いて15通りとなるわけです。

こう考えれば、どのアルファベットを使っているかは関係なく、文字の種類が何種類あるかを表す N だけわかれば、総数は計算できるということはご理解いただけるでしょうか。


出題中の出力例2を見てみます。

入力文字列 baa に対しては、

b,a(1個目のa),a(2個目のa),ba(1個目のa),ba(2個目のa)

の5通りあるので、5 という答えが出せないといけません。

これを上と同じようにみて行くとこんな感じになります。

b   (b使う   , a使わない )
 a  (b使わない, a1個目使う)
  a (b使わない, a2個目使う)
ba  (b使う  , a1個目使う)
b a (b使う  , a2個目使う)
------------------------
    (b使わない,a使わない ) この出題の「部分列」の定義に当てはまらない

と見ることができます。1回しか現れない文字 b については、(使う, 使わない)の2通り、2個現れる a については、(1個目使う, 2個目使う, 使わない)の3通りで、総数は 2×3=6通り、両方「使わない」は上と同様に除かないといけないので、1を引いて 5 と計算できることになります。

同じように出題中の出力例3を考えると、文字列が abcab ですから、aが2個、bが2個、cが1個ですから、aについて(1個目使う, 2個目使う, 使わない)の3通り、bについても同じく3通り、cについては(使う, 使わない)の2通り、で総数の3×3×2=18から、全部「使わない」の1を引いて、17 が答えになります。

つまり、ある文字の出現回数がわかれば、その(出現回数+1)が、その文字に関する場合の数を表しているということになります。


全く現れない文字については、(使わない)の一択なので配列c[]の値を1にしておけば、×1は何もしないのと一緒なのでうまい具合に無視してくれるので、場合分けなどせずにc[]の全要素を掛け算すれば良いことになります。

あなたの見たコードのint配列c[]は、全要素の初期値が1にしてあるか、数え終わった後に全要素に1を足す、ということをしているのではないでしょうか。


ご理解いただけたでしょうか。わかりにくい部分があれば、どの部分がどうわからないかを具体的に知らせていただければ、もう少し詳しく書けるところがあるかもしれません。

1
  • 丁寧な解説ありがとうございます。 解説いただいた内容をもとにコードを追っていくと理解できました。 非常に助かりました。ありがとうございました。
    – sample
    Commented 2019年3月17日 7:06

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。