「や」の字: Google Code Jam 2013 Qualification Round

結果

D-Large が Timeout した以外は全部提出しましたが、C-Large が両方落ちて結局 100pt 4217 位でした。落ちる前は 3 桁 rank だったので終了後スコア見たときには D-Large 解いた人そんないるの？と思ったりしてしまいました。C-Large は 15 桁くらいまで bruteforce したリストと照らし合わせた上だったので落ちると思っていなかったのです。が、まぁ、最終結果で確認しろってことですね(後述)。

前振り

今回も C++11 を使って書く、をコンセプトにしています。開始してから gcc version 4.8.1 20130328 (prerelease) (GCC) をダウンロードしてきて使っています。ついでにとりあえず普段は使わない 64 bit exe にしています。共通コードは以下のようなコードです。Boost も使用。Google Code Jam の規定用に URL とバージョンを明示しています。IR というのは range-base for loop 用のものです(Integer Range のイメージ)。for(auto i : IR(1, 6)) とかやると 1,2,3,4,5 でループされます。

// gcc version 4.8.1 20130328 (prerelease) (GCC) at http://www.drangon.org/mingw/
// with -std=c++11

#include <iostream>
#include <sstream>
#include <iomanip>

#include <iterator>

#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>

#include <string>

#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>

#include <tuple>
#include <initializer_list>

#include <cmath>

// Boost library can be retrieved from http://www.boost.org/
// 1.52 is used

#pragma GCC diagnostic ignored "-Wconversion"
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
#pragma GCC diagnostic warning "-Wconversion"

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;

#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)

using namespace std;

template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer  last)
{ return boost::irange(first, last); }

Problem A. Tic-Tac-Toe-Tomek

縦横斜めで各コマの数を数えて判定。Small input の時は↓のように書きましたが、

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases; cin.ignore(numeric_limits<streamsize>::max(), '\n');
 REP(casenum, cases) {
  string result;
  int num = 0;
  int counter[4+4+2][3] = { 0 };
  REP(i, 4) {
   string s;
   getline(cin, s);
   REP(j, 4) {
    if(s[j] == '.') continue;
    int t = 0;
    ++num;
    switch(s[j]) {
    case 'X': t = 0; break;
    case 'O': t = 1; break;
    case 'T': t = 2; break;
    default: assert(false);
    }
    ++counter[  i][t];
    ++counter[4+j][t];
    if(  i == j) ++counter[8][t];
    if(3-i == j) ++counter[9][t];
   }
  }
  REP(i, 10) {
   if(counter[i][0] + counter[i][2] == 4) result = "X won";
   if(counter[i][1] + counter[i][2] == 4) result = "O won";
  }
  if(!result.size()) {
   if(num == 16) result = "Draw";
   else result = "Game has not completed";
  }
  cin.ignore(numeric_limits<streamsize>::max(), '\n');
  cout << "Case #" << casenum+1 << ": " << result << endl;
 }

 return 0;
}

「C++11で書いてないじゃないですかー」ということから一部修正して large input を submit

map<char, int> table = { {'X', 0 }, {'O', 1 }, {'T', 2 } };
// 略
    int t = table[s[j]]; // swtich のところを置き換え

書くだけならこうも書けますが

    int t = map<char, int>{ {'X', 0 }, {'O', 1 }, {'T', 2 } }[s[j]];

毎回 map 作られるのはどうかと思ったのでやめました。

Problem B. Lawnmower

高い方のマスから縦横の高さを確定していく、というコードで1回書いて、別に縦横両方ともその高さで刈る訳じゃないじゃんということで没。実際に提出したコードは↓。縦横で最大の高さをとって(これ以上低く刈ることはできない)、各マスに対して縦横の低い方を取った結果が指定に一致するか、で判定しています。これ C++03 でも通っちゃうんじゃ？と思いましたが、right angle bracket さん(template 指定としての >> の連続)がいるので大丈夫ですね。

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases;
 REP(casenum, cases) {
  UI N, M; cin >> N >> M;
  vector<vector<int>> board(N, vector<int>(M, 0));
  vector<int> h(N, 1), v(M, 1);
  REP(i, N) {
   REP(j, M) {
    cin >> board[i][j];
    h[i] = max(h[i], board[i][j]);
    v[j] = max(v[j], board[i][j]);
   }
  }
  std::string result = "YES";
  REP(i, N) {
   REP(j, M) {
    if(board[i][j] != min(h[i], v[j])) { result = "NO"; break; }
   }
   if(result == "NO") break;
  }
  cout << "Case #" << casenum+1 << ": " << result << endl;
 }

 return 0;
}

Problem C. Fair and Square

問題のアレです。繰り上がりが発生しないケースで限定しています。abcba の二乗だと、

8	7	6	5	4	3	2	1	0
a²	2ab	2ca+b²	2ab+2bc	2a²+2b²+c²	2ab+2bc	2ca+b²	2ab	a²

abccba の二乗だと、

10	9	8	7	6	5	4	3	2	1	0
a²	2ab	2ca+b²	2bc+2ca	2ab+2bc+c²	2a²+2b²+2c²	2ab+2bc+c²	2bc+2ca	2ca+b²	2ab	a²

と、偶数桁と奇数桁で挙動が違いますが中央桁の 2a²+2b²+2c² あるいは 2a²+2b²+c² が一番効いてきます。結局ほとんど 0 と 1 場合によっては 2 もありうるという感じになります。これをパターン分けして数え上げて最初にリストを作ってしまう、というコードが↓です。

vector<string> fair = { "1", "4", "9", "121", "484" };

struct numeric_less
{
 bool operator()(const string &s1, const string &s2) const {
  return s1.size() < s2.size() ||
   (s1.size() == s2.size() && s1 < s2);
 }
};

void mygenerate(int len, const vector<pair<int,int>> &indices)
{
 bool valid = true;
 vector<int> v(len);
 for(auto &val : indices) {
  v[val.first * 2] += val.second * val.second;
  if(v[val.first * 2] > 9) { valid = false; break; }
 }
 REP(i, indices.size()) {
  for(auto j : IR<UI>(i+1, indices.size())) {
   v[indices[i].first+indices[j].first] += 2 * indices[i].second * indices[j].second;
   if(v[indices[i].first+indices[j].first] > 9) { valid = false; break; }
  }
  if(!valid) break;
 }
 if(valid) {
  string s;
  for(auto &val : v) {
   s.push_back(val+'0');
  }
  fair.push_back(s);
 }
}

void init_fair(size_t max_len)
{
 const UI N = (max_len + 1) / 2 + 1;
 REP(i_, N) {
  int i = i_ + 1; // 1 -> (max_len + 1) / 2
  if(i < 3) continue;
  if(i & 1) { // odd
   // 1xx0xx1 x can have 1 at most 6 positions
   //   1.0.1
   //   1.1.0.1.1
   //   1.1.1.0.1.1.1
   //   1.1.1.1.0.1.1.1.1
   // 1xx1xx1 x can have 1 at most 6 positions
   //   1.1.1
   //   1.1.1.1.1
   //   1.1.1.1.1.1.1
   //   1.1.1.1.1.1.1.1.1
   // 1xx2xx1 x can have 1 at most 2 positions
   //   1.2.1
   //   1.1.2.1.1
   // 2.2
   // 2.1.2

   const int X = (i - 1) / 2;
   // 2.2
   mygenerate(2*i-1, { {0,2}, {2*X,2} });
   // 1.0.1
   mygenerate(2*i-1, { {0,1}, {X,0}, {2*X,1} });
   // 1.1.1
   mygenerate(2*i-1, { {0,1}, {X,1}, {2*X,1} });
   // 1.2.1
   mygenerate(2*i-1, { {0,1}, {X,2}, {2*X,1} });
   // 2.1.2
   mygenerate(2*i-1, { {0,2}, {X,1}, {2*X,2} });

   for(auto ii : IR(1, X)) {
   // 1.1.0.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {X,0}, {2*X-ii,1}, {2*X,1} });
   // 1.1.1.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {X,1}, {2*X-ii,1}, {2*X,1} });
   // 1.1.2.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {X,2}, {2*X-ii,1}, {2*X,1} });
   }

   for(auto ii : IR(1, X)) {
    for(auto jj : IR(ii+1, X)) {
   // 1.1.1.0.1.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {X,0}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
   // 1.1.1.1.1.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {X,1}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
    }
   }

   for(auto ii : IR(1, X)) {
    for(auto jj : IR(ii+1, X)) {
     for(auto kk : IR(jj+1, X)) {
   // 1.1.1.1.0.1.1.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {kk,1}, {X,0}, {2*X-kk,1}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
   // 1.1.1.1.1.1.1.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {kk,1}, {X,1}, {2*X-kk,1}, {2*X-jj,1}, {2*X-ii,1}, {2*X,1} });
     }
    }
   }

  } else { // even
   const int X = i  / 2;

   // 1xxxx1 x can have 1 at most 6 positions
   //   1..1
   //   1.1..1.1
   //   1.1.1..1.1.1
   //   1.1.1.1..1.1.1.1
   // 2.2

   // 1..1
   mygenerate(2*i-1, { {0,1}, {2*X-1,1} });
   // 2.2
   mygenerate(2*i-1, { {0,2}, {2*X-1,2} });

   for(auto ii : IR(1, X)) {
   // 1.1..1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {2*X-ii-1,1}, {2*X-1,1} });
   }

   for(auto ii : IR(1, X)) {
    for(auto jj : IR(ii+1, X)) {
   // 1.1.1..1.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {2*X-jj-1,1}, {2*X-ii-1,1}, {2*X-1,1} });
    }
   }

   for(auto ii : IR(1, X)) {
    for(auto jj : IR(ii+1, X)) {
     for(auto kk : IR(jj+1, X)) {
   // 1.1.1.1..1.1.1.1
    mygenerate(2*i-1, { {0,1}, {ii,1}, {jj,1}, {kk,1}, {2*X-kk-1,1}, {2*X-jj-1,1}, {2*X-ii-1,1}, {2*X-1,1} });
     }
    }
   }

  }
 }
 sort(RNG(fair), numeric_less());
#if 0
 for(auto & val : fair) {
  cout << val << endl;
 }
#endif
}

UI solve(const pair<string, string> &iv)
{
 auto it1 = lower_bound(RNG(fair), iv.first, numeric_less());
 auto it2 = lower_bound(RNG(fair), iv.second, numeric_less());
 UI result = it2 - it1;
 if(it2 != fair.end() && *it2 == iv.second) ++result;
 return result;
}

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases;
 size_t max_len = 0;
 vector<pair<string,string>> iv(cases);
 for(auto & val : iv) {
  cin >> val.first >> val.second;
  max_len = max({max_len, val.first.size(), val.second.size()});
 }
 init_fair(max_len);
 for(auto & val : iv) {
  cout << "Case #" << &val - iv.data() + 1 << ": " << solve(val) << endl;
 }

 return 0;
}

で、どこでミスったかというと

 sort(RNG(fair), numeric_less());
#if 0
 for(auto & val : fair) {
  cout << val << endl;
 }
#endif

が、こうなってました。

#if 0
 sort(RNG(fair), numeric_less());
 for(auto & val : fair) {
  cout << val << endl;
 }
#endif

ああああああああ。まぁ Qualification Round なので通ったからいいんですが。不用意な修正には気をつけろってことですね。

Problem D. Treasure

lexicographically smallest とか言われているのでこりゃ探索するしかないなってんで、どの chest を開いたかによって鍵の数も決まるので探索済みだったら枝刈りする形のコードが↓。これでも small input は通ります。あ、#include <boost/dynamic_bitset.hpp> の追加が必要です。

deque<int> solve(const vector<int> &required, const vector<vector<int>> &got, set<dynamic_bitset<>> &visited, dynamic_bitset<>& open, vector<int> & keys)
{
 if(visited.count(open)) return {};
 if(open.count() == required.size()) return { -1 };
//cerr << "OPENED_COUNT: " << open.count() << endl;
 REP(i, required.size()) {
  if(!open[i] && keys[required[i]] > 0) {
//cerr << "OPEN: " << i << endl;
   open.set(i);
   --keys[required[i]];
   REP(j, got[i].size()) {
    ++keys[got[i][j]];
   }
   auto t = solve(required, got, visited, open, keys);
   if(t.size()) {
    if(t.back() == -1) {
     t.back() = i+1;
    } else t.push_front(i+1);
    return t;
   }
   REP(j, got[i].size()) {
    --keys[got[i][j]];
   }
   ++keys[required[i]];
   open.reset(i);
  }
 }
 visited.insert(open);
 return {};
}

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases;
 REP(casenum, cases) {
  UI K, N; cin >> K >> N;
  vector<int> keys(200);
  REP(i, K) { UI t; cin >> t; ++keys[t-1]; }
  vector<int> required(N);
  vector<vector<int>> got;
  REP(i, N) {
   cin >> required[i]; --required[i];
   UI t; cin >> t;
   vector<int> got_(t);
   for(auto &val : got_) {
    cin >> val; --val;
   }
   got.push_back(got_);
  }

  dynamic_bitset<> open(N);
  set<dynamic_bitset<>> visited;
  cout << "Case #" << casenum+1 << ":";
  auto result = solve(required, got, visited, open, keys);
  if(result.size()) {
   for(auto &val: result) {
    cout << ' ' << val;
   }
  } else {
   cout << " IMPOSSIBLE";
  }
  cout << endl;
 }

 return 0;
}

IMPOSSIBLE に対する時間がかかりすぎるので、鍵の数が足りない場合と相互(3つ以上含む)に持ち合っている場合を除外「しよう」としたのが↓コードです(※通りません)。@tanakh さん曰く

D-largeは、何とかがんばれば、鍵開けが可能かどうかだけは線形時間で判定できるので、あとは前から順番に埋めていけば、Lexico最小の解が求まります。
— Hideyuki Tanakaさん (@tanakh) 2013年4月14日

D問題、線形での判定は、グラフの連結性と、あとは鍵の数があってるかだけ確かめればおｋです。
— Hideyuki Tanakaさん (@tanakh) 2013年4月14日

ということで、連結してないケース＝相互に持ち合ってるケースのイメージなので方針としては間違って無かったようです。手書きメモ上ではグラフみたいなもの書いてたのに(時間もあるのに)適当実装してしまったのが駄目なところですね。

deque<int> solve(const vector<int> &required, const vector<vector<int>> &got, set<dynamic_bitset<>> &visited, dynamic_bitset<>& open, vector<int> & keys)
{
 if(visited.count(open)) return {};
 if(open.count() == required.size()) return { -1 };
//cerr << "OPENED_COUNT: " << open.count() << endl;
 REP(i, required.size()) {
  if(!open[i] && keys[required[i]] > 0) {
//cerr << "OPEN: " << i << endl;
   open.set(i);
   --keys[required[i]];
   REP(j, got[i].size()) {
    ++keys[got[i][j]];
   }
   auto t = solve(required, got, visited, open, keys);
   if(t.size()) {
    if(t.back() == -1) {
     t.back() = i+1;
    } else t.push_front(i+1);
    return t;
   }
   REP(j, got[i].size()) {
    --keys[got[i][j]];
   }
   ++keys[required[i]];
   open.reset(i);
  }
 }
 visited.insert(open);
 return {};
}

bool sanity_check(const vector<int> &required, const vector<vector<int>> &got, const vector<int> &keys_orig)
{
 vector<int> req(200);
 REP(i, required.size()) {
  ++req[required[i]];
 }
 bool flag = false;
 REP(i, required.size()) {
  vector<int> keys(keys_orig);
  REP(j, required.size()) {
   if(i != j) {
    REP(k, got[j].size()) {
     ++keys[got[j][k]];
    }
   }
  }
  bool flag_one = true;
  REP(j, keys.size()) {
   if(req[j] > keys[j]) {
    flag_one = false;
    break;
   }
  }
  if(flag_one) {
   flag = true;
   break;
  }
 }
 return flag;
}

bool sanity_check2(const vector<int> &required, const vector<vector<int>> &got, const vector<int> &keys)
{
 stack<int> q;
 dynamic_bitset<> pushed(200);
 dynamic_bitset<> open(required.size());
 REP(i, keys.size()) { if(keys[i] && !pushed[i]) { pushed.set(i); q.push(i); } }
 while(!q.empty()) {
  int n = q.top(); q.pop();
  REP(i, required.size()) {
   if(required[i] == n && !open[i]) {
    open.set(i);
    for(auto j : got[i]) {
     if(!pushed[j]) { pushed.set(j); q.push(j); }
    }
   }
  }
 }
 return open.count() == required.size();
}

int main(void)
{
 ios_base::sync_with_stdio(false);

 UI cases; cin >> cases;
 REP(casenum, cases) {
  UI K, N; cin >> K >> N;
  vector<int> keys(200);
  REP(i, K) { UI t; cin >> t; ++keys[t-1]; }
  vector<int> required(N);
  vector<vector<int>> got;
  REP(i, N) {
   cin >> required[i]; --required[i];
   UI t; cin >> t;
   vector<int> got_(t);
   for(auto &val : got_) {
    cin >> val; --val;
   }
   got.push_back(got_);
  }

  dynamic_bitset<> open(N);
  set<dynamic_bitset<>> visited;
  cout << "Case #" << casenum+1 << ":";
  if(sanity_check(required, got, keys) && sanity_check2(required, got, keys)) {
   auto result = solve(required, got, visited, open, keys);
   if(result.size()) {
    for(auto &val: result) {
     cout << ' ' << val;
    }
   } else {
    cout << " IMPOSSIBLE";
   }
  } else {
   cout << " IMPOSSIBLE";
  }
  cout << endl;
 }

 return 0;
}

総評

C-Large はせっかく合ってたのに感はありますが通過できればいいんです、うん。とにかく楽しかったです。Round 1A も頑張るぞ。

「や」の字

2013年4月14日日曜日

Google Code Jam 2013 Qualification Round

結果

前振り

Problem A. Tic-Tac-Toe-Tomek

Problem B. Lawnmower

Problem C. Fair and Square

Problem D. Treasure

総評

0 件のコメント:

コメントを投稿