betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング B - Reversi 解法 まず、1つ性質を確認しておきます。それは「石の色を塗り替える操作について、両端と同じ色を間にも含むような区間に対する操作は考えなくても良い」ということです。具体的には以下の図の上側に示すような操作です。このような操作は下側のように小分けにした操作と同じになるので、小分けにした操作だけを考えて良いです。この性質は後で使います。 答えの求め方ですが、左からDPをします。以下のようにDPテーブルを定義します。 左端から 番目までの石だけで考えた時の、色の塗られ方の場合の数 を求めるための遷移を考えます。 としてあり得るものとして、まず「 番目までの塗られ方それぞれについ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F03%2F17%2F011847" title="AGC031 B - Reversi - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/betrue12/20190317/20190317011038.png Hatena Blog https://hatena.blog 2019-03-17 01:18:47 rich https://betrue12.hateblo.jp/entry/2019/03/17/011847 1.0 100%