問題
考察
N人が何度か1列に並んだ後、隣り合っていない2人組の組み合わせは何通りあったかという問題です。$N≦50$かつ1列に並ぶ回数Mも$M≦50$であることから、愚直にシミュレーションをして最後に隣り合うことがなかった2人組を数え上げても十分に間に合いそうです。
シミュレーションについては、$N×N$の2次元配列$v_{i,j}$を作り、$i$番目の人と$j$番目の人とが隣り合ったことがあるかをフラグで記録するのがいいです。
最終的に$v_{i,j}$の中のフラグが立っていない数を数え上げていきますが、以下の2点に注意して答えを出力してください。
- $v_{i,j}$の$i=j$ものはフラグが立っていなくても数えない。(同一人物であるため無視しておく)
- 数え上げて出てきた数字を2で割って答えを出力する。(求められているものは組み合わせであるため。)
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。