ホーム » 2015 » 10月 » 14

日別アーカイブ: 2015年10月14日

2015年10月
 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)にかけた結果の行数が少ないものを勝ちとする。

Debianのapache2の設定方法

学生が、Raspberry-PiでCGIを使いたいらしいけど、設定の方法がDebianは一癖あるので、 説明資料を記述。

Debianの原則

Debianでは、基本的な設定ファイルは極力自分で触らない主義。

apache2 も同様で、便利なモジュールも設定ファイルは、必要なものは モジュール毎にインストール時に読み込ませて、触らない主義。

このための設定があって、 CGIとかPHPといったものは、モジュールで管理。

DebianのApache2設定ファイルの考え方

一般的なApacheでは、設定は、/etc/apache2/apache2.conf とか、 /etc/apache2/httpd.conf に記述する。 しかし、いくつものモジュールを使うと、これらの設定ファイルが、 巨大で理解困難になってしまう。

このためDebianのapache2 では、/etc/apache2/*-enabled で対応する。 /etc/apache2/apache2.conf には、以下のような行が書いてあり、 *-enabled配下の設定ファイルをすべて読み込んで起動する。

(( /etc/apache2/apache2.confの一部 ))
 IncludeOptional mods-enabled/*.load
 IncludeOptional mods-enabled/*.conf
 IncludeOptional conf-enabled/*.conf
 IncludeOptional site-enabled/*.conf

/etc/apache2/mods-enabled (mods-available)

  1. 必要なモジュールをインストールすると、 設定ファイルは /etc/apache2/mods-available に書き込まれる。
    (モジュール名.load モジュール名.conf)
      使えるモジュールは、以下のコマンドを使えば、一覧が見れる。
      $ aptitude search libapache2-mod
      インストールしたいモジュールが見つかったら
      $ sudo aptitude install libapache2-mod-モジュール
    
  2. 本当に使いたいモジュールは、以下のコマンドを実行。
      $ sudo /usr/sbin/a2enmod モジュール名
      /etc/apache2/mods-enabled に、mods-available への
      シンボリックリンクを作ってくれる。
    

    使いたくなくなったら、

      $ sudo /usr/sbin/a2dismod モジュール名
    
  3. a2enmodなどを実行したら、以下のコマンドで apache2を再起動
      $ sudo /etc/init.d/apache2 restart
    

    基本原則 /etc/apache2/mods-enabled の配下の設定ファイルは触らない。 どうしても設定ファイルを変更したい場合は、conf-enabled , site-enabled で設定。

/etc/apache2/sites-enabled (sites-available)

  1. apache2では、1台のコンピュータで複数のwebサイトを構築できる。 バーチャルホストの設定は1つのホスト毎に、sites-available の *.conf に記述。 ホスト毎の細かい設定は、この中に記述する。
  2. そのホストを使えるようにしたかったら、以下のコマンド。
      $ sudo /usr/sbin/a2ensite ホスト
      /etc/apache2/site-enabled に、site-available への
      シンボリックリンクを作ってくれる。
    

    ホストを使えないようにする。

      $sudo /usr/sbin/a2dissite ホスト
    
  3. a2ensite を実行したら、"/etc/init.d/apache2 restart"

/etc/apache2/conf-enabled (cont-available)

  1. site-* では、各ホスト毎の設定を書くけど、すべての仮想ホストに共通な 設定は、conf-enabled / conf-available を使う。
  2. 設定を /etc/apache2/conf-available の中に、設定名.conf で記述し、 以下のコマンドで有効にする。
      $ sudo /usr/sbin/a2enconf 設定名
      $ sudo /usr/sbin/a2disconf 設定名
    

(例)

CGIを使いたい (CGIは基本モジュールなのでlibapache2-mod-cgi などはしなくていい)

 $ sudo /usr/sbin/a2enmod cgi  # cgiモジュールの有効化
 $ sudo /etc/init.d/apache2 restart

PHP5を使いたい

 $ sudo aptitude install php5   # PHP5をインストール
 $ sudo aptitude install libapache2-mods-php5
                           # apache2のphp5モジュールをインストール
 $ sudo /usr/sbin/a2enmod php5  # php5モジュールの有効化
 $ sudo /etc/init.d/apache2 restart  # apache2 の再起動

ページは各ユーザの /home/user/public_html/ 配下に作らせたい。

 $ sudo /usr/sbin/a2enmod userdir

SSLのhttps://を使いたい

 $ sudo vi /etc/apache2/site-available/default-ssl.conf
 $ sudo /usr/sbin/a2ensite default-ssl
 $ sudo /etc/init.d/apache2 restart

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー