AtCoder Grand Contest 039参加メモ

Aのみ！以上

A - Connection and Disconnection

文字数Mの文字列Sに対して考えると、連続する文字数を数えて2で割ればよい。 aaa→1個書き換え、aaaa→2個書き換え･･･みたいなん。

• k回のくり返しがある場合
  場合分けしていくとわかりやすい*1。

  • 頭とお尻*2が同じでない場合
    独立に考えることができるのでSについて求め、k倍すればよい。

  • 頭とお尻が同じ場合
    さらに全文字同じ場合と全文字同じではない場合に分ける。

    • 全文字同じ場合
      一つの文字列と考えて、Mxk/2。

    • 全文字同じではない場合
      先頭とは異なる文字(i文字目)からM文字分を一つの文字列と考えれば頭とお尻が同じでない場合と同じように考ることができる。ただしくり返し数はk-1。
      あとは残った頭[0,i)、お尻[i,M+1)について考えて終了*3。
      ※aabba→bbaaaをk-1回繰り返したものと、aaとbbaについて考える

B - Graph Partition

解説読むと簡単に思える不思議。

• 二部グラフを作れる→それをとすれば条件を満たす分け方になる(同集合内でのパスがない)、条件を満たす→二部グラフを作れる
• d+1以上に分割→どこかのを分割→に3つ以上の集合が隣接することになるので満たさなくなる
• ワーシャルフロイド：グラフに含まれる頂点のすべての組の最短距離を求めることができる→最大値がグラフの直径

*1:俺調べ

*2:お頭とは言わないのはなぜだろう･･･

*3:分けなくてもSについて考えれば良いか･･･