ARC088 E Papple Sort
https://atcoder.jp/contests/arc088/tasks/arc088_c
出現回数が奇数の文字が2個以上あると回文にはできない
回文の後半の文字列(と真ん中の文字)を決めると、回文全体が求まる。
後半をどのように決めるか?
->
後ろから見ていって出現した文字を配列に追加し、対になる文字を削除する。
を配列の長さがn/2になるまで行う。
回文が求まったら元の文字列と比較して隣接swapの必要な回数を求める。
隣接swapの必要な回数の求め方。
元の文字列のそれぞれの文字の位置に移動後の文字列での位置を入れた配列Aを作る。
移動後の文字列ではこの配列は昇順に並び替えられているので、この問題は配列Aを昇順に並び替えるのに必要な隣接swapの回数と言い換えられる。
つまりバブルソートの回数なので、転倒数を数えてやれば良い。
ABC048 D An Ordinary Game
https://atcoder.jp/contests/abc048/tasks/arc064_b
このゲームは二人の合計手数が奇数であれば先手が勝利し、偶数であれば後手が勝利する。
従って
最初の文字列の長さ-最後に残る文字列の長さの偶奇
を調べてやればよい。
ゲーム終了時の文字列の形は
abababab, ..., a (or) bとなる。
最後がaになる場合、最後に残る文字列の長さは必ず奇数長になる。
最後がbになる場合、最後に残る文字列の長さは必ず偶数長になる。
従って最初と最後の文字が同じかどうかを確認すればよい。