1完。
各問題
A - Equal Hamming Distances
まず、S[i] == T[i]
ならそこは0でよいです。以下S[i] != T[i]
の場所だけについて考えます。
SとTの1の個数をそれぞれsn, tnとすると、snとtnが共に偶数(または共に奇数)でなければ構築不可です。(入力例2のパターン。もっと長い文字列でも、交互に1を当てはめていって調整していくと最終的にそのパターンに帰結します(多分))
sn < tn
ならば(不等号が逆の場合、入れ替えて同じ考え方をすればよい)、(tn - sn) / 2
個の1をtnの1に対して割り当てると相殺されていい感じになります。ここで、答えは辞書順最小でなければならないので、1はできるだけ後ろの方に置きたいです。よって'S[i] == 0 and T[i] == 1になる場所に後ろから貪欲に(tn - sn) / 2
個だけ1を置いて他の場所には0を置けば完成です。
B - A < AP
なんとなくどういう性質を持っているかが見えているような見えていないような状態で椅子を温め続けました...。
公式解説を見たら、見えていたと思っていたのは違うなにかだったようです。
まとめ
連続水パフォ記録が9で途切れてしまいました。まあ4桁パフォは12解連続取得中なので、とか書いたらフラグになっちゃうか?