いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Grand Contest 001 D - Arrays and Palindrome

考察

回文で同じ文字で無いといけない部分に辺を張ると全部に辺が張れればいいとわかる
UF木を考えたけどaの並べ方の列挙とかが必要で間に合う気がしない
なにかこれができれば解けるってパターンがあると思った
もしくは絶対ダメなパターンを見つければいいと思ったのでサンプルを眺める
諦めて解説を読む

解法

http://agc001.contest.atcoder.jp/data/agc/001/editorial.pdf
n点に対して最低でも辺の個数がn-1個無いと達成不可能であることがわかる
回文の性質から奇数長の回文1個につき張れる辺が1本減る
aの数列が全部偶数の場合,aの数列において張れる辺はN/2本
bもN/2本張れるようにすれば,aに含んで良い奇数長の文字列が2個以内だとわかる
あとは解説の図みたいな感じで繋いでいけばいい

Submission #2904435 - AtCoder Grand Contest 001