Bは、考察で勘違いがあったものの、実装もミスってたためシステムテストを通って救われました……。
コンテストへのリンク
A. Mind Control
何人に前を取ってもらい、何人に後ろを取ってもらうか、さえ決めれば、何番目の人を説得しても変わらないと気付くのが重要。
あとは、前を取るよう何人説得したか、で全探索（で、できるものの、結構混乱しやすく難しい）。
B. Irreducible Anagrams
これは実験してみるしかない気がしますが……。
「1文字目～k文字目まで」(k=1から最後の一つ前)が全てアナグラムになってないことが必要なので、そうなる条件を考えていく感じかなぁ。
sampleにある、"abb"に対して"bba"がirreducible、ということから最初と最後の文字が重要そう、と気付いた後、同じ文字でも、"abca"→"caab"のように、他に二つ文字があれば構成可能、と気付ければ解ける。
どうすれば速く解けるかはよく分からない……。
C. Prefix Enlightenment
主にアルメリアさんのブログ記事を参考に解説ACしたものの、理解にも実装にも苦しみました。
とりあえず、こういう問題はグラフへ帰着すると良い、という点ではAtCoder Beginner Contest 155 F - Perils in Parallelの類題といっていいと思う。
その後は、一つ一つ変化したときに状況がどう変わるかをじっと調べる感じか。スイッチの重なりが高々二つなので、場合分けをする……というのも言われてみれば自然ではある。
いやぁ、難しい。
0 件のコメント:
コメントを投稿