T2012 TCO Algorithm > Round 1A

2012 TCO Algorithm > Round 1A

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

250のみ提出。119.35点。レートは995から1016へ。なんとか緑コーダーを維持。Room 20。Room内13位。0点を除けばRoom内最低得点という結果。

	Problem	Status	Points
250	EllysJuice	119.35	119.35
500	EllysFractions	Opened	0.0
1000	EllysLights	Unopened	0.0

• 1問提出
  • 1問目は愚直に実装した。それにしても時間をかけすぎた
  • 2問目の実装途中に終了
• DIV I相当の問題セットだったようだ
  • 難しかった
• チャレンジできなかった
  • 今度から終了後にチャレンジされた実装を見るようにする
• 次回の目標
  • 2問通す(次回はSRMなので、DIV II相当の難易度)

EllysJuice

実装に40分。119.35/250を獲得。

• 総括
  • 愚直な実装しか思いつかなかった
• コードリーディング
  • Room内の実装は皆なかなか愚直であった

提出した実装は以下。

class EllysJuice {
public:
  std::vector<std::string> getWinners(std::vector<std::string> players) {
    const double gallons[8] = {
      1.0 /  2, 1.0 /  2, 
      1.0 /  4, 1.0 /  4, 
      1.0 /  8, 1.0 /  8, 
      1.0 / 16, 1.0 / 16
    };

    int size = players.size();

    std::sort(players.begin(), players.end());

    std::set<std::string> winners;

    do {
      std::map<std::string, double> map;

      for (int i = 0; i < size; i ++)
	map[players[i]] = 0.0;
      
      for (int i = 0; i < size; i ++)
	map[players[i]] += gallons[i];
      
      std::vector<std::pair<double, std::string> > pairs;
      
      for (std::map<std::string, double>::iterator it = map.begin(); it != map.end(); ++ it)
	pairs.push_back(std::make_pair(-it->second, it->first));

      if (pairs.size() > 1) {
	std::sort(pairs.begin(), pairs.end());

	if (pairs[0].first != pairs[1].first)
	  winners.insert(pairs[0].second);
      }
      else {
	winners.insert(pairs[0].second);
      }
    } while (std::next_permutation(players.begin(), players.end()));

    std::vector<std::string> names;

    for (std::set<std::string>::iterator it = winners.begin(); it != winners.end(); ++ it)
      names.push_back(*it);

    std::sort(names.begin(), names.end());

    return names;
  };
};

• • 途中でstd::mapの初期化を行っている

     std::map<std::string, double> map;

      for (int i = 0; i < size; i ++)
	map[players[i]] = 0.0;
      
      for (int i = 0; i < size; i ++)
	map[players[i]] += gallons[i];

• • • 調べてみるに、std::mapはoperator[]を用いてアクセスした要素が存在しない場合に要素を作成するようだ
      • 値の型のデフォルトコンストラクタで初期化される
      • doubleの場合値はstatic_cast(0)となる(Tips (1) - C++ Labyrinthを参照のこと)
    • つまり、この初期化は必要なかったのであった

以下はMac OS X 10.7.3でのstd::mapの実装。

# /usr/include/c++/4.2.1/bits/stl_map.h

      // [23.3.1.2] element access
      /**
       *  @brief  Subscript ( @c [] ) access to %map data.
       *  @param  k  The key for which data should be retrieved.
       *  @return  A reference to the data of the (key,data) %pair.
       *
       *  Allows for easy lookup with the subscript ( @c [] )
       *  operator.  Returns data associated with the key specified in
       *  subscript.  If the key does not exist, a pair with that key
       *  is created using default values, which is then returned.
       *
       *  Lookup requires logarithmic time.
       */
      mapped_type&
      operator[](const key_type& __k)
      {
	// concept requirements
	__glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)

	iterator __i = lower_bound(__k);
	// __i->first is greater than or equivalent to __k.
	if (__i == end() || key_comp()(__k, (*__i).first))
          __i = insert(__i, value_type(__k, mapped_type()));
	return (*__i).second;
      }

• • 上の初期化もそうだが、この手の問題ではPython脳になってしまうようだ
    • Pythonで実装したものと比べてみる。何か共通点がある

#!/usr/local/bin/python3.2 -t

import itertools
import operator


class EllysJuice():
    @staticmethod
    def gallons():
        i = 1 / 2
        while 1:
            yield i
            yield i
            i /= 2

    def getWinners(self, players):
        winners = {}

        for t in itertools.permutations(players):
            d = dict(zip(t, itertools.repeat(0.0)))
            
            for player, gallon in zip(t, self.gallons()):
                d[player] += gallon
                
            pool = sorted(d.items(), key=operator.itemgetter(1), reverse=True)

            if len(pool) == 1 or pool[0][1] != pool[1][1]:
                winners[pool[0][0]] = True

        return tuple(sorted(winners))


if __name__ == '__main__':
    print(EllysJuice().getWinners(("elly",
                                   "kriss",
                                   "stancho",
                                   "elly",
                                   "stancho",
                                   )))

• • 消費ガロン数を図示してみる

• • 0回目、1回目に飲むと1ガロンとなる
    • 2、3、4、5、6、7回目と飲んでも1ガロンにならない(最大で0.75ガロン)
    • つまり2回以上飲む人は必ず勝つ可能性がある
  • ただし参加者が一人だけなのであれば、その参加者が必ず勝つ
    • 後ほど実装し直したときにこの条件を見過ごした
      • つまり、この方法で実装していたらシステムテストで落ちていたということだ。うーむ

以上を踏まえた実装は以下(システムテスト済)。実際に消費する量を考える必要がなくなってしまった。

class EllysJuice {
public:
  std::vector<std::string> getWinners(std::vector<std::string> players) {
    std::map<std::string, int> population;

    for (std::vector<std::string>::iterator it = players.begin(); it != players.end(); ++ it)
      population[*it] ++;

    players.clear();

    if (population.size() == 1) {
      players.push_back(population.begin()->first);
    }
    else {
      for (std::map<std::string, int>::iterator it = population.begin(); it != population.end(); ++ it)
	if (it->second >= 2)
	  players.push_back(it->first);
    }

    std::sort(players.begin(), players.end());

    return players;
  };
};

EllysFractions

30分考えたが解けなかった。0.00/500点。

• 階乗がlong longでも扱えないくらい大きくなってしまい、事実上解けなくなってしまった

実装は以下のようなものであった(システムテストを通らないと思われる。投稿していない)。

class EllysFractions {
public:
  long long getCount(int N) {
    long long result = 0;

    for (long long i = 1, j = 1; i <= N; i ++, j *= i) {
      for (long long k = 1; k * k < j; k ++) {
	long long l = j / k;

	if (l * k == j)
	  if (gcd(k, l) == 1)
	    result ++;
      }
    }

    return result;
  };

  long long gcd(long long a, long long b) {
    while (1) {
      a = a % b;
      
      if (a == 0)
	return b;

      std::swap(a, b);
    }
  };
};

• 後で考える