部活16
部活です。
ネタはあるけど、書く時間がないですね。別のことして遊んでるだけなんですけど。
だいぶ戻って、部活8の③「決まった同値類の組から、パネルの組を求める」について。理論は高校数学の範囲ですが、順を追っていきます。
パネルの最高点ごとに同値類分割を行っていますから、最高点がp点のパネルがr枚と言われたらp点のパネルの数nに対してnCr通りの選び方があります。このブログ上だとめちゃめちゃ書きづらいので、nCr を C(n, r)と関数の形にさせてください。
では任意のn, rに対してC(n, r)をリストアップするとき、どう実装するかというところです。
例として{0, 1, 2, 3, 4}の5枚のパネルから2枚選ぶと
{{0,1},{0,2},{0,3},{0,4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
の10通りになります。=C(5,2)=(5*4)/(2*1)=10
ではここで、「0」のパネルに注目すると、
{{0,1},{0,2},{0,3},{0,4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
0が選ばれている赤の方では、0を既に選んでいるので、残り4枚の中から1枚を選んでいます。=C(4,1)=4
逆に0が選ばれていない青の方では、0を選ばないと決めているので、残り4枚の中から2枚を選んでいます。=C(4,2)=(4*3)/(2*1)=6
したがって、C(5,2)=C(4,1)+C(4,2)と表せます。これは一般化すると
C(n,r) = C(n-1,r-1)+C(n-1,r)
となります。つまり、任意のn,rに対してC(n,r)を再帰的に求めることができます。
一旦切ります。
部活15
部活です。
パネしり部といいながらリボルトしかやってない見掛け倒しのブログになっているのでここらで更新。
前回記事で被りを除去する話をしたのでその辺を。
特に難しくもなんともなく上から舐めてあったら飛ばすだけなんですけど。
****************************************************************************************
/* かぶりを判定する関数 */
/* in : [stPanSd*] pstSdNow : 既に作ったリスト */
/* in : [stPanSd] stSdNew : 探索対象 */
/* out : [int] : 0 -> 存在しない / 1 -> 既存 */
int isExistSd(stPanSd* pstSdNow, stPanSd stSdNew) {
･･･
pstSdLoop = pstSdNow; // 検索開始位置
while (pstSdLoop != NULL) { // 全同値類群を見るまでループ
for (iCnt1 = iEqclsMax; iCnt1 >= iEqclsMin; iCnt1--) { // 各点数を使っている枚数をチェック
if (pstSdLoop->iEqclsAry[iCnt1] != stSdNew.iEqclsAry[iCnt1]) {
iEqFlag = 0; // 不一致
break; // 不一致なら抜ける
}
iEqFlag = 1; // 一致
}
if (1 == iEqFlag) return 1; //全部一致したら「既存(1)」
return 0; // 不一致のため「存在しない(0)」
}
****************************************************************************************
これを前々回のコードから呼んで、存在しないときだけ繋げるようにします。
これで、かぶりを登録しなくなるように改良できました。
今日はここまで。
リボルト
雑記です。
CPU戦になかなか勝てず、カードを回収しているのですが
負けるパターンがなんとなく分かってきました。
①単純に乱戦においてスペル対象に選ばれやすい
→シャッター+ホリワn、マジボ*2、シャッター+マジボとかでグルになって攻められると普通にムリ。お前ら絶対同盟組んでるだろ。
②出目の偏り
→サイが2つになって「5」周辺に固まりやすい(4～6で「44.44%」)。この辺の意識が全然なかった。マジボで潰れた土地に止まりにくくなり、逆に潰す土地を計算すれば止まりやすくなったと言い換えてもいいかも。
③序盤の出遅れが負けに直結しやすい
→②の理由もあり、いままでのシリーズより辛い。特に敵領地を踏んだ後更に敵領地を踏む確率が高めというところが失点のスパイラルを引き起こす要因。
一番の問題はやっぱり①で、普通にCPUが数の暴力でひたすらハンドを削ってくるのがキツい。ぶっちぎり3位にもガンガンスペルが飛んでくるので早い段階で少しでも離されたらGp稼ぎも兼ねて打ち切り安定だと思いました。
だってCPUとタイマンだと全く負けないもん(当たり前)。
リンカネはハンド増えないから論外、ホープは絶妙に解決になってないしどうすればいいんでしょうか。
白と黒のとびら
雑記です。
最近フォロワーさんが読んでいる本で気になったものがあったので購入しました。
それがこちら。
まだ1章とちょっとしか読めていないですが、内容はオートマトンの教科書を謎解きチックに書いたものになっています。
何も知らない人にいきなり決定性有限オートマトンの話をするのにこれほど効果的なことがあったでしょうか。
とにかく、「受理」とか「タプル」とかのしちめんどくさい定義がないので、単純な謎解きモノとしてかなりとっつきやすいと思います。
ただ、これを教科書として使うには、これを裏付ける理論の部分の展開が不可欠だと思いますが...
是非解説しながら読みたいところですが、多分著作権的にアウトだと思うので紹介だけにしておきます。
個人的に解説するのは歓迎なので、リプライください。
部活14
部活です。
前回の欠陥について。
正解は、「かぶりを考えていない」です。
例として233点の場合を挙げます。
233点になるパターンは、以下の2パターンあります。
Sa = { 15^1 + 14^4 + 13^9 + 12^4 + 11^1 }
Sb = { 15^1 + 14^4 + 13^8 + 12^6 }
Saから導ける232点の組は、以下の3パターンです。
15, 14, 13がすべて使い切られているため、15, 14は減らせません。
Sa1 = { 15^1 + 14^4 + 13^8 + 12^5 + 11^1 }
Sa2 = { 15^1 + 14^4 + 13^9 + 12^3 + 11^2 }
Sa3 = { 15^1 + 14^4 + 13^9 + 12^4 + 10^1 }
一方Sbから導ける232点の組は、以下の3パターンです。
Sb1 = { 15^1 + 14^3 + 13^9 + 12^6 }
Sb2 = { 15^1 + 14^4 + 13^7 + 12^7 }
Sb3 = { 15^1 + 14^4 + 13^8 + 12^5 + 11^1 }
ここで、Sa1とSb3は同じ組になっていますが、前回のように単純に実装してしまうと既に実施した計算を再度行ってしまうことになります。
せっかく計算量を減らしているのに、これではもったいないので、同じものがあるかを確認する必要があります。
今日はここまで。
部活13
部活です。
テーマは変わらず。
19枚の同値類の組を、和が-1になるように選択しなおすについて。
長いのでさっさといきます。
****************************************************************************************
#define PANEL_SEL 20 // パネルの選択数
/* 19枚選択 */
typedef struct pan_sd {
int iEqclsAry[EQCLS_PT];
struct pan_sd *pstNext;
} stPanSd;
stPanSd *pstSdNow; // 現在探索中の同値類群
stPanSd *pstSdNext; // 次に探索する同値類群
int iSumSd; // 現在探索中の同値類群の和
･･･
pstSdNow = (stPanSd *)calloc(1, sizeof(stPanSd));
/* 最高点を求める */
for(iSel = 0, iSumSd = 0, iCnt1 = iEqclsMax;
(iCnt1 >= iEqclsMin) && (iSel < PANEL_SEL - 1); iCnt1--) {
/* 選択可能数分上から選ぶ */
pstSdNow->iEqclsAry[iCnt1] = MYMIN2(PANEL_SEL-1-iSel, iEqclsidx[iCnt1]);
iSumSd += pstSdNow->iEqclsAry[iCnt1] * iCnt1;
iSel += pstSdNow->iEqclsAry[iCnt1];
}
pstSdNow->pstNext = NULL;
･･･
stPanSd *pstSdLoop; // ループ用
stPanSd *pstSdDmy; // next用
stPanSd *pstSdNew; // アロケーション用
/* ③ */
for(pstSdLoop = pstSdNow, pstSdDmy = pstSdNext; pstSdLoop != NULL; ){
/* ①, ② */
for(iCnt1 = iEqclsMax; iCnt1 >= iEqclsMin; iCnt1--){
if( (pstSdLoop->iEqclsAry[iCnt1] > 0)
&& (iEqclsidx[iCnt1-1] - pstSdLoop->iEqclsAry[iCnt1-1] > 0) ) {
/* -1できる状態なら、-1する */
pstSdNew = (stPanSd *)calloc(1, sizeof(stPanSd));
*pstSdNew = *pstSdLoop; // Sのときの値をコピー
pstSdNew->iEqclsAry[iCnt1]--;
pstSdNew->iEqclsAry[iCnt1-1]++;
pstSdNew->pstNext = NULL; // 次はNULL
pstSdDmy->pstNext = pstSdNew; // 1こ前に繋げる
pstSdDmy = pstSdNew; // 次の保存先を1こずらす
}
}
}
****************************************************************************************
ブログに直書きするの疲れる。
実はこのアルゴリズムには、あることを考慮していないという欠陥があります。どっちかというと前回記事の欠陥ですね。分かった人は私の代わりに実装してください。ぜひ。
(コードのミスはわざとじゃないのであったら教えてください。)
それはまた次回。
