Problem H

Problem H
Restriction Enzyme
解説菅原
解答状況
予想 Accepted 0～
最初のAccepted : 190分
総 Submit
:5
総 Accepted
:1
echizen.com よくがんばった。
問題
DNAを計算に用いたい。
変異が起きると困る。
分子複製中に変異が起きたか検出したい。
DNA鎖の状態を簡単に調べる方法
制限酵素 : DNA鎖を特定の部位で切断できる
断片の長さを測定する装置
まず、制限酵素地図を作ってほしい。
問題
という話だったのさ。
読めましたか？
問題
輪になった鎖があります。
鎖の数箇所を切って、断片を得ました。
輪の長さと断片の長さから、切った場所を特
定してください。
問題
切り方は三通り
切る箇所がAとBとの二種類
Aを切る、Bを切る、両方切る
断片の情報は不完全
長さが同じ断片が複数得られてもひとつしか報告
されない。
答え方
切り方が少ないやつの中からどれでも。
解法
DFSで探索しましょう。
解法
DFSで探索しましょう。
端から順番に、切るか切らないかを決める。
or
or NONE
解法
DFSで探索しましょう。
切れ端はABの幅しかとらない。
端から順に、その幅を取って切ってゆく。
ABの幅
or
解法
DFSで探索しましょう。
存在しない長さの切れ端があるなら、枝刈。
枝刈するとO(3N)からO(2N)くらいに下がります。
解法
環状構造を答える。
→ 相対位置0にAが来ると仮定すると楽。
最後に輪のつじつまを合わせる。

Download Report