cafelier@SRM

SRM435 Div1

SRM | 13:48 |

SRM435 の成績・ソース (要ログイン) : AC/AC/- : だんだんチャレンジ恐怖症になってきた

500開く

• 『2500文字以下のDNA(A,T,G,Cの文字列)と、"3文字->アミノ酸"のマッピング(50マッピング以下)が与えられるので、適当に文字削除して3文字毎に区切って左から右にアミノ酸化して作れるアミノ酸列は何パターンあるか。mod 1000000007で。』

• mod 1000000007 と言ってるので探索はない。
• まあ2500^2*50くらいのDPでしょ

• アミノ酸の個数でループ回すとどうだ
  • 1個目を作る作り方全パターン（i文字目まで使うやり方はn通り、みたいなテーブル）を求める
  • 2個目を作る作り方全パターン（i文字目まで使うやり方はn通り、みたいなテーブル）を求める
  • ...
• 「i文字目まで…」で持つとだめだなー。重複カウントしてしまう。10文字目までで[a,b,c]を作るパターンと20文字目までで[a,b,c]を作るパターンとかそういうのを。
• かといって[a,b,c]とかのパターンを全部覚えたら計算量が指数だ。

• えーと
• いや、[a,b,c]を作るときは常に最左で作るパターンだけ考えればいいんじゃね？
  • さっきのだと20文字目まで使う方は捨てればいい
  • 他で作れるなら最左で作れるパターンからでも作れるので

• ちょっと頭を整理しよう
• dna[0...i] を使って作れるアミノ酸列のパターン数を dp[i] とする。
  • このとき、dna[0...i] でも作れるけどもっと短い dna[0..j], j＜i でも作れるようなパターンはカウントしない
• dp[k] = Σ{dp[i]*u | i=0～k, u=dna[i...k]でちょうどぴったり1個アミノ酸作る作り方}
• だ。
• ちょうどぴったり作れるかどうかは、iからkまでループ回して、まあ適当になんとかなる

• というわけで、個数というよりはDNA上のインデックスで回すDP的なもの
  • dp[k]の計算の時にうしろを参照するよりは、dp[i]の計算の時に表の先の方に足し込んでいってΣを計算する感じになった

• できた
• サンプル通った。まああってるでしょう多分。えいや。

250開く

• 『親の番号の配列、という形式で2分木が与えられる。あと、死んでるノードの番号が与えられる。死んでるノードの子孫でない葉ノードの個数は？』

• 書くだけ問題
• …と思ったけど部屋に245点越えてる人がいない。なにか勘違いしてるかな…

• 全てのノードについて親方向に上っていって
  • 何はともあれご先祖様全部にフラグたてる
  • 死んでるノードが見つかったら自分にフラグたてる
• フラグ立ってないノードの数をカウント。おしまい。

• できた。サンプル通った。
• って自分も240点とかだ。こんなもんかー。
• サブミット。

1000開く

• 問題長いなあ。整理すると…
  • 『50点以下の有向グラフが与えられる。辺を適当に削って複数のツリーにせよ。ツリーの個数を最小にするように。ただし
    • 子から親への（元のグラフでの）パスがあってはいけない
    • 兄弟間に（元のグラフでの）ループがあってはいけない

• さっぱりわからぬ
• とりあえず強連結成分分解したら強連結成分の中身だけ考えればいいようにならないだろうか
  • ならない
  • うーん

• 悩んでいるうちに500がTLEにならないか不安になってきた
  • 適当に最大ケースを作って試してみる
  • 手元で1秒。大丈夫だ

• 「子から親への（元のグラフでの）パスがあってはいけない」という条件は、要するに絶対にツリーにするときに使ってはいけない辺があるというだけの条件か
• 「兄弟間に（元のグラフでの）ループがあってはいけない」は、ツリーにするときに両方使ってはいけない辺ペアという条件になる
• あとツリーを作るというのは、親が２つあってはいけないということなので、これも両方使ってはいけない辺ペアという条件になる
• この辺の制約は前処理して静的に求めておけるな…

• 『最大2500個の使っていい辺のうち、いくつかのペアには同時に使ってはいけないという制約がかかっている。連結成分の個数をできるだけ少なくするように辺を選べ』
• という問題になった。
• 「連結成分の個数」って評価関数はどう評価すればいいのだ。わからん。

• 時間切れ

撃墜タイム

• 250を非常に怪しげな解き方をしてる人がいたので、10分考えて「これだ！」という例を突っ込んだものの、失敗。
  • もうだめぽ
• しかもその人のコードSystem Testで落ちてるよ！僕の目は間違ってなかった！

感想

• 500はもう少しスピーディに解けてもよかった
• 1000全然解けないなー。まずいなー。