AtCoder Beginner Contest 197（Sponsored by Panasonic）
46:42全完ノーペナで46位でした。 久しぶりにノーペナで終えれて嬉しかったです。
A - Rotate
文字列を扱うのはC++よりPythonの方が簡単なのでPythonで実装しました。提出欄直打ちでACしました。
B - Visibility
Bにしては難しい気がします？
$(X, Y)$から上下左右に#が出てくるまで１文字ずつ見ていけばいいです。少し実装に手間取ったので他の人のコードを参考にしたいところです。
C - ORXOR
ぱっと見難しそうですが制約が$N \le 20$と小さいので、bit全探索すればいいです。 より具体的には$N-1$桁の2進数のbitが立っているところと区間の切れ目を対応させて区間の切り方を全探索します。 区間の切り方を決め打ったときに値がどうなるかは$\Theta(N)$で求められ、区間の切り方は$2^{N-1}$通りあるので全体で計算量は$\Theta(N2^{N})$になります。
D - Opposite
まず考察です。$(x_0, y_0)$と$(x_{\frac{N}{2}}, y_{\frac{N}{2}})$を結ぶ直線は正$N$角形の中心を通ります。このことから$(x_0, y_0)$と$(x_{\frac{N}{2}}, y_{\frac{N}{2}})$の中点$((x_0+x_{\frac{N}{2}})/2, (y_0+y_{\frac{N}{2}})/2)$が正$N$角形の中心だと分かります。あとは、この点を中心として$(x_0, y_0)$を$\frac{2\pi}{N}$だけ回転移動させれば$(x_1, y_1)$を求めることができます。
実装ですが、点の回転移動は複素数を使うと便利です。C++だと標準ライブラリにstd::complex<T>があるのでそれを使うとよいと思います。また、点の回転移動にはstd::polarを使うとよいです。
complex - cpprefjp C++日本語リファレンス
E - Traveler
個人的には少し難しいと感じたのに、かなり通されててびっくりしました。
全体の順番としては色の番号が小さい順に取ることしかできないので同じ番号のボールを取る順番を考えます。 よく考えると、最適に動いたとき同じ番号のボールの中で最後に取るのは、同じ番号のボールだけを見たときの両端のボールのどちらかであることが分かります。なぜなら、両端のボールのどちらも取ったときその間にあるボールはすべて回収できているはずだからです。
以上の考察により、各番号について、最後に左端と右端のボールそれぞれをとった場合の最小移動回数を求めていくdpで答えが求められます。
F - Construct a Palindrome
これもそこそこ難しいと思ったんだけど、結構通されてますね...
上手く状態を定義してあげてそれを頂点とした新しい有向グラフを作ります。
状態$v(a, b)$を「頂点$1$から頂点$a$へのパスと頂点$N$から頂点$b$のパスで、それらのパスによって得られる文字列が一致するものが存在する」と定義します。このとき、$v(a, b)$から$v(c, d)$への有向辺が存在する条件は「頂点$a$から頂点$c$を結ぶ辺と頂点$b$から頂点$d$を結ぶ辺で書かれた文字が同じものが存在する」ことです。
このとき$d(0, N)$から$d(N, 0)$へのパスが存在すれば所望の回文が存在することになります。また、辺を１つ通ることは文字を１つ追加することに相当するので距離が回文の最短長になります。嘘でした。解説と同じように偶数か奇数かで場合分けすれば良さそうです。
実際に辺を張るのは同じ文字の辺をまとめて処理することで$O(M^2)$、$d(0, N)$から$d(N, 0)$へのパスの最短長を求めるのは$O(N^2)$で可能です。(新しく作ったグラフ頂点数は$N^2$なので)したがって、全体で$O(M^2+N^2)$でこの問題を解くことができました。
