4完2WA

各問題

A - Yay!

1文字目と2文字目が同じとき、1文字目と違う文字を3文字目以降で探せばよいです。

1文字目と2文字目が異なるとき、1文字目と3文字目が同じなら2文字目が他と異なり、1文字目と3文字目が異なるなら1文字目が他と異なるとなります。

N, Q が小さいので、毎回 P を前からみていって A, B のうち先に現れた方が答えとしてよいです。

S に対して直接操作を行うと間に合いませんが、"abcdefghijklmnopqrstuvwxyz" という文字列を作ってそれに対して操作をしてから、操作後の文字を S に当てはめていけば O(N + Q) になります。

"abcdefghijklmnopqrstuvwxyz" を自力で書いたんですが、typo して 2WA...。あほすぎる。

とりあえず素因数分解して、平方数でないものは偶数でない素因数を一つずつ集めた集合とみなします。12 なら -> [2]、24 なら 2³ * 3 -> [2, 3] といった要領で。

で、グループ分けします。

各グループ内では掛け合わせると平方数になるのでそれをまず求めます。グループをまたぐとき、平方数と平方数でないものはかけても平方数にならないので放置です。0 とそれ以外の数は常に平方数なのでその個数も求めます。

以上を足し合わせたものが答えです。

DP 的なことができるんだろうかどうだろうかで結局わからず。

D はさくっと解けたのに C の typo でパフォを溶かしてしまってげんなり...。