朝日新聞2005年7月29日パズル横丁解答

プログラムの実行結果は以下の通り。

N:0, cnt:256, hit:100
N:1, cnt:256, hit:155
N:2, cnt:256, hit:130
N:3, cnt:256, hit:100

ちなみに同じ味が存在しないものとしてプログラムを実行した場合の結果は以下の通り。

N:0, cnt:24, hit:6
N:1, cnt:24, hit:11
N:2, cnt:24, hit:10
N:3, cnt:24, hit:6

どちらもN=1の場合最大になっている。

プログラムのソースは以下の通り。

#include "puzutl.h"

void eat( int N)
{
  int cnt = 0;                  // 全ての場合の数
  int hit = 0;                  // 一番おいしいカレーを食べた場合の数
  int aji[10];                    // A,B,C,Dのお店の味の評価。
  //--------------------------------------------------------------------
  // A,B,C,Dのお店の味の全ての可能性を考える。
  // 異なる店が同じ味になる可能性も考える。
  //--------------------------------------------------------------------
  for( int a=1; a<= 4; a++) {
    for( int b=1; b<= 4; b++) {
      for( int c=1; c<= 4; c++) {
        for( int d=1; d<= 4; d++) {
          aji[0] = a;
          aji[1] = b;
          aji[2] = c;
          aji[3] = d;
#if 0 // 同じ味の店が存在しない場合ここを有効にする。
          {
            int dup[5] = {0};
            if( dup[a] > 0) continue;
            dup[a]++;
            if( dup[b] > 0) continue;
            dup[b]++;
            if( dup[c] > 0) continue;
            dup[c]++;
            if( dup[d] > 0) continue;
            dup[d]++;
          }
#endif
          ++cnt;
          //------------------------------------------------------------
          // 一番おいしい味を求める。
          //------------------------------------------------------------
          int ajimax = 0;
          for( int i=0; i< 4; i++) {
            if( aji[i] > ajimax) ajimax = aji[i];
          }
          //------------------------------------------------------------
          // Nまでの店の前を通り過ぎ一番良い味(nmax)を記憶する。
          //------------------------------------------------------------
          int nmax = 0;
          for( i=0; i< N; i++) {
            if( aji[i] > nmax) nmax = aji[i];
          }
          //------------------------------------------------------------
          // 残りの店を調べ，それ以降に以前出現した味よりも良い味があればそれを食べる。
          // 良い味が出ない場合問題。
          //------------------------------------------------------------
          for( ; i< 4; i++) {
            if( aji[i] > nmax) {
              //--------------------------------------------------------
              // 今までよりおいしいカレーが出現した。
              //--------------------------------------------------------
              if( aji[i] == ajimax) hit++;
              break;
            }
          }
          if( i == 4) {
            //----------------------------------------------------------
            // 後戻りできないので渋々最後の店でカレーを食べた。
            //----------------------------------------------------------
            if( aji[3] == ajimax) {
              //--------------------------------------------------------
              // でも今までより美味しくは無いが，結果的にこれが一番おいしいカレーだった。
              //--------------------------------------------------------
              hit++;
            }
          }
        }
      }
    }
  }
  ps( "N:%d, cnt:%d, hit:%d\n", N, cnt, hit);
}

int main( int argc, cstring argv[])
{
  eat(0);
  eat(1);
  eat(2);
  eat(3);
  return    0;
}