高専プロコンの競技部門や、プログラミング甲子園に、学生さんが参加しているけど、 パズル問題は再帰呼び出しとかの経験がないと難しい。
そこで、校内プロコンをやって実力をつけてもらおう…という話がでてきたので、 定番のパズル問題を、私なりにひねってみた。 プログラミング甲子園でも、同じ問題があったかもしれないけど、 一応私が考えた問題をいかに示す。
ぷよぷよ連鎖
6×6のます目に、ぷよぷよのブロックがいくつか落ちた 状態の情報が記録されている。 ブロックを1つ落とすなら、どこがいいか答えよ。
問題は、C言語の配列で与えられる。
- ぷよぷよのブロックの色は、アルファベット1文字で表現し、黄Y,緑G,赤R,青Bの4色とする。
- ブロックの無い場所には空白が入っている。
- 1行の7文字目には\0が入っていて、C言語の配列としては6×7とする。
(例) char field[6][7] = { " " , " GGGB" , " YYYBG" , " RRGRR" , "BBRGRB" , "RRBGBR" , } ;
このマス目にぷよぷよのブロックを1つ落とす。 どこに何色を落とすと何ブロック消せるか求め、 消えるブロック数が最大となる場合の、場所と色を答えよ。 連鎖のルールはぷよぷよと同じとする。
最大の式
文字列で与えられた数字と演算子を組み合わせて数式を作る。 その数式の最大値を答えよ。
式をつくる条件は以下の通りとする。
- 数字は1桁とし、必ず間に演算子を挟むこと。(43はNG)
- すべての文字を使わなくてもいい
- 同じ数字や演算子を2度使うのは禁止。112+*が与えられた場合、2*2+2はNG。2*1+1はOK
- 与えられる文字は、0-9,+,-,*,/,(,)
- 0除算が発生する式はNGで、C言語の文法として正しいこと。
int max_exp( char exp[] , char src[] ) { // src: 与えられる文字 // exp: 答えの式 // 返り値: その式の値 } int main() { char ans[ 10 ] ; int ans = max_exp( ans , "1234+-*" ) ; printf( "%s = %d\n" , exp , ans ) ; // たぶん、4*3+2 が答えだと思う。 return 0 ; }
8クイーンの将棋バージョン
プログラミングの組み合わせ問題の有名なもので、8クイーンがある。 8クイーンは、チェスの盤面にお互いに取られないように、8つのクイーンの 置き方を答える問題。
これの将棋バージョンの問題として、以下2つの問題を答えよ。
- 9竜馬
- 9桂馬
- 9×9の将棋盤上に、竜馬(成り角)をお互い取られないように並べたい。 最大おける個数とその配置を答えよ。別解が複数ある場合は、最低1つ出力すればよい(全解でもよい)。
- 同じく、9×9の将棋盤上に、敵方向に向いた桂馬をできるだけ多く並べたい。 ただし、各桂馬は、次の1手が打てること。 次の1手で移動した先に、他の桂馬が無いこと。
この条件を満たすように桂馬を置く場合、最大いくつ置けるか? その配置も答えよ。
評価方法
以上のプログラムを、すべての提出されたプログラムがそろった段階で、すべてを実行させ 最適解を答えられたものについて、処理速度とシンプルさで評価する。
処理速度は、答えやデバッグ用出力をすべてコメントアウトし、 処理関数を100回とか1000回とか複数回実行させるようにしたプログラムで、コンパイルする。 処理開始、処理終了の時間差を求めて比較する。(unixのtimeコマンドなどで比較)
プログラム言語は、問題趣旨に沿っていれば、なんでもよい。 ただし、コンパイル結果の時間で比べるため、 同一プログラムがJavaプログラムとCプログラムであれば、 C言語の方が有利となる。
プログラムのシンプルさについては、空白行やC言語のプリプロセッサ行を消した状態で、 一般的なプログラム清書プログラム(例えばcb)にかけた結果の行数が少ないものを勝ちとする。