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
250	PasswordXGuessing	Opened
500	PasswordXGrid	Opened
1000	PasswordXPalindrome	Unopened

75分間250を考えたが何も出来なかった
チャレンジも失敗した
- 後々考えてみるとRoom内で一番よく書けている実装に対してチャレンジしていた
次回の目標
- 1問通す(次回はSRMなので、DIV II相当の難易度)
- 250を提出するスピードを上げる
  - 最近は30分を超えていることが多い

PasswordXGuessing

75分考えて何も出来なかった。0点。

後で考えれば簡単な問題だった
- 全ての推測したパスワードは必ず1文字間違えている
  - つまり、正解のパスワードと推測したパスワードを比較すると1文字違うはず
- ならば正解のパスワードの候補を用意して、整合性を調べてやればよい
  - 推測したどのパスワードも1文字以外は正解のパスワードと合っているので、どの推測したパスワードを元にしてもよい
    - 初めのものを選択
  - 推測したパスワードのどの1文字が間違えているか分からない
    - ならば1文字ずつ間違えていると仮定して、全部試す
    - 選択したパスワードそのものも試す
- パスワードの文字数は高々50文字
- パスワードの種類も高々10文字
- パスワードの候補数も高々50
  - 十分間に合う

実装は以下(システムテストを通した)。

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;
  };
};