pocarist

//5578864439
//ENV: F#
//POINT: 未使用の文字から何種類できるかについてメモ化再帰で全探索。メモのポイントは種類を無視して個数の組み合わせをキーにする。また、答えは32bitで桁あふれするので注意。
//感想: 久しぶりの出題で楽しかったです。最初全部メモしてどうにも遅かったので回答をあきらめそうになりましたが純粋な再帰関数を作って呼ばれるパラメーターのダンプをみていたらメモする方法を思いつきました。ただの数え上げでは２時間くらいかかったけど、メモ化したら１秒以下になりました。

let solve gems target =
    let gems = List.ofSeq gems in
    let target = List.ofSeq target in
    let target_rev = target |> List.rev in
    let memo = ref Map.empty in

pocarist

(* POINT: 選べるチケットの中で帰国日が最も早いものを選ぶことを繰り返す。Greedy。
アリ本P.43と同じ問題。 *)

(* OCaml *)
let try_fx f x =
  try Some (f x) with
  | _ -> None

let () =
  (* 日付の比較は単に(month, day)のペアとする *)

pocarist

#include <condition_variable>
#include <mutex>
#include <queue>

template <typename T>
class blockingqueue {
public:
	blockingqueue() {}
	void enqueue(const T& item) {
		std::lock_guard<std::mutex> lk(lk_);

pocarist

--- ocaml-4.02.1/asmrun/signals_osdep.h	2014-09-29 04:46:24.000000000 +0900
+++ ocaml-4.02.1_fix/asmrun/signals_osdep.h	2014-10-05 15:22:24.000000000 +0900
@@ -163,14 +172,24 @@
 
 #elif defined(TARGET_i386) && defined(SYS_bsd_elf)
 
- #define DECLARE_SIGNAL_HANDLER(name) \
- static void name(int sig, siginfo_t * info, struct sigcontext * context)
+ #if defined (__NetBSD__)
+  #include <ucontext.h>

pocarist

// http://www.prefield.com/algorithm/container/fenwick_tree.html
// add(k, a) == v[k] = v[k] + a
// sum(i, j) == v[i] + ... + v[j] (両端を含む)
type FenwickTree(N : int) =
    let zero = LanguagePrimitives.GenericZero
    let x = Array.create N zero
    member me.sum i j =
        if i = 0 then
            let rec loop acc k =
                if k >= 0 then loop (acc + x.[k]) ((k &&& (k+1)) - 1)

pocarist

// sample of has_mem_xxx.
// this can be compiled with MS VC2012.

#include <iostream>
#include <utility>
#include <type_traits>

template< typename T >
struct has_mem_xxx {
    template< typename U > static std::true_type check( decltype( std::declval<U>().xxx )* );

pocarist

module Heap =
    type tree<'T> = Node of 'T * tree<'T> * tree<'T>
                    | Leaf
    type t<'T> = { root : tree<'T>
                   cmp : 'T -> 'T -> bool
                }
    let create cmp =
        {root=Leaf; cmp=cmp}

    let rec meld cmp a b =

pocarist

#include <vector>
#include <cmath>
using namespace std;

vector<int> primes(int n)
{
	vector<bool> table(n + 1, true);
	table[0] = table[1] = false;
	int mid = (int)floor(sqrt(n));
	for (int i = 2; i <= mid; i++) {

pocarist

open System

let memo_rec f =
  let m = ref Map.empty in
  let rec g x =
    match Map.tryFind x !m with
    | Some ans -> ans
    | None ->
        let y = f g x in
        m := Map.add x y !m

pocarist

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

module type S =
sig
  type elt
  type t
  val empty: t