AtCoder Beginner Contest 104

けんちょん @drken1215

これ見ると、橙中位でも 800 点は 6 割で良さそうなのん！！ pic.twitter.com/r40DEwqyB6

拡大

hotpepsi @hotpepsi

@masashinakata togetter.com/li/1253847 そういえばAtCoderはじめました competitiveprogramming.info/atcoder/contes…

agw @masashinakata

@hotpepsi おー、おつです! なんか水色が緑になってるっぽい...? competitiveprogramming.info/atcoder/contes…

hotpepsi @hotpepsi

@masashinakata バグってました、さんきゅー

てんぷら @tempura_cpp

前々回のABCのDのやつ、DPで書くとこれだけなんか pic.twitter.com/TnecpqNP7z

拡大

てんぷら @tempura_cpp

それはこっちのほうがいいなぁ

ちゃっく @chakku_000

@tempura_pp これdpの状態になにもたせてるんです?

てんぷら @tempura_cpp

なんかN=10^5とかでも状態数が定数だとDPできるみたいなのいまいち思いつけないなぁ

てんぷら @tempura_cpp

@chakku_000 dp[i][j]で「j文字目まででi文字完成しているものの数」です iが1ならAまで完成してるものの個数、3ならABCまで完成してるものの個数です

ちゃっく @chakku_000

@tempura_pp なるほど...DP解わかっていなかったので参考にします...

てんぷら @tempura_cpp

@chakku_000 i+1文字目まででできるABの数は i+1文字目がBなら｢i文字目までのABの数+i文字目までのAの数｣ それ以外なら｢i文字目までのABの数｣ みたいなことをしています(ただし?の扱いは気をつけないといけない)