2013-08-13

アルゴリズム概要

inputs[:512] <- [規定入力, 乱数*300]
outputs[] <- eval inputs
探索範囲[:1000くらい] <- `親ソルバー < サイズとoperator`

loop:
  if children.size < CPUの2倍:
    child <- `子ソルバー -t 探索範囲.pop < (inputs, outputs)`
    children.push(child)

  child.onFinish:
    if 出力なし:
      goto loop
    else:
      program <- 出力
      探索範囲.push(all 探索中)
      killall children
      status, 反例 <- guess program
      if status == 'win':
        print program
        探索終了
      if status == 'mismatch':
        inputs.append(反例), outputs.append(反例)
      goto loop

という風にやってました。自然言語より似非コードの方が伝わるんで書きなおしてみた。

この辺の作業は時系列順に言うと

@tzik さんが細かい単位で書いていた。
手作業が面倒だったので全体を繋げた。
@tzik さんが並列化。

という感じに進んでて、よく見ると Python 知識が必要なところは @tzik さんがガシガシ書いてくれました。

2013-08-13

ICFP Contest 2013

ICFP Contest 2013 に参加してました。oyososan チームの一員として @nodchip @tzik_tack (以後 @tzik と略) @ysks と一緒に。
コアな部分は @nodchip さんが書いてるので、他の部分を。

2013-01-30

Find the Min

問題

数列の内、頭の k 項が知らされている。残りについては、"直前 k 項に現れない、最小の非負整数"という条件もわかっている。この時数列の最後 n 項目は何か。

考え方

初項 k 項については乱数だけど 10^9 まである掛け算だから 64bit 使おう
未知部分については、とりあえず k+1 より大きい数が現れるはずはない
むしろ k+1 周期でループするんじゃん。
まずは m[0..k] を計算しておこう。
[k] だけは疑似乱数の枠じゃないから別計算だな。
m[k+1..2k+1] を求められれば m[(n-1)%(k+1)] が答えじゃん。
使える／使えない数のリストを持たないとなー。
使える数は最小が云々だからsetで、使えないのは配列/vectorでいいか。

コード

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long int64;

void PseudoRand(const int n, vector<int>* data) {
  int64 a, b, c, r;
  cin >> a >> b >> c >> r;
  for (int64 i = 0; i < n; ++i) {
    (*data)[i] = static_cast<int>(a);
    a = (b * a + c) % r;
  }
}

int64 Solve() {
  int n, k;
  cin >> n >> k;

  // Input and generate
  vector<int> data(k + 1);
  PseudoRand(k, &data);

  // Set up
  vector<int> used(k + 1, 0);
  for (int i = 0; i < k; ++i) {
    const int d = data[i];
    if (d <= k + 1)
      ++used[d];
  }
  set<int> usable;
  for (int i = 0; i <= k; ++i) {
    if (used[i] == 0)
      usable.insert(i);
  }

  // Set m[k]
  {
    set<int>::iterator itr = usable.begin();
    data[k] = *itr;
    ++used[*itr];
    usable.erase(itr);
  }

  // Make m[(k+1) .. 2*(k+1)-1]
  for (int i = 0; i <= k; ++i) {
    const int d = data[i];
    if (d <= k + 1 && used[d] > 0) {
      --used[d];
      if (used[d] == 0)
	usable.insert(d);
    }

    set<int>::iterator itr = usable.begin();
    data[i] = *itr;
    usable.erase(itr);
  }

  return data[(n - 1) % (k + 1)];
}


int main(void) {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": " << Solve() << "\n";
  }
}

2013-01-30

Balanced Smileys

問題

:) やら :( やらが含まれる文字列で、カッコの対応が付いているかチェックせよ。

考え方

考慮すべきカッコに種類があるわけではない。
Smiley が関係無い場合、カッコを潜っている段数 n を見るだけでいいテンプレ問題が有るのを思い出す。
- 途中は n>=0 をキープし、最後に n==0 となれば OK
カッコの前に : があったら Smiley になる可能性があるから分岐させればいい。
こんなときは DP すると良さ気。
最初のカッコの時だけ : チェックしない例外とか面倒だからスペース入れておこ…

コード

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <set>
#include <string>
using namespace std;

bool Solve() {
  string line;
  getline(cin, line);
  line = ' ' + line;
  set<int> a, b;
  set<int>* st = &a, * st2 = &b;
  st->insert(0);
  for (int i = 0; i < line.size(); ++i) {
    if (line[i] != '(' && line[i] != ')')
      continue;
    st2->clear();
    set<int>::iterator itr;
    if (line[i] == '(') {
      for (itr = st->begin(); itr != st->end(); ++itr)
	st2->insert(*itr + 1);
      if (line[i - 1] == ':')
	for (itr = st->begin(); itr != st->end(); ++itr)
	  st2->insert(*itr);
    } else if (line[i] == ')') {
      for (itr = st->begin(); itr != st->end(); ++itr)
	if (*itr > 0)
	  st2->insert((*itr) - 1);
      if (line[i - 1] == ':')
	for (itr = st->begin(); itr != st->end(); ++itr)
	  st2->insert(*itr);
    }
    swap(st, st2);
  }

  return (st->find(0) != st->end());
}

int main(void) {
  string line;
  getline(cin, line);
  const int n = atoi(line.c_str());
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": "
	 << (Solve() ? "YES\n" : "NO\n");
  }
  return 0;
}

2013-01-30

Beautiful String

問題概要

アルファベットに1〜26の点数が付いている。与えられた文字列が最高得点になる時の得点を計算せよ。

考え方

多い文字に高い得点付ければいいんじゃない？
文字数カウントして個数をソートすれば大丈夫っぽい。

コード

#include <algorithm>
#include <cctype>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int Solve() {
  string s;
  vector<int> count(26, 0);
  getline(cin, s);
  for (int i = 0; i < s.size(); ++i) {
    if (!isalpha(s[i])) continue;
    ++count[tolower(s[i]) - 'a'];
  }
  sort(count.begin(), count.end());
  
  int cost = 0;
  for (int i = 0; i < 26; ++i) {
    cost += (i + 1) * count[i];
  }
  return cost;
}

int main(void) {
  string n_str;
  getline(cin, n_str);
  int n = atoi(n_str.c_str());
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": " << Solve() << "\n";
  }
  return 0;
}

2013-01-30

Facebook Hacker Cup 2013 Qualification Round

https://www.facebook.com/hackercup/scoreboard?round=185564241586420

2012-08-10

Round 2

ICFPC

ICFP Programming Contest 2012 | Official Site で第 2 ラウンドの結果が公表されました。Lightning の方では Round 1 の 10 位以内に続き、今回も 5 位以内に入ることができたようです。
一方の Main では Round 1 の 53 位からグッと上がって 11 位になりました。
両方とも、手元 PC で追実験した時の結果を書いておきます。

Main

括弧内は公式で発表されている点数です。

full1  1157  (1157)
full2  1571  (1562)
full3  1669  (1703)
full4  2059  (1949)
full5  4620  (1204)
full6  2603  (2578)
full7   664  ( 660)
full8  2322  (2322)
full9  3477  (3477)
full10 4444  (3219)
合計  22586 (19831)

随分違っているので Lightning の結果は心配です。

Lightning

あくまで最終版を使っての手元実験なので参考程度に。

lightning1   212
lightning2   275
lightning3  1177
lightning4  1005
lightning5  1157
lightning6  2677
lightning7  2679
lightning8  4788
lightning9  2448
lightning10 3254
合計       19672

6 位以下の成績と比べると Map7 の成績が異様に良くて、Map10 の成績が振るわない感じ。