369.1

プラクティスを軽量化したらしいが...重たいことに変わりなかった。

250

AとBからなる文字列のうち、Aの文字数の上限と、Aが連続して良い回数の上限、Bの文字数の上限と、Bが連続して良い回数の上限が与えられるので、このときの最長の文字列の長さを答えよ、という問題。

どうやれば間違えずに解けるか考えよう、という問題。基本コーナーケースだらけ。本番ならまじめにやる...。

Aが連続するものがK回登場すると考えると、Bが連続するものはK-1回かK回かK+1回のいずれかしかあり得ない。(K-1が負になるのでめんどくさい...。)Aが連続して良い回数が0の場合、Kは0しかあり得ないし、Bの場合も同様。また、KはAの文字数の上限を超えられないし、Bの場合も同様...。後は極力Aを詰め込んだ時の長さとAの上限数を比較して悪い方がKに対するAの総文字数、Bも同様にして加算して、すべてのKについて最適なものを答えてやる。

500

初項と次の項が与えられ、以降は前二つの項の差分の絶対値とするような、非負の無限整数列を考える。K番目の項を答えよ、という問題。

差分を取るので新規に登場する値は徐々に小さくなっていくはずだが、とても大きい値ととても小さい値が与えられると、次の項はとても大きい値で、その次もとても大きい値で、その次が最初のとても小さい値になる、という過程がかなり長く続くことになる。実はこの3ステップは、大きい方の値から小さい方の値が2回引かれる、ということなので、これを適当に潰してやる。これを潰してしまえば後はユークリッドの互除法と同じオーダーの計算量に落ちるので、愚直にシミュレーションして問題ない。