朝日新聞2004年4月17日のパズルパーク問題

問題

「ピ」と「ョ」と「ン」を使って単語を作る。単語に対する制約は以下の通り

• 「ン」は単語の最初の文字にならない。
• 「ョ」は「ピ」の直後だけに来る。
• 同じ文字や文字列を続けて繰り返すことは出来ない。

以上の制約の元で最長の単語を求める。

解答への考え方(ヒント)

これは簡単な再帰問題である。コードは以下のようになる。

find( level)
{
  if( level > maxLevel) { 最長単語が出現した }
  foreach ch  ( 'ピ' , 'ョ', 'ン') {
    word[level] = ch
    if( 単語が制約条件を満たしているか?) {
      find( level+1)
    }
  }
}

C++にforeach の構文は無いので，for文で表現する。文字を数字に対応させれば，

for( int ch=0; ch<= 2; ch++) 

となる。対応関係は以下の通り。

0 : ピ
1 : ョ
2 : ン

配列word[]に現在のlevelまでの文字を入れ，制約をチェックする関数を呼び出す。

最長単語が出現する毎に単語を出力する。最後に出力された単語が解となる。

同じ文字や文字列を続けて繰り返すことは出来ない

ピピンは「ピ」が繰り返されるのでダメ。ピョンピンピョンも「ンピ」が繰り返されるのでダメ。制約をチェックする関数は以下のようになる。

YesNo 単語が制約条件を満たしているか( int level)
{
  if( word[0] != 0) return NO; // 最初の文字は「ピ」に限る
  for( int i=1; i<= level; i++) {
    if( word[i] == 1 && word[i-1] != 0) return NO; // 「ョ」は「ピ」の直後だけに来る
  }
  for( i=0; i< level; i++) {
    for( int j=1; j<= level-i; j++) {
      if( word[i]からj文字と同じ文字列が直後に出現するなら) return NO;
    }
  }
  return YES;
}

最初の呼び出し

今回のプログラムでは最初の呼び出しを find(0) としたが，最初の1文字は「ピ」であることが判るので，

word[0] = 0; // ピ
find(1);

のようにプログラムしても良い。制約をチェックする関数で word[0] のチェックが要らなくなる。

解速度

即