hotpepsiの練習帳

SRM 516 Div2

22:41

Easy (250) NetworkXZeroOne

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_516/NetworkXZeroOne.cpp

Medium (500) NetworkXOneTimePad

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_516/NetworkXOneTimePad.cpp

Hard (1000) NetworkXMessageRecovery

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_516/NetworkXMessageRecovery.cpp

結果

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文字ずつ処理するとシンプルに書けそうだ。