2018-08-30から1日間の記事一覧

SRM510 Div1 Easy - TheAlmostLuckyNumbersDivOne

問題 からまでの整数の中で4と7以外の数字を多くとも1つしか使わない数字はいくつあるか求めよ。 解法 桁DPのメモ化が無いようなもの。状態として、 上から何桁目を見ているか 4と7以外の数字が何回出てきたか 今まで見てきた要素でより大きいことが保証され…

SRM509 Div1 Easy - LuckyRemainder

問題 整数から数字を1つ以上取り除き残った数字を順番はそのままに右へ詰めてできる整数らの和を9で割った余りを求めよ。 解法 上の桁から順番に9で割った余りがそれぞれ何回出てくるかを記録していく。これをとする()。桁目の数字がだったとき、これを使う…

AtCoder Regular Contest 023 C - タコヤ木

問題 広義単調増加列のうち一部分が不明となっている列が与えられる。あり得る組み合わせの数を求めよ。 解法 不明な部分が連続している一つの塊に注目する。たとえば定数についてという部分列を考えるとすると、からに至るまでの4回の遷移の総和がとなって…