2004/Contest/愛媛大会
ソースたち †
方針 †
- combat
- 判定すべき距離が2までなのがポイント。
- 各ログインネームについて、1ステップで生成できる文字列をsetに入れる。距離2の判定をするにはこれらのsetに共通要素があるかを調べる。
- このように両側から探索することでオーダーが平方根になります。--村主
- Maximum-TNT
- 聞いた(私はAしか問題読んでません)感じ動的計画法な問題がこれしかなかったので動的計画法で。各ログインネームの組みに対してEdit distanceを求める。Edit distanceの計算には各ログインネームの長さ同士の積の計算量が必要。
- 挿入、削除、置換はそのまんまEdit distanceのものを使う。
- 交換は単純に交換、交換後挿入、削除後交換の三種類がある。
- 全体の計算量はログインネームの数の２乗で収まる。
感想 †
- Maximum-TNT
- 初期化をミスっていました。典型問題は全て正しいコードを持っていきましょう。 -- 黄
|
combat