SRM 589 Div.1 Easy Medium

こう考えられたらいいなぁというメモ．

どちらもある条件を満たすまでの手数を最小化する問題．

GooseTattarrattatDiv1

各iについて"s[i] = s[n-1-i]"となっていることが条件．

状態ベース

"s[i] = s[n-1-i]"という条件から，対応する文字は必ず同じ文字に変換されなければならない．s[i]=a, s[n-1-i]=bだったら，最終的に，aもbも（何らかの）同じ文字になっている．この関係は推移的．aもbも同じ文字，bもcも同じ文字になるなら，aもcも同じ文字になる．ここで，最初の条件を使い，同じ文字にならなければならない極小の文字集合を求められることが分かる．

命令ベース

"s[i] = s[n-1-i]"という条件から，一方はもう一方に変換されると考える．s[i]=a, s[n-1-i]=bだったら，a->bまたはb->a．a->bまたはb->aとb->cまたはc->bを考えた時，…．

同じ文字にする文字集合を求めた後，
どうするかを考える．
集合以外に含まれる文字にする意味は無い（損するから）．
だから，集合内の文字にする．
どうやって変換するか．
a->b，b->cみたいな変換は確実に損する．
"(aの個数)*2 + (bの個数)"手数かかる．
同等の事は
a->c，b->cでできる．
変換しない文字以外は必ず変換する．
変換する文字は全て変換しない文字に変換すれば，
変換する文字の個数の和で手数の上限を与えられる．
従って，逆に，変換する文字の個数の和以上の手数は必ずかかる．
変換しない文字を決めた時の手数のタイトな値がこれで出た．
で，変換しない文字を個数最大のものとすれば，
それが最小であると分かる．

メモ

「推移的」に飛躍あり．
後半の変換は謎．同等の…が飛躍してる気がする．
上限下限を与えるときの変換しない文字固定が不自然．

GearsDiv1

三部グラフ（のようなもの）から最小頂点を除くことで二部グラフに変換する．

同じ色の頂点は同じグループに属するので，
二部グラフになった時は，
GB:R
BR:G
RG:B
RGB:空
この4パターンしかない．これ以外の状態はありえない．
この時，同じグループに属する頂点間には辺があってはいけない．
最後のパターンだけ飛ばす．
左側には辺がある可能性があるが，これは二部グラフ．
最小で辺を覆う頂点集合（最小点被覆）は二部グラフについては最大マッチングで求められる（知識）．
最後のパターンの最小点被覆は明らかに上3つのパターンを下回らないので計算する必要がない．

メモ

「4パターンしかない」の部分に飛躍があるかも．
こういうRGBの集合で分ける，というところ．