Hatena::Grouptopcoder

hotpepsiの練習帳

2011-09-28

SRM 516 Div2

22:41

Easy (250) NetworkXZeroOne

問題

  • oとxだけからなる文字列があり
  • 破損して?になっている部分を復元する

方針

  • oxoxかxoxoのように交互のものを作ればよい

実装

Medium (500) NetworkXOneTimePad

問題

  • 平文と暗号文から鍵の候補を生成する
  • 鍵の候補について、暗号文から平文を生成する
  • 暗号文の全要素が平文に存在すれば鍵

方針

  • 平文と暗号文をXORしたものを鍵候補としてsetに突っ込む
  • 各鍵について各暗号文でループしてチェック

実装

Hard (1000) NetworkXMessageRecovery

問題

  • 破損した部分文字列から、元の文字列を復元する
  • それぞれの文字は1回しか出現しない
  • 複数の候補がある場合はアルファベット順

方針

  • 文字Xについて、それよりも前にある全ての文字A,B,C...を記憶しておく
  • ある文字Yについて、Yよりも前かつ未出力の文字がなければYを出力

実装

結果

oxx 209.00+310.71*0+516.54*0 1117 -> 1076

Easyは、oとxが交互であることが問題文から読み取れず、時間がかかった。

落ち着いて読んだら「任意の偶数個のsubsequenceに含まれる個数が一緒」と書いてあるので必ず交互になる。

Mediumも問題文を斜め読みして、鍵の候補を結果にしたためにsystem test failとなった。

終了後解きなおした。

今回初めてHardのsubmitまでできた。1行breakの位置が違っていたがほぼできてたのでよしとする。

しかしこの一箇所のバグで撃墜されたので、ちゃんと読んでるだなあと思った。

Hardについては、後ろから1文字ずつ処理するとシンプルに書けそうだ。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20110928