外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

J - Another 7-5-3 Festival

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、tau0529、trueryob

配点 375 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

数列が00を含まないとき、NN以下の数値の長さは⌈log⁡10N⌉\lceil \log_{10} N \rceil以下であるため、その長さの部分文字列を全探索すれば良いです。

leading 00を含む場合、その限りではありません。そのために、数える手間を、個数の計上に転嫁します。

各00の連結成分の大きさは、Union Findなどを活用することで、簡単に数えられます。

最後に、leading 00の部分文字列を重複して数えるのを防ぐために、一工夫をしましょう。

ユーザー解説

ユーザー解説を書く