googleのコードジャムというのが先ほどまで有った。本番の問題をコンテスト中に解くと大問題になるだろうが、今回は数珠繋ぎという練習問題の回答を私なりに考えてみた。ただただ、考えてみた。
次に実行してみようとも思ったが、得意の容量計算をすると現在使用しているPCでは限界を大幅に超えていると思ったので実行は思いとどまった。Small inputのみに対応ならいけるだろうが。。。
おおまかにMySQLでの動作を想定しています。このプログラムの実行に関してと構文エラーなどは例の如く保証はしていません。雰囲気のみで見てください。
<<以下その考えた内容>>
/* 設問の回路を最初に用意するパターンを逆に取って、通電及びONとOFFの状態で回路生成する。人手の再現より手間がかかるパターンだが同様の結果が得られる条件に変更している。条件の一致する時だけ回路を用意する分、シミュレーションの高速化が図れる。(プログラムってこうでないといけない気がする。)
今回の設問以前の大きな条件が高速計算と言う点なので、命題の範囲を超えた考えに変更 これで、全体の回路のパターンテーブルが完成。結果、回路を用意するといった命題も最終的にデータテーブルとして用意してカンストしている。入力を見てからの計算でなくて、全入力パターンを網羅するテーブルを用意してそれから検索する点でスピードが違う。データマイニング若しくは、達観的な手法か?*/
create fanction tc returns integer;
create fanction n returns integer;
create fanction k returns integer;
create fanction @1 returns integer;
create database snapper;
use snapper;
create table snapper (id int,i char(1),s char(1),o char(1),k int,n int);
/* idはsnapper回路の通し番号、iはインプット(通電ありなし),sはスイッチ(On,Off),oはアウトプット(通電ありなし),kとnは設問と同じ。
create table snapper1 (id int,i char(1),s char(1),o char(1),k int,n int);
create table mondai (n int,k int);
create table mondai1 (rownum int,n int,k int);
/* ここからは、回路設計ルーチン */
n1=1;
n_loop: while n1< n+1 do;
/* id=1 の初期化 (k=0)*/
insert snapper select set id=1,i='1',s='0',o='0',k=0,n=n1;
k1=1;
k_loop: while k1 < k +1 do;
/* id>1 の初期化 (k=0)*/
n2=n1;
id_loop: while 1 < n2 do;
insert snapper select set id=n2,i='0',s='0',o='0',k=0,n=n1;
n2=n2-1;
while end id_loop;
/*通電状態の再現(スイッチの状態をここでは保存しているのがミソ)*/
delete from snapper1;
insert snapper1 select snapper2.id,'0',snapper2.s,'0',k1,n from snapper,snapper as snapper2
where snapper.i='0' and snapper.id=snapper2.id-1 and snapper.k = k1 and snapper.n = n or snapper.s='0' and snapper.id=snapper2.id-1 and snapper.k = k1 and snapper.n = n1;
insert snapper1 select snapper2.id,'1','1','1',k1,n from snapper,snapper as snapper2
where snapper.i='1' and snapper.s='1' and snapper2.s='1' and snapper.id=snapper2.id-1 and snapper.k = k1 and snapper.n = n1;
insert snapper1 select snapper2.id,'1','0','0',k1,n from snapper,snapper as snapper2
where snapper.i='1' and snapper.s='1' and snapper2.s='0' and snapper.id=snapper2.id-1 and snapper.k = k1 and snapper.n = n1;
insert snapper select * from snapper1;
/*音に反応した場合の再現(通電可能なスイッチの状態だけ変化させているのがミソ)*/
delete from snapper1;
insert snapper1 select id ,'1','1','1',k1+1,n from snapper where s='0' and i='1' and snapper.k = k1 and snapper.n = n1;
insert snapper1 select id ,'1','0','0',k1+1,n from snapper where s='1' and i='1' and snapper.k = k1 and snapper.n = n1;
insert snapper select * from snapper1;
set k1=k1+1;
while end k_loop;
set n1 = n1 + 1;
while end n_loop;
/*後は、そのパターンテーブルと入力ファイルを連係して答を得るルーチン(実際に計算時間の間に行う処理で、最終行はコマンドラインでは不使用*/
/* input.sql: */
use snapper;
/* ファイル名は適当。当然入力ファイルの場所と名前が入ります。*/
load data infile "/home/my/download/input.dat" into table mondai;
insert mondai1 select @i:=@i+1 as rownum,k,n from (select @i:=-1) as dummy,mondai where mondai.n is not null;
/*以下tc.data出力用の処理*/
select n from mondai limit 1;
/* output.sql:(limit の処理部分は命題通りの動作を再現しているだけで、実稼動では削除OK) */
select "case #"+rownum ,':',case o when 1 then "on" when 0 then "off" from mondai1,snapper where mondai1.k=snapper.k and mondai1.n=snapper.n limit 2,tc;
/* select "case #"+rownum ,':',case o when 1 then "on" when 0 then "off" from mondai1,snapper where mondai1.k=snapper.k and mondai1.n=snapper.n; */
/* コマンドラインから実行 tcはトータル行数の数このプログラムの実際の計算には使わない */
mysql < input.sql > tc.data
mysql < output.sql > output.txt
/* output.txt をupしたら完了 */
/* 注意:設問のデータ量上限のパターンを実際に実行するにはテーブルの容量が少なくとも16GBほど必要(減らす方法もあるがここでは書かない)。メモリー32GBほどをラムディスクの設定にしてあれば余裕で計算出来ると思う。回答の制限時間Ｓｍａｌｌで４分、Ｌａｒｇｅ8分だが、これなら実際の計算では無いのでmaxの5000件だったとしても3秒も掛からないやり方になる。(反則?)。時間やコストを無視するとHDDに書きこんで出来る。しかしHDDをクラッシュする確率も高く検証はする予定なし。(特にdelete処理の部分が心配)*/
/* snapperテーブル 回路データ推移の例 n=<3、k=<8
1,"1","0","0",0,1 snapper回路1つで処理開始時のsnapper回路1の状態
1,"1","1","1",1,1 snapper回路1つで処理開始後1度音が鳴った時のsnapper回路1の状態
1,"1","0","0",2,1 snapper回路1つで処理開始後2度音が鳴った時のsnapper回路1の状態
1,"1","1","1",3,1 snapper回路1つで処理開始後3度音が鳴った時のsnapper回路1の状態
.
.
1,"1","0","0",0,2 snapper回路2つで処理開始時のsnapper回路1の状態
1,"1","1","1",1,2 snapper回路2つで処理開始後1度音が鳴った時のsnapper回路1の状態
1,"1","0","0",2,2 snapper回路2つで処理開始後2度音が鳴った時のsnapper回路1の状態
1,"1","1","1",3,2 snapper回路2つで処理開始後3度音が鳴った時のsnapper回路1の状態
1,"1","0","0",4,2 snapper回路2つで処理開始後4度音が鳴った時のsnapper回路1の状態
1,"1","1","1",5,2 snapper回路2つで処理開始後5度音が鳴った時のsnapper回路1の状態
1,"1","0","0",6,2 snapper回路2つで処理開始後6度音が鳴った時のsnapper回路1の状態
1,"1","1","1",7,2 snapper回路2つで処理開始後7度音が鳴った時のsnapper回路1の状態
1,"1","0","0",8,2 snapper回路2つで処理開始後8度音が鳴った時のsnapper回路1の状態
.
.
2,"0","0","0",0,2 snapper回路2つで処理開始時のsnapper回路2の状態
2,"1","0","0",1,2 snapper回路2つで処理開始後1度音が鳴った時のsnapper回路2の状態
2,"0","1","0",2,2 snapper回路2つで処理開始後2度音が鳴った時のsnapper回路2の状態
2,"1","1","1",3,2 snapper回路2つで処理開始後3度音が鳴った時のsnapper回路2の状態
2,"0","0","0",4,2 snapper回路2つで処理開始後4度音が鳴った時のsnapper回路2の状態
2,"1","0","0",5,2 snapper回路2つで処理開始後5度音が鳴った時のsnapper回路2の状態
2,"0","1","0",6,2 snapper回路2つで処理開始後6度音が鳴った時のsnapper回路2の状態
2,"1","1","1",7,2 snapper回路2つで処理開始後7度音が鳴った時のsnapper回路2の状態
2,"0","0","0",8,2 snapper回路2つで処理開始後8度音が鳴った時のsnapper回路2の状態
.
3,"0","0","0",2,3 snapper回路3つで処理開始後2度音が鳴った時のsnapper回路3の状態
3,"1","0","0",3,3 snapper回路3つで処理開始後3度音が鳴った時のsnapper回路3の状態
3,"0","1","0",4,3 snapper回路3つで処理開始後4度音が鳴った時のsnapper回路3の状態
3,"0","1","0",5,3 snapper回路3つで処理開始後5度音が鳴った時のsnapper回路3の状態
3,"0","1","0",6,3 snapper回路3つで処理開始後6度音が鳴った時のsnapper回路3の状態
3,"1","1","1",7,3 snapper回路3つで処理開始後7度音が鳴った時のsnapper回路3の状態
3,"0","0","0",8,3 snapper回路3つで処理開始後8度音が鳴った時のsnapper回路3の状態
.
*/
