#include <iostream>
#include <utility>

// 再帰処理を使用して、T型の変数にN個のポインタを付与するメタ関数

template <int N> struct int_ {};
template <bool cond> struct bool_ {};

// tag despatch
struct cont {}; // continue
struct end {}; // end

template < bool Cond >
auto is_end (bool_<Cond>)
-> typename std::conditional<Cond, end, cont>::type;

template < class T, int N >
auto add_pointers_impl( T, int_<N>, cont )
-> decltype(
  add_pointers_impl(
    std::declval<T*>(),
    int_<N - 1>(),
    std::declval<
    decltype(
      is_end( bool_<N - 1 == 0>() 
      )
    )>()
  )
);

template < class T, int N >
auto add_pointers_impl( T, int_<N>, end )
-> T;

template < class T, int N >
auto add_pointers( T, int_<N> )
-> decltype(
  add_pointers_impl (
    std::declval<T>(),
    int_<N>(),
    std::declval<
    decltype(
      is_end( bool_<N == 0>() )
    )
  >()
  )
);

template < class T, int N >
using pow_pointer = decltype(
  add_pointers(
    std::declval<T>(),
    int_<N>()
  )
);

int main() {
  int* p;
  pow_pointer< int, 2 > dp = &p;
}

解説

pow_pointer に型と付加したいポインタの数を指定するとそれに対応した型が返ってきます。

pow_pointerが最初に呼び出しているのは add_pointers という関数になります。
この関数には具体的な実装がありませんが、この関数を decltype で評価することによって返り値の型を得ることができるようになります。したがって、テンプレートメタプログラミングの文脈で使用するにかぎっては実装はいりません。

add_pointers は処理を add_pointer_impl に委譲します。
処理を委譲する際、型の後置宣言を使用しています。
これは参考書によると、複雑な型宣言をするから、らしい。

add_pointer_impl は引数を３つ取るので、add_pointers の返り値にも３つの引数を与える必要があります。
この３つの引数は、ポインタを付与したい型情報、再帰する回数(N)と再帰条件に使用するタグの情報です。

再帰では、再帰終了条件を付ける必要があります。これがないと永遠に関数が呼び出され続けて、スタックオーバーフローを引き起こします。
ここでは、第3引数に空の構造体の名前を入れることで条件を区別しています。また、このように構造体の名前を使用して処理を分岐することをタグディスパッチといいます。
add_pointer_impl では第3引数が cont なら続ける、 end なら型を返して終了です。

もっと詳しく、返り値の宣言を見てみます。

 decltype(
  add_pointers_impl (
    std::declval<T>(),
    int_<N>(),
    std::declval<
    decltype(
      is_end( bool_<N == 0>() )
    )
  >()
  )
);

decltype を使用して add_pointers_impl の型情報を抜き出す形です。
この際、型Ｔのインスタンスを作るために std::declval<T>() という関数を使用しています。
これは型Ｔにデフォルトコンストラクタが存在しなくても型情報を渡せるようにするために存在します。(中では T&& を返しているようですがあんまりよくわかってない。)

また、再帰条件の判定には is_end(bool_<T>()) が渡されています。
この実装は以下のようになります。

template < bool Cond >
auto is_end (bool_<Cond>)
-> typename std::conditional<Cond, end, cont>::type;

最初に宣言した bool_ を使用して真理値を渡し、true ならは end, falseならばcont を返します。
その際、std::conditionalを使用しています。

このように N が 0 になると、最後に

template < class T, int N >
auto add_pointers_impl( T, int_<N>, end )
-> T;

型情報が返され、結果的に T******... が手に入ります。

まとめ

decltypeとdeclvalを使用して型を操作するメタ関数を簡単に作れる。
終了条件の判定には、タグディスパッチを使ったメタ関数のオーバーロードが使える。

2019-06-07

make_vectorを自作する

std::vector<std::vector<std::vector<int>>> vec; みたいに型の中に何十も std::vector を書くのが死ぬほど面倒臭い。ということで std::make_tuple のように型を指定して std::vector を返す関数を作りました。

make_vector

template <class Thead>
constexpr auto make_vector(Thead head)
{
  return std::vector<Thead>();
}

template <class THead, class ...Args>
constexpr auto make_vector(THead head, Args... tail) 
{
  return std::vector<decltype(make_vector(tail...))>();
}

次のように使います。

int main(){
  auto vec1 = slc::make_vector(1, 2); // vector<vector<int>>
  auto vec2 = slc::make_vector(1, '1'); // vector<vector<char>>
  int n = 3;
  auto v = slc::make_vector(1);
  for (int i = 0; i < n; ++i) {
    v.push_back(i);
  }

  vec1.push_back(v);

  for (int i = 0; i < n; ++i) {
    std::cout << vec1[0][i] << "\n";
  }
}

簡単な解説

make_vector は引数で指定してパラメータ分だけ次元を持つ std::vector を返します。
また、std::vector は最後に指定した型を持つベクトルになります。
つまり、引数自体には意味がありません。

今後の課題

引数で指定したぶんの領域を確保できるようにする
理想なのは make_vector<char>(10, 20, 30) // vector<vector<vector<char>>>(10, 20, 30) のように型引数を1つ取り、引数をあらかじめ確保したい要素数を指定できるようにすること。ただし、関数テンプレートは引数から型を推論できてしまうのと、どうやって型1つで可変長引数をとるのかがわからない。

今回のソース

github.com

いろいろ使えればいいな

2019-05-30

パラメータパックを使ってModInt構造体を自作してみる

既出だったらすみません。
C++のパラメータパックという機能を使って任意の引数を取ることができるModInt構造体を自作してみました。

ModIntとは

競技プログラミングでは解を $10^{9} + 7$ で割った余りを答えさせる問題が頻出です。
ただ、繰り返しModを取るとソースコードが剰余計算の嵐になりバグを埋め込んでしまう原因にもなり得ます。

noshi91.hatenablog.com

その問題を軽減するために、こちらの記事でnoshi91さんがModInt構造体というものを紹介しています。

本記事ではこれを少し拡張して、複数の入力に対応した add, sub, mul 関数を含む ModCalcBase クラスとこのクラスを継承し、実際に値を持つ ModCalc クラスを製作したので紹介します。

ModCalcBase クラス

class ModCalcBase 
{
  using mod_type = long long;
  static constexpr mod_type M = 1000000007;
public:
  template <class Reference, class Body>
  static void add(Reference& lval, Body body) noexcept
  {
    lval += (Reference)body % M;
    lval %= M;
  }

  template <class Reference, class Thead, class ...Args>
  static void add(Reference& lval, Thead head, Args... body) noexcept
  {
    lval += (Reference)head % M;
    lval %= M;
    add(lval, body...);
  }

  template <class Reference, class Body>
  static void mul(Reference& lval, Body body) noexcept
  {
    lval *= (Reference)body % M;
    lval %= M;
  }

  template <class Reference, class Thead, class ...Args>
  static void mul(Reference& lval, Thead head, Args... body) noexcept
  {
    lval *= (Reference)head % M;
    lval %= M;
    mul(lval, body...);
  }

  // 返り値が負数になってはいけない
  template <class Reference, class Body>
  static void sub(Reference& lval, Body body) noexcept
  {
    lval -= (Reference)body % M;
    lval += M;
    lval %= M;
  }

  template <class Reference, class Thead, class ...Args>
  static void sub(Reference& lval, Thead head, Args... body) noexcept
  {
    lval -= (Reference)head % M;
    lval += M;
    lval %= M;
    sub(lval, body...);
  }
};

パラメータパックを使用して複数の引数を受け取れるようにしています。
この関数群は, ModCalcBase::add(1, 2, 3, ...) のように使えます。
一応、オーバーフローを防ぐために Referenceで全ての引数をキャストしてます。

使用例

#include <iostream>
using std::cout;
using std::endl;

int main() {
  long long a, b, c, d;
  a = 1, b = 2, c = 3, d = 4;
  ModCalcBase::add(a, b, c, d);
  cout << a << endl; // 10
  ModCalcBase::sub(a, b, c);
  cout << a << endl; // 5
  ModCalcBase::mul(a, b);
  cout << a << endl; // 10

  a = 1000000006, b = 2;
  ModCalcBase::add(a, b);
  cout << a << endl; // 1
  a = 4000000010, b = 1000000006, c = 2000000000;
  ModCalcBase::sub(a, c, b);
  cout << a << endl; // 1000000004
  a = 1000000006, b = 2;
  ModCalcBase::mul(a, b);
  cout << a << endl; // 1000000005
}

ModCalcクラス

class ModCalc : public ModCalcBase 
{
  using value_type = long long;
  using reference = value_type&;
public:
  value_type value;
  
  ModCalc(value_type value = 0)
    : value(value) {}

  // 値の変更はメソッドを使って欲しい。。。
  const value_type&
  operator ()() const
  {
    return value;
  }

  value_type
  operator +(const ModCalc& rhs) const noexcept
  {
    value_type tmp = value;
    add(tmp, rhs.value);
    return tmp;
  }

  value_type
  operator -(const ModCalc& rhs) const noexcept
  {
    value_type tmp = value;
    sub(tmp, rhs.value);
    return tmp;
  }

  value_type 
  operator *(const ModCalc& rhs) const noexcept
  {
    value_type tmp = value;
    mul(tmp, rhs.value);
    return tmp;
  }
    
  ModCalc&
  operator +=(const ModCalc& rhs) noexcept
  {
    add(value, rhs.value);
    return *this;
  }

  ModCalc&
  operator -=(const ModCalc& rhs) noexcept
  {
    sub(value, rhs.value);
    return *this;
  }

  ModCalc&
  operator *=(const ModCalc& rhs) noexcept
  {
    mul(value, rhs.value);
    return *this;
  }

  friend std::ostream& operator <<(std::ostream& os, const ModCalc& rhs);
};

std::ostream& operator <<(std::ostream& os, const ModCalc& rhs)
{
  os << rhs();
  return os;
}

ModCalcBaseを継承した実際に値を持っているクラスです。
計算の方を使ってもいいし、こちらで値を持ってもいいなあと思って分離。

使用例

int main() {
  long long a,b,c,d;
  a = 1, b = 2, c = 3, d = 4;

  ModCalc ins1(a), ins2(b), ins3(c);
  cout << ins1 + ins2 << endl; // 3
  cout << ins2 - ins1 << endl; // 1
  cout << ins2 * ins1 << endl; // 2

  ins1 += ins2;
  cout << ins1 << endl; // 3
  ins1 -= ins2;
  cout << ins1 << endl; // 1
  ins1 *= ins3;
  cout << ins3 << endl; // 3
}

operator +, -, *, +=, -=, *= に対応しています。

また、operator <<もオーバロードしているので cout << で出力可能です。

AtCoderでの使用例

atcoder.jp

こんな感じで使えます。

コードはこちら

github.com

2019-05-28

Macで実行ファイルのヘッダのマジックナンバーをVSCode拡張機能を使って見るまで

タイトル通り。
プログラムの実行フォーマットについてあまりに無知すぎたので備忘録です。

実行ファイルフォーマット

Wikipediaによると、

実行ファイル（じっこうファイル、Executable、Executable file）とは、コンピュータがプログラムとして解釈実行できるファイルである。実行可能ファイル、実行形式ファイル、あるいは単に実行形式とも呼ばれる。

ということらしいです。

具体的な例として、ELFフォーマットやa.outがあります。

特にELFはLinuxなどで採用されており、広く普及しているファイルフォーマットです。

実行ファイルは多くの場合、ファイルフォーマットを識別するためのマジックナンバーやCPUの種類、アーキテクチャなどを含むヘッダから始まります。

Mach-O

多くのOSで実行ファイル形式として採用されているELFですが、Macの場合はMach-Oという形式で保存されます。

Mach-Oのヘッダは, /usr/include/mach-o/loader.h に定義されている C の構造体が付与されます。

以下、loader.h。

struct mach_header_64 {
    uint32_t   magic;      /* mach magic number identifier */
    cpu_type_t  cputype;    /* cpu specifier */
    cpu_subtype_t   cpusubtype; /* machine specifier */
    uint32_t   filetype;   /* type of file */
    uint32_t   ncmds;      /* number of load commands */
    uint32_t   sizeofcmds; /* the size of all the load commands */
    uint32_t   flags;      /* flags */
    uint32_t   reserved;   /* reserved */
};

先頭 4byte にマジックナンバー、それ以降はcpuのタイプ、fileのタイプと続きます。

また、マジックナンバーは

/* Constant for the magic field of the mach_header_64 (64-bit architectures) */
#define MH_MAGIC_64 0xfeedfacf /* the 64-bit mach magic number */

と定義されています。

すなわち、実行ファイルを生成するとリトルエンディアンで先頭から CF FA ED FE と格納されるはずです。

実際に簡単な C のプログラムを使って確認してみます。

#include <stdio.h>
int main() {
  printf("Hello world\n");
}

これをコンパイルすると、実行時に Hello world と表示される実行ファイル a.out が生成されます。

実行ファイルは 0, 1 から成るバイナリデータです。

これからこのバイナリを読みマジックナンバーを確認するわけですが、普通のエディタではバイナリは読めません。

ということで VSCode の拡張機能 hexdump for VSCode を使用してみます。

詳しい説明は紹介する記事に譲りますが、 VSCode 上でバイナリを hexdump した結果を出してくれる優れものです。

tarukosu.hatenablog.com

ということで Hexdump for VSCode で実行ファイルを表示した結果がこちら。

f:id:ryo_seriru:20190528231105p:plain

先頭4byteは... CF FA ED FE ということで、マジックナンバーが確認出来ました。

まとめ

実行ファイルのファイルフォーマットには ELFやa.out, Mach-Oなどがある。
実行ファイルの先頭には様々な情報が詰まったヘッダがあり、ファイルフォーマットを区別するマジックナンバーが付いている。
Mach-Oのマジックナンバーは CF FA ED FE。
バイナリを読むには hexdump for VSCode が非常に便利。

セグメントとかリンカとか知らないことが多すぎる

2019-05-12

diverta 2019 Programming Contest B RGB Boxes

問題

atcoder.jp

問題概要

$Rr + Gg + Bb = N$ となる $(r, g, b)$ の組の総数を求めよ。

考察 and 解説

$1 \leq R, G, B, N \leq 3000$ であるので、 $3$ 重ループによる全探索は間に合いません。

よって、 $2$ 重ループで $r, g$ の組を総当たりし、 $Bb = N - Rr - Gg$ となる $b$ が存在するかを調べれば良いです。

類題

abc085.contest.atcoder.jp

提出コード

#include <iostream>
using namespace std;

int main() {
  int r,g,b,n;
  cin >> r >> g >> b >> n;

  int rmax = n / r;
  ll ans = 0;
  for (int i = 0; i <= rmax; ++i) {
    int rem = n - i * r;
    int gmax = (rem / g) + 1;
    for (int j = 0; j <= gmax; ++j) {
      int remain = rem - j * g;
      if (remain >= 0 and remain % b == 0) ans += 1;
    }
  }
  cout << ans << endl;
}

2019-05-09

AtCoder Regular Contest 078 D Fennec VS Snuke

問題

atcoder.jp

問題概要

$N$ 個のマスと $N - 1$ 本の道を持つグラフがある。
Fennecは $1$ 番目、Snukeは $N$ 番目のマスからそれぞれ別の色を塗る。
先にマスに色を塗れなくなるのはどちらか。

考察 and 解説

基本的に先に塗れるマスが多い方が勝つ。

このグラフを各道のコストが $1$ の無向グラフに見立て $1$ と $N$ から、各マスへの最短コストを求める。

このとき、 $2$ 人の勝利条件は

Fennec
- 先に塗れるマスが Snuke より多い。
Snuke
- 塗れるマスが同じか、先に塗れるマスが Fennec より多い。

注意なのは先に塗れるマスが同じときで、この場合は最初にFennecが塗るマスがなくなり負けてしまう。

各マスへの最短路計算にはダイクストラ法を使うと良い。(プライオリティキューを使った実装で $O(Nlog N)$ )

提出コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
struct edge { long long to, cost;};
typedef pair<long long, long long> P_dij;

/* params
 * @s -> start, n -> 要素数, G -> グラフ, d -> 結果(参照渡し)
*/
void dijkstra(const long long s, const long long n,
  vector< vector<edge> > const &G, vector<long long> & d){
  d.resize(n);
  for(int i=0; i<n; i++) d[i] = INF; 
  priority_queue<P_dij, vector<P_dij>, greater<P_dij>> que;
  d[s] = 0;
  que.push(P_dij(0, s));
  while (!que.empty()) {
    P_dij p = que.top();
    que.pop();
    long long v = p.second;
    if(d[v] < p.first)continue;
    for(int i=0;i<G[v].size(); i++){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        que.push(P_dij(d[e.to], e.to));
      }
    }
  }
}

/* END END END */
int main() {
  int n;
  cin >> n;
  vector<vector<edge>> G(n+1);
  
  int a,b;
  rep(i, n-1) {
    cin >> a >> b;
    --a, --b;
    G[a].push_back({b, 1});
    G[b].push_back({a, 1});
  }

  vector<ll> d1, d2;
  dijkstra(0, n, G, d1);
  dijkstra(n-1, n, G, d2);

  int cntf = 0, cnts = 0;
  for (int i = 0; i < n; ++i) {
    if (d1[i] < d2[i]) cntf += 1;
    else if (d1[i] == d2[i]) cntf += 1;
    else cnts += 1;
  }

  if (cnts > cntf or cnts == cntf) {
    cout << "Snuke" << endl;
  } else {
    cout << "Fennec" << endl;
  }
}

ダイクストラ法はアルメリアさんのコードを少し改造して使っております。。。

seriruの技術屋ブログ

競技プログラミングやゲーム開発など技術に関することを発信します

AtCoder Beginer Contest 099 Good Grid

問題

考察

再帰テンプレートでN個のポインタを付けるメタ関数を作る

参考書

コード

解説

まとめ

make_vectorを自作する

make_vector

簡単な解説

今後の課題

パラメータパックを使ってModInt構造体を自作してみる

ModIntとは

ModCalcBase クラス

使用例

ModCalcクラス

使用例

Macで実行ファイルのヘッダのマジックナンバーをVSCode拡張機能を使って見るまで

実行ファイルフォーマット

Mach-O

まとめ

diverta 2019 Programming Contest B RGB Boxes

問題

問題概要

考察 and 解説

提出コード

AtCoder Regular Contest 078 D Fennec VS Snuke

問題

問題概要

考察 and 解説

提出コード