Single Round Match 537 - agwの日記

Single Round Match 537 Round 1 - Division II:

http://community.topcoder.com/stat?c=round_overview&er=5&rd=14730

1問通過。2回のチャレンジ成功。332.72点。レートは857から958へ。~~白コーダー~~灰コーダーから緑コーダーへ。Roomは95。Room内4位。

	Problem	Status	Points
250	KingXNewBaby	Passed System Test	232.72
550	KingXNewCurrency	Opened	0.0
925	PrinceXToastbook	Unopened	0.0

1問通した。目標を大幅に下回った
Mediumに65分使った挙げ句、解法が全く思いつかなかったというありさま
初チャレンジ。Easyで2回成功
- 他のユーザーがチャレンジで落とした投稿にはチャレンジできないことを知った
- 1回50点がかなり大きいことに気付く
  - Easyに35分かかると130点とかになってしまう。Easyに10分かけて230点獲得した場合と比べチャレンジ成功2回分の点差がある
- チャレンジを成功するととても気持ちがいいことに気付いてしまった。病み付きになりそうだ
休憩の間にEasyのテストを書こうとしたが、5分で書けなかった
- テストはPythonで記述しようとした
- C++で記述したほうがよいのかもしれないなと思った
プラグインを変更した
- テストの見通しがよくなったため、チャレンジする前に自分の実装で成立するかどうかを余裕を持ってテストすることができた
次回の目標
- 2問通す
- Roomのより上位を目指す
- レートを落とさない(どうやる?)

KingXNewBaby

問題を読むのに2分。実装とテストに7分。232.72/250.00獲得。

総括
- 文字列に2回出現する母音が2セット以上あった場合に不適合とする処理を入れるのをすっかり忘れていた
  - テストに助けられた
  - テストに頼らないようにしないと
- 文字列は小文字アルファベットのみで構成される条件を読み飛ばしていて、そのチェック処理を入れてしまった
  - チャレンジフェーズでアルファベットのチェックをしていない投稿に注目してしまい、危うくチャレンジしようとしてしまった
  - 条件に気付き、無駄なチャレンジをせずに済んだが時間を浪費してしまった
コードリーディング
- 最後に出現した母音を保持する実装が多かった
  - 母音が3個出現した時点で、また2つ目に出現した母音が1つ目のものと異った時点で停止することができる(ように思う)
- メモリは多少使うけれど、この実装を結構気に入っていたりする
  - 配列に入れてしまう発想か?
  - Python/jQuery/Prototype.js的だから?
  - ああ、そうか。Pythonで書けば以下のことをしていたのか

  vowels = list(filter(lambda x: x in "aeiou", name))

提出した実装は以下。

class KingXNewBaby {
public:
  std::string isValid(std::string name) {
    if (name.size() != 8)
      return "NO";

    char vowels[50];

    int i = 0;

    for (std::string::iterator it = name.begin(); it != name.end(); ++ it) {
      char *p = strchr("aeiou", *it);

      if (p) {
	vowels[i ++] = *p;
      }
      else if ('a' <= *it && *it <= 'z') {
	;
      }
      else {
	return "NO";
      }
    }

    return (i == 2 && vowels[0] == vowels[1]) ? "YES" : "NO";
  };
};

入力がアルファベットであるかどうかのチェックは行わなくてよい。すると、以下のような実装となるか(この実装はシステムテストしていない)。

class KingXNewBaby {
public:
  std::string isValid(std::string name) {
    if (name.size() != 8)
      return "NO";

    char vowels[50];

    int i = 0;

    for (std::string::iterator it = name.begin(); it != name.end(); ++ it) {
      char *p = strchr("aeiou", *it);

      if (p)
	vowels[i ++] = *p;
    }

    return (i == 2 && vowels[0] == vowels[1]) ? "YES" : "NO";
  };
};

となるとこんなんでもいいのかな? ちょっとやり過ぎか(この実装はシステムテストしていない)。

class KingXNewBaby {
public:
  std::string isValid(std::string name) {
    if (name.size() != 8)
      return "NO";

    char vowels[50];

    int i = 0;

    for (std::string::iterator it = name.begin(); it != name.end(); ++ it)
      for (char* p = strchr("aeiou", *it); p; vowels[i ++] = *p, p = NULL)
	;

    return (i == 2 && vowels[0] == vowels[1]) ? "YES" : "NO";
  };

KingXNewCurrency

65分かかって何も出来ず。後で全探索の実装からやり直してみたい。0.00/550.00。

追記(2012/3/19)

数論っぽい解法を思いついた。システムテストも通った。
- 全探索での終了条件をどう設定すればよいか今だに思いつかない...

以下は投稿したものをさらにリファクタリングしたもの。

class KingXNewCurrency {
public:
  int howMany(int A, int B, int X) {
    if (A % X == 0 && B % X == 0)
      return -1;

    bool a[200+1], b[200+1];

    if (A % X == 0) {
      std::fill(a, a + 201, true);
    }
    else {
      std::fill(a, a + 201, false);
      
      for (int y = A; y >= 0; y -= X)
	for (int i = 1; i * i <= y; i ++)
	  if (y % i == 0)
	    a[i] = a[y / i] = true;
    }

    if (B % X == 0) {
      std::fill(b, b + 201, true);
    }
    else {
      std::fill(b, b + 201, false);

      for (int y = B; y >= 0; y -= X)
	for (int i = 1; i * i <= y; i ++)
	  if (y % i == 0)
	    b[i] = b[y / i] = true;
    }

    int c = 0;

    for (int i = 1; i <= 200; i ++)
      if (a[i] && b[i])
	c ++;
    
    return c;
  };