Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-07-01

[][] Google Code Jam Round3 Problem D small 01:36 はてなブックマーク -  Google Code Jam Round3 Problem D small  - 練習帳

問題文

 問題文

概要

  • 文字列sが与えられている.長さnで次の条件を満たす文字列が存在するような数nのうち,最小のものを答えよ.
  • 条件:文字列が,文字列sの「2-gram」及び「2-gramの一部分をleet変換して出来るすべての候補」を全て含む.
    • 文字列のN-グラムとは,長さNの部分列の事.例えば「abca」なら「ab」「bc」「ca」
    • leet変換とは特定のアルファベットを形の似ている数字や記号に変換する事.例えば「google」→「g00gle」など.この問題では,"o" → "0", "i" → "1", "e" → "3", "a" → "4", "s" → "5", "t" → "7", "b" → "8" "g" → "9"のleet変換のみ考える.
  • 制限:sの長さは1000以下

コード

 Practiceでの提出コード(gist):https://gist.github.com/2952584

考えた過程

方針1:時間のかかる解き方 → 失敗

最初に思いついた方法は,巡回セールスマン問題に帰着させる方法でした.sの2-gram及び2-gramのleet変換すべてを列挙し,それらをグラフの頂点とします.頂点aから頂点bへのコストは,aの後ろにいくつか文字を加えて,bが接尾辞となる為に必要な最小の文字数とします.すると,全ての頂点を1回ずつ訪問するコストは,解候補となる文字列の長さとなります.従ってそのような訪問コストのうち,最小のものをとれば答えが得られます.

しかし,sの長さが1000なので,部分文字列の個数は1000個,leet変換を施すと候補数は最悪2*2=4倍に増えるので,頂点数が4000の巡回セールスマン問題を解かなければならず,とても時間に間に合いません.

方針2 (その1):簡単な場合の問題に帰着させる

問題を簡単化する事を考えます.leet変換できるような文字がsの中に存在しないとします.例えばs="pqrp"などです.leet変換がない場合に,文字列を2-gramに分解してからごにょごにょするようなアルゴリズムで問題が解けるとします.すると,一般にleet変換がある場合は,同じように2-gramに分解した後,leet変換で拡張してから同じアルゴリズムを適用すれば問題が解けるはずです.まずはleet変換がない場合について考えてみようと思います.

(2-gramに分解せずに解くようなアルゴリズムを用いた場合,そのアルゴリズムをleet変換が含まれるケースに拡張できるかは分かりません.例えばppoの場合,含めるべき2-gramはpp, po, p0だけですが,もとの文字列ppoにp0を追加してしまうと,ppop0となり,含める必要のないopが入ってしまいます.)

方針2 (その2):leet変換がない場合を考える → 失敗

leet変換がない場合,答えはsの長さと同じになるかというと,そうとは限りません.例えば,s="pqppqp"は2-gramの種類としてpq, qp, ppしか持ちません.この3種類の部分列をすべて含む最短の文字列は,sよりも短い"pqpp"などの4文字です.もっと極端なのは,s="ppppppppppppppppppp"などは,"pp"が条件を満たします.

少し気になるのは,全2-gramをunique操作を残った2-gramから,元の文字列を復元する問題は,今解こうとしている問題と同程度に難しい事です.例えば,pqppqrから2-gramをとってunique操作をすると,pq, qp, pp, qrが取り出せます.これらを組み合わせて、もとの文字列のpqppqrを復元する問題は,今解きたい問題から最小性の条件を取り除いたものです.

条件を満たす文字列は可能性としては短くなる事しかあり得ません.そこで,どのような時に短くなるかを考えてみましたが,法則みたいなものは見つかりませんでした.

方針3:2-gramの別の表現方法を考える → うまくいく...らしい

この辺りで手詰まり感が出てきたので,別な方針を考える事にしました.これまではずっと,個々の2-gramを一つの頂点だと思ってきましたが,別の表現方法もありました.つまり,それぞれのアルファベットを頂点だと思って,xyという2-gramがあったら,xからyへ枝を貼るとしてグラフを作っても,2-gramを表現できます.このグラフの場合,最短の文字列を作るのは,すべての枝を通る,最短の一筆書き(重複を許す)を見つける問題に帰着されます.

もし一筆書きが出来るのならば,答えは単純に1+(枝の数)です.しかし,一般の場合には枝の本数より長くならなければなりません.早く提出している人の回答を見てみると,その答えは,1+(枝の数)+max( (Σ_{v} max(out_edge-in_edge, 0) )-1 , 0)となるようです.証明は,例えば節の数についての帰納法等で行えると思うのですが,もう少し直感的な説明が欲しいところです.