競技プログラミング用 知識集積所
ABC414B - String Too Long
最終更新：
Bot(ページ名リンク)
-
view
問題
必要知識
A問題レベルのものは省略
考え方
ランレングス圧縮（未作成）を戻すのは、まず空文字列を作って、「cをl文字追加」をループすればよい。
問題は、Too Longの判定方法。
実際に作ってから判定する方法は、lの値に10^18を投げ込まれたときに追加処理に10^10秒（300年）かかるためTLEする。
そこで、作る前に「いまから作ったら100文字超えますか？」を確認してからやるようにする必要がある。
実際に作ってから判定する方法は、lの値に10^18を投げ込まれたときに追加処理に10^10秒（300年）かかるためTLEする。
そこで、作る前に「いまから作ったら100文字超えますか？」を確認してからやるようにする必要がある。
解答例
注意点
Too Long判定は毎回やる
「最初に合計文字数が100を超えるか判定すればいいんじゃん？」というのは、発想としては正しい。
しかし、最大で10^18になるデータを最大100個足すと、なんと[[long long型（未作成）]ですらオーバーフローする。
10^20まで扱える型を頑張って用意するのは手間すぎるので、1つ足すたびに判定する形で回避したい。
しかし、最大で10^18になるデータを最大100個足すと、なんと[[long long型（未作成）]ですらオーバーフローする。
10^20まで扱える型を頑張って用意するのは手間すぎるので、1つ足すたびに判定する形で回避したい。
