CSES -Two Knights
CSESについて
CSESはフィンランドの競プロサイトで問題セットとオンラインジャッジがあります。
この書籍で紹介されていました。
2017_Book_GuideToCompetitiveProgramming
問題
Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.
1*1からk*kまでの各チェス盤について,互いに干渉しないナイトの置き方の数を求めます。
考察
サンプルの出力はn=8で以下のとおりです。
0
6
28
96
252
550
1056
1848
すべての配置の可能性は(n*n)*(n*n-1)/2であり,これから互いに干渉するナイトの位置の数を引くことを考えました。
n=5の場合,互いに干渉するナイトの数は,各マス毎に以下のとおりです。
2 3 4 3 2
3 4 6 4 3
4 6 8 6 4
3 4 6 4 3
2 3 4 3 2
これらの総和は96になり入れ替えを考えると48通りです。
n=5の場合で
(n*n)*(n*n-1)/2=300ですから,
300-48=252でサンプルと合います。
n>=4の場合で
2になるマスが四隅の4か所
3になるマスが四隅のとなりの8か所
4,6,8になるマスはnから計算でき解けました。
n<=3の場合は数値を入れておきます。
ACしたコード
#include <iostream> using namespace std; int main(){ long long x,ans; cin>>x; for(long long n=1;n<=x;n++){ ans=0; if(n==1){ ans=0; } else if(n==2){ ans=6; } else if(n==3){ ans=28; } else{ ans=n*n*(n*n-1)/2-(2*4+3*8+4*(4+(n-4)*4)+6*(n-4)*4+8*(n-4)*(n-4))/2; } cout<<ans<<endl; } return 0; }