2012 TCO Algorithm > Round 1C
2012 TCO Algorithm > Round 1C
http://community.topcoder.com/stat?c=round_overview&er=5&rd=15092
75分間250を考えたが何も出来なかった。チャレンジに失敗。-25点。レートは936から753へ。白コーダー灰コーダーに降格。Room 61。
Problem | Status | Points | |
---|---|---|---|
250 | PasswordXGuessing | Opened | 0.0 |
500 | PasswordXGrid | Opened | 0.0 |
1000 | PasswordXPalindrome | Unopened | 0.0 |
- 75分間250を考えたが何も出来なかった
- チャレンジも失敗した
- 後々考えてみるとRoom内で一番よく書けている実装に対してチャレンジしていた
- 次回の目標
- 1問通す(次回はSRMなので、DIV II相当の難易度)
- 250を提出するスピードを上げる
- 最近は30分を超えていることが多い
PasswordXGuessing
75分考えて何も出来なかった。0点。
- 後で考えれば簡単な問題だった
- 全ての推測したパスワードは必ず1文字間違えている
- つまり、正解のパスワードと推測したパスワードを比較すると1文字違うはず
- ならば正解のパスワードの候補を用意して、整合性を調べてやればよい
- 推測したどのパスワードも1文字以外は正解のパスワードと合っているので、どの推測したパスワードを元にしてもよい
- 初めのものを選択
- 推測したパスワードのどの1文字が間違えているか分からない
- ならば1文字ずつ間違えていると仮定して、全部試す
- 選択したパスワードそのものも試す
- 推測したどのパスワードも1文字以外は正解のパスワードと合っているので、どの推測したパスワードを元にしてもよい
- パスワードの文字数は高々50文字
- パスワードの種類も高々10文字
- パスワードの候補数も高々50
- 十分間に合う
- 全ての推測したパスワードは必ず1文字間違えている
実装は以下(システムテストを通した)。
class PasswordXGuessing { public: long long howMany(std::vector<std::string> guesses) { int h = guesses.size(), w = guesses[0].size(); long long c = 0; for (int j = 0; j < w; j ++) { std::string passwd = guesses[0]; for (int k = '0'; k <= '9'; k ++) { passwd[j] = k; int n = 0; for (int i = 0; i < h; i ++) if (diff(passwd, guesses[i]) == 1) n ++; if (n == h) c ++; } } return c; }; int diff(std::string a, std::string b) { int c = 0; for (int i = 0, size = a.size(); i < size; i ++) if (a[i] != b[i]) c ++; return c; }; };