ABC342｜ardririy

久々(初めて？)の5完。やったね✌

A - Yay!

頭をよぎるBLD yay（違う）。

mapを使って数を数えて、各文字ごとに最後に出てくるインデックスを持っておいて...と処理したが、もっと簡潔な方法がありそう。

人iが何番目に並んでいる、というように配列を持ち替えておくことで、クエリの処理が簡単になる。

ある文字cが最終的にどの文字に変わったかの対応表を持っておけば良い。元の文字列を置き換える必要はなく、各アルファベットの今の文字が変わるかを判定して変わる場合に置き換えればいいので、O(Q)(毎ループ26回計算するので定数倍がちょっと重い？)で求まる。

与えられたA_iをそれぞれ平方数で割れるだけ割っておく。この操作を行ったあとの配列をVとして、Vにある要素毎に数を数える。

例えば、ケース1なら配列Vは[0, 3, 2, 2, 3]となる(8, 12はそれぞれ平方数4で割れるので。)

基本的に同じ要素でしかペアになれないので、重複を省きながら数え上げれば良い。ただし、0はどの要素ともペアとなれることに注意する。計算量は素因数分解がボトルネックで、O(N log(max(A))) ← 伝われオーダー記法わからん

問題文がややこしい。各情報について、B → Aに辺を張る。地点Bから地点Nに到達する最遅の時刻が既知であれば、AからBに行く最遅の電車はダイクストラ法っぽい感じで見つけることができるので、する。要するにダイクストラの拡張問題みたいな感じ。