Commentsブログの運営方針としてコンテスト後に毎回、問題を取り上げて解説をしていくことになったので今回はこれhttps://beta.atcoder.jp/contests/agc023/tasks/agc023_b問題概要は直接見てください。愚直解から考えてみよう。\(AとB\)をすべて試しそれが条件満たすかどうか調べてその数を数えるというものがある。\(AとB\)の選び方は\(N^{2}\)通り存在し、それが満たすかどうかを調べるにはすべてのマスのペアについて調べる必要があるので\(N^{2}\)かかる。300\)なので\(TLE\)。ここで、この問題を数式で表してみる。一つ目の盤面で\((i,j)\)にある文字は二つ目の盤面では\((i+A,j+B)\)に移動する。良い盤面であるということは二つ目の盤面で\((i’,j’)\)と\((j’,i’)\)の文字が等しいことなので、\((i+A,j+B)\)と\((j+B,i+A)\)の文字がすべて等しいことが条件である。ここで\((j+B,i+A)\)の文字は一つ目の盤面では\((j+B-A,i+A-B)\)にあることが分かるので、結果として、条件は一つ目の盤面で\((i,j)\)と\((j+B-A,i+A-B)\)に書いてある文字が等しいことに言い換えられる。N\))と置くと、一つ目の盤面で\((i,j)\)と\((j+k,i-k)\)の文字が等しければ良く、\(B-A=k\)となる\(A,B\)をまとめることができた。\(k\)で条件を満たした時\(B-A=k\)となる\(A,B\)は\(N-|k|\)通りある。N\)通りなので合計の計算量は\(O(N^{3})\)となりこれは十分間に合う。注意としては\(j+k,i-k\)が\(N\)を以上の場合、\(N\)で剰余をとる必要がある。\(j+k,i-k\)は負になる可能性があるので剰余をとる際に(j+k+N)%Nの様にしておく必要がある。(こうしておくと負にならない)これは頻出のテクニックなので覚えておきましょう。以下は解答例となります。0;}計算量を落とすために同じものをまとめて計算するというのは基本的な考え方で、今回の問題の様に数式で表してみると簡単になる問題は多い気がする。コメントをキャンセルメールアドレスが公開されることはありません。