AtCoder Grand Contest 031 感想
AtCoder Grand Contest 031 に参加しました。
2時間、一生懸命考えましたが解法のカの字も浮かびませんでした。したがって提出していません。
A - Colorful Subsequence
atcoder.jp
文字の出現回数+1 をかけ合わせるだけでいいみたいです。
仮に、a=1, b=1, c=1 としてみます。このとき、それぞれを取るか取らないかという考え方をして、答えは 2*2*2 で 8......ですが一つも取らないということはできないので 8-1=7通りとなります。
a=1, b=1, c=3 のとき。a,b については同様。c は、1番目を取るか、2番目を取るか、3番目を取るか、取らないかの 4 種類。したがって、2*2*4-1 で15通りとなります。
敗因
組み合わせ = 2^N だと思い込んでいた。先ほどの例だと、a=1, b=1, c=1 のときの求め方は 2^1 * 2^1 * 2^1 だと勝手に思い込んでいたということです。なぜかはわかりませんが僕の頭の中はこうなっていました。
そのため、2^3 とか、2^3 - (2^(k-1) - 1) とかわけのわからない数式を量産して混乱していました。よって、数学の「組み合わせ問題」に慣れていなかったせいである、と結論することができるでしょう。数学を勉強しましょうね。