ホーム » スタッフ » 斉藤徹 » 校内プロコンの問題

2015年10月
« 9月   11月 »
 123
45678910
11121314151617
18192021222324
25262728293031

最近の投稿(電子情報)

アーカイブ

カテゴリー

校内プロコンの問題

高専プロコンの競技部門や、プログラミング甲子園に、学生さんが参加しているけど、 パズル問題は再帰呼び出しとかの経験がないと難しい。

そこで、校内プロコンをやって実力をつけてもらおう…という話がでてきたので、 定番のパズル問題を、私なりにひねってみた。 プログラミング甲子園でも、同じ問題があったかもしれないけど、 一応私が考えた問題をいかに示す。

ぷよぷよ連鎖

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の将棋盤上に、竜馬(成り角)をお互い取られないように並べたい。 最大おける個数とその配置を答えよ。別解が複数ある場合は、最低1つ出力すればよい(全解でもよい)。
9桂馬
同じく、9×9の将棋盤上に、敵方向に向いた桂馬をできるだけ多く並べたい。 ただし、各桂馬は、次の1手が打てること。 次の1手で移動した先に、他の桂馬が無いこと。
この条件を満たすように桂馬を置く場合、最大いくつ置けるか? その配置も答えよ。

評価方法

以上のプログラムを、すべての提出されたプログラムがそろった段階で、すべてを実行させ 最適解を答えられたものについて、処理速度とシンプルさで評価する。

処理速度は、答えやデバッグ用出力をすべてコメントアウトし、 処理関数を100回とか1000回とか複数回実行させるようにしたプログラムで、コンパイルする。 処理開始、処理終了の時間差を求めて比較する。(unixのtimeコマンドなどで比較)

プログラム言語は、問題趣旨に沿っていれば、なんでもよい。 ただし、コンパイル結果の時間で比べるため、 同一プログラムがJavaプログラムとCプログラムであれば、 C言語の方が有利となる。

プログラムのシンプルさについては、空白行やC言語のプリプロセッサ行を消した状態で、 一般的なプログラム清書プログラム(例えばcb)にかけた結果の行数が少ないものを勝ちとする。