「メンバー/SGHR/topcoder/同じ数字で挟み撃ち」の編集履歴(バックアップ)一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
*[[問題>https://codeiq.jp/ace/thisweek_masuipeo/q1149]]
*ジャンル
??
*解説
1からnまでの数字が書かれたカードが2枚ずつ全部で2n枚あり、iとiの間のカードがi枚になるような順列の数を数えよ、という問題。
n=11だと総当りは無理だったのでアルゴリズムを以下のように工夫した。
ちなみに答えは(逆順も含めて)35584通りだった。そんなにあるのか。
1.ある数字iのおく場所jを決める。
2.場所j+i+1にiがおけるか判定する。
3.おければiを1増やして1.に戻る。おけなければjを1増やして1.に戻る。
*コード
#highlight(C++,linenumber){{
#include<cmath>
#include<cstdlib>
#include<string>
#include<sstream>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;
int n = 11;
int ans = 0;
void rec(int i, vector<int> cards){
/*
for(int j=0; j<2*n; j++){
cout << cards[j] << " ";
}
cout << endl;
*/
if(i == n+1){
for(int j=0; j<2*n; j++){
cout << cards[j] << " ";
}
cout << endl;
ans++;
}
else{
for(int j=0; j<2*n; j++){
if(j+i+1 <= 2*n-1){
if(cards[j] == 0 && cards[j+i+1] == 0){
cards[j] = i;
cards[j+i+1] = i;
}
else continue;
}
else break;
rec(i+1, cards);
cards[j] = 0;
cards[j+i+1] = 0;
}
}
}
int main(){
vector<int> cards;
cards.resize(2*n);
for(int i=0; i<2*n; i++) cards[i] = 0;
rec(1, cards);
cout << ans << endl;
}
}}
*[[問題>https://codeiq.jp/magazine/2014/11/18658/]]
*ジャンル
??
*解説
1からnまでの数字が書かれたカードが2枚ずつ全部で2n枚あり、iとiの間のカードがi枚になるような順列の数を数えよ、という問題。
n=11だと総当りは無理だったのでアルゴリズムを以下のように工夫した。
ちなみに答えは(逆順も含めて)35584通りだった。そんなにあるのか。
1.ある数字iのおく場所jを決める。
2.場所j+i+1にiがおけるか判定する。
3.おければiを1増やして1.に戻る。おけなければjを1増やして1.に戻る。
*コード
#highlight(C++,linenumber){{
#include<cmath>
#include<cstdlib>
#include<string>
#include<sstream>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;
int n = 11;
int ans = 0;
void rec(int i, vector<int> cards){
/*
for(int j=0; j<2*n; j++){
cout << cards[j] << " ";
}
cout << endl;
*/
if(i == n+1){
for(int j=0; j<2*n; j++){
cout << cards[j] << " ";
}
cout << endl;
ans++;
}
else{
for(int j=0; j<2*n; j++){
if(j+i+1 <= 2*n-1){
if(cards[j] == 0 && cards[j+i+1] == 0){
cards[j] = i;
cards[j+i+1] = i;
}
else continue;
}
else break;
rec(i+1, cards);
cards[j] = 0;
cards[j+i+1] = 0;
}
}
}
int main(){
vector<int> cards;
cards.resize(2*n);
for(int i=0; i<2*n; i++) cards[i] = 0;
rec(1, cards);
cout << ans << endl;
}
}}