hotpepsiの練習帳

SRM 572

02:21

Div1 Easy (250) NewArenaPassword

問題

• 新しいパスワードルールでは、先頭のK文字と末尾のK文字が一致する必要がある。
• 古いパスワードが与えられる。
• ルールに適合するために変更しなければならない文字数を求める。

方針

• メモ化探索で提出
• MLE
• 適当に書き直して提出
• Challenge Succeeded
• (終了後)
• 解き直し
• length - Kの周期を持つらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_572/NewArenaPassword.cpp

Div1 Medium (500) EllysBulls

問題

• 数当てゲーム
• 推測した数字(guess)と、当たりの総数(bulls)の配列が与えられる
• 元の数がわかるなら答える

方針

• さっぱりわからない
• (終了後)
• 半分全列挙らしい
• しめじたんのソースを読む
• mapのキーがvector...素晴らしい
• 前半と後半の桁にわける
• 前半を全部列挙して、bullsを全部試す
• 初期値を各bullとして、guessと一致したら-1していき、総数が負にならない数とbullのペアを記憶する
• ここで記憶するbullは、前半でヒットしなかった総数なので、後半でヒットすべき
• 後半を全部列挙して、bullsを全部試す
• 初期値をゼロとして、各桁について、guessと一致したら+1していき、先に記憶していたbullと一致するものがあれば、それは前半と後半両方の条件を満たす
• 複数マッチするものがあるなら"Ambiguity"
• 一つもマッチしなかったら"Liar"
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_572/EllysBulls.cpp

結果

x-- 0pt rating 1401 -> 1330 (-71)

周期性を持つパスワードって...