Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2009-01-06

SRM 432

23:57

o x opened. Cruel Systest:(

250 o

K回のon offで全部つけるのが可能なパターンのうち、もっとも多くでてくるものを答える。

mapで集計してから順番に判定しました。

500 system test failed.

超時間かかったのにsystem test failed. 酷いです。私のコードが。

一度半分書いてから書き直しました。

取り合えず書いてみる...?

まず考えたのは、取り合えず条件からくっつけなければいけないものをくっつけて、それから考えるというものでした。

  • それからっていつ? 一応parts.size()回だけ回せばいいか。
  • くっつける場合、partsを舐めた上で、くっつけるのに必要な要素を取り除かないといけない。取り除く要素を覚えておいて後でまとめてerase? ただでさえeraseは面倒です。
  • くっつけた要素はどこに保持しておくのか。dequeかlistにして、片方の端から観察して、生成物はもう片方の端につけるのが常套手段?

どうも実装が怪しくなってきました。そのうちに別の実装が固まってきたのでそちらに変更しました。


頭と尻尾をちゃんと数えてからつなげてみる。

aaaaaなどの一種類で始まる文字列を全部除くと、ある文字で始まる文字列やある文字で終わる文字列は高々一つしかありません。これをあらかじめ数えておけば問題はありません。

26文字について、次の要素を調べます。

  • その文字のみからなる文字列の、文字の長さの合計。(case 0なら aのこれが6つ。case 3ならs,tに一つずつあります)
  • 上に当てはまらない文字列の中で、以下のもの。

下三つは、それらに当てはまる文字列が二つ以上あったら即IMPOSSIBLEです。それから、"その文字を中間に含む文字列"が存在する場合は、他の要素があると即IMPOSSIBLEです。

これらを調べてから、次の順番で判定を行いました。

  • 下三つが無い場合(すべての文字列がaaaaやdなど一種類の文字からなる場合), MANYか正解例を返す。
  • 開始可能な文字、すなわちその文字で始まる文字列が一つあり、その文字で終わる文字列が無いような文字を探す。
    • これが存在しない場合は{"ab", "bc", "ca"}などのループなのでIMPOSSIBLE.
    • これが複数存在する場合はMANY.
    • これが唯一存在するなら、次の項目へ。
  • 開始可能な文字からはじめて、上のテーブルを参考に元の文字列を構築してゆく。
    • 開始可能な文字が一つしかないので、それ以外の文字列の頭文字には必ずその前にくる文字列が存在する。
    • 文字列を連結するときに、ちゃんと"その文字のみからなる文字列"を足しておくこと。
  • 元の文字列を構築し終わったときに、"その文字のみからなる文字列"が残っているならMANY. 残っていなければ構築した文字列を返す。
    • ここでMANYになる例は例3 {"te", "s", "t"}。tが開始可能文字でsが余ります。

Challengeは喰らいませんでしたがSystem Testで刺さりました。

今気づきましたが。ab cdcをabで返していました。cdcの検出忘れでした。それからabc bbをMANYで返していました。"*b*"と"bbb"が共存できないという判定を忘れています。酷いな。

条件が複雑になっているのがまずいと思います。どうすれば良かったのか。

1000 opened

残り15分で考えたのはGreedyにPrimをやればとけるかなといったあたりでした。おそらく解けるはずです。

Challenge Phase. None

全然刺せませんでした。部屋では500がかなり刺されていましたがどうしたものかと。Challenge Phaseが終わった後の会話によると何か非常にspecificなケースで殺している例がありました。みんなどうやってそこまで読み込むのでしょう。

反省点

  • 500に時間がかかりまくった。
  • おそらく1000の方が簡単だった。週末に解く。
  • 時間中の身の振り方が分からないので、時間を区切った練習セッションをしないといけないはず。
    • 500で手間取っているのは前回と同じ。ここを変えないとずっと500が解けるか解けないかの1600点プレイヤーのまま裏世界でひっそり幕を閉じる
 |