ABC135

今回はE問題がかなり難しかった。F問題より難しく感じた。 Youtubeの解説放送を聞いて、やっとわかってきた。 自分用のメモなので、日本語が雑になっている。。

ABC #135 D - Digits Parade

dp[i][j]をi桁目まで見た時に、あまりがjとなる場合の数として、求めていく。

ABC #135 E - Golf

事前に、X>=0,Y>=0にしておく

1) X+Yが奇数 かつ Kが偶数

-1を返す。 どうやっても奇数番地にはたどり着けない

2) X+Y>K

n=ceil(X+Y/K)として、X+Y と nK の偶奇が異ればn++とする。余剰 nK-X-Y のために、冗長な経路を作る。 ここで、X=0 だと、序盤の移動において、マンハッタン距離が正しくないので、swap(X,Y)しておく（もちろん出力時には戻す）。

           +(X,Y)
           | Y
(0,0)+     -
   t |     | t = (nK-X-Y)/2
     |-----|
        X

3)X+Y<K

3-1) X+Yが偶数

n=2となる。それ以降の計算は、2) と同じ。

           +(X,Y)
           | Y
(0,0)+     -
   t |     | t = (2K-X-Y)/2
     |-----|
        X

3-2) X+Yが奇数（ 1) の条件よりKも奇数）

n=3になる。これは思いつかない。この場合のみ、X, Y両方向に冗長な経路を取る必要がある。

                      p
                    +----+
                  (X,Y)  | Y
         (0,0)+          -
            t |          | t = K-X
              |-----|----|
                X     p = (K+X-Y)/2

4) X+Y==K

一発で行ける。

ABC #135 F - Strings of Eternity

ローリングハッシュで文字列の比較をO(1)で行えるようにしておく。 他のアルゴリズムでも良いと思う。 あらかじめSを充分に大きくしておく。 UnionFindを用意しておき、 Sのi番目とTがマッチして、なおかつ S の i+T.size() 番目とTがマッチしているときは、 iとi+T.size()に対して、Union処理を行う。 UnionFind全体で、グループの要素数の最大値が答えとなる。