制限酵素地図・問題に落とし込むまで

今回は珍しく（？）医学or生物学関連のことについて書きます。
生化学の実習で制限酵素地図というものを作りました。題材としてはかなり典型的なものだと思います。

制限酵素というのは、特定の配列の部分を切り取ることができるもので、制限酵素地図を書くというときは、
大体大腸菌とかの環状プラスミドDNAを用いたものが多いです。
では制限酵素地図がどういうものか、ということですが、https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1375408703
この知恵袋の解答が比較的わかりやすいです。
DNAにある制限酵素をぶち込んで切断させたのをアガロース電気泳動させたら複数本バンドが出ます。移動度からbp数がざっくり割り出せるので、例えば既知のプラスミドに未知の配列が挿入されたプラスミドを扱うとき、いくつかの制限酵素で実験してデータを取ることで、
未知の配列の詳細な塩基情報がわからなくとも、配列がどのくらいの長さでどんな切れ方をするか、つまり切れるところでどんな配列があるのかを推定することができます。
ここまでが準備で、ここからが本題です。
ここで扱うことは、（最低限のもとのプラスミドの情報がある中で）電気泳動の結果を入力で受け取り、挿入される配列がどこで切れるか、というのを出力するということです。競プロではBか簡単めのC問題くらいでしょうか。

文だけだとわかりにくいので一つ簡単な例を表します。
○が塩基を表し、緑字が制限酵素が切る可能性のあるところを表します。もとの配列の情報は十分あるので、制限酵素がどこをきるか、ということは把握済みとします。そして、問題の本質とは関係ない煩雑さを取り除くために、挿入前の塩基列で制限酵素が切るところはないとします（切るのは挿入配列のところのみ）。たとえば下の図で、たとえば制限酵素Aがサイト（緑字）12と10を切るなら、その結果2bp, 14bpのフラグメントが出てきます。

IMG_7235.HEIC

1932147 Bytes

ファイルダウンロードについて

ダウンロード

これで大筋は理解していただけたと思うので、問題を具体的に設定し、解きます。
問題文
上図のように、Nbpのプラスミド(0~N-1の番号がつく）に長さMのプラスミドが挿入されたケースを考えます。
0~L-1の番号がついたL個の制限酵素を使います(N、M、Lが入力として初めに与えられます）。次にそれらの酵素を順番に単体で使った時のフラグメントの情報が提示され、その後
L個の制限酵素のうち２個を取り出し使った時のフラグメントの情報が与えられます。その順序としては、例えばL=3の時
酵素0 酵素1 (フラグメントの情報）
酵素0 酵素2 (フラグメントの情報）
酵素1 酵素２ (フラグメントの情報）　
のようになります。フラグメントの情報は、ピースの個数kと、ピースの長さを短い順に、たとえば2bpと4bpのピースがあれば
2 2 4
のような形で与えられます。なお、酵素の番号は入力には含まれません。
例えばN=30、M=20、L=2で酵素０が34, 36を切り、Bが35, 37を切るとします。すると、入力の様子は、
30 20 2
2 2 48
2 2 48
4 1 1 1 47
となります。そのため、出力は
34 36
35 37
となるようなものを組む必要があります。
それぞれの制限酵素の切断サイトの位置(定義は上の図のよう)を順に出力してください。例えば酵素１のサイトが10,11、酵素２のサイトが23なら
1 10 11
2 13
のように出力してください。
また、複数個解がある場合は全て出力してください。
制約
・入力は皆０以上の整数
・30<=N<=40
・20<=M<=29
・L=4
・2<=k<=4
・一つ酵素を用いたアッセイで出るバンドの長さは皆異なるものとする

（具体例）
入力
30 20 4
2 10 40
2 12 38
3 3 5 42
3 2 5 43
4 2 4 8 36
5 1 3 3 4 39
5 1 2 2 5 40
5 1 3 3 5 38
5 1 1 5 6 37
5 2 2 3 3 40

出力
0 29 39
1 31 43
2 32 35 40
3 30 32 37
0 30 40
1 32 44
2 33 36 41
3 31 33 38
0 31 41
1 33 45
2 34 37 42
3 32 34 39
0 32 42
1 34 46
2 35 38 43
3 33 35 40
0 33 43
1 29 41
2 32 37 40
3 35 40 42
0 33 43
1 35 47
2 36 39 44
3 34 36 41
0 34 44
1 30 42
2 33 38 41
3 36 41 43
0 34 44
1 36 48
2 37 40 45
3 35 37 42
0 35 45
1 31 43
2 34 39 42
3 37 42 44
0 35 45
1 37 49
2 38 41 46
3 36 38 43
0 36 46
1 32 44
2 35 40 43
3 38 43 45
0 37 47
1 33 45
2 36 41 44
3 39 44 46
0 38 48
1 34 46
2 37 42 45
3 40 45 47
0 39 49
1 35 47
2 38 43 46
3 41 46 48