読者です 読者をやめる 読者になる 読者になる

EPOCHまつやま

通りました。id:peryaudoと参加します。

去年がんばったのに落ちて悲しかった。「迫真」で参加します。よろしくおねがいシマス。

去年は「YJSNPI」だから落ちたのかなーと思い、無難な名前を選びました。


した解法

問1.

map使った。

問2.

O(N)で1文字変わっているか判定した。あと1文字追加と1文字削除は等価なことを利用した。

問3.

文字列SをA+B=Cに分けるとすると、+の部分を決めたら、=を右に動かすとA+Bは単調増加し、Cは広義単調減少することが分かる。逆の場合も然り、にぶたん使えそう。

 まあ要するに単調性利用して二分探索。効率悪いのかもしれけないけどまあお手軽に思いつくのでがんばって実装。これより単純にやって枝狩りがんばるほうが速いらしい。むずい。

計算量

テストケース数をTで、数字の長さを|S|とする。

  • 『+』を固定して全て調べるのにO(|S|)
  • 『=』の位置決定するのにO(log |S|)
  • 大小比較に多倍長でO(|S|)。

計算量はO(T・|S|^2 log |S|)。

これだけ見るとかなり絶望的だが、実際には大小比較に桁数とかでチェックしてさぼれるだけさぼっているので、最悪計算量にはなりえない。|S|の部分が結構さぼれるということなので、まあ現実時間で終わる。定数項の最適化と、続いている0の位置判定とかを相方に実装してもらい、かなり高速化されてすごかった。