opam install z3 が "clang: error: unsupported option '-fopenmp'" で落ちる

## 解決策

ocamlc の -cc オプションで clang の代わりに gcc を指定させる.
バッドノウハウだが, ocamlc と ocamlfind を wrap する.

コマンドを理解してから使ってください

cc=`which gcc`

dir="$(dirname $(which ocamlc))"

if [ ! -e $dir/ocamlc_ -a -e $dir/ocamlc ]; then
  mv "$dir/ocamlc" "$dir/ocamlc_"
fi

if [ -e $dir/ocamlc_ ]; then
  echo "#\!/bin/sh
\`dirname \$0\`/ocamlc_ \"\$@\" -cc \"$cc\"
" > "$dir/ocamlc"
  chmod 755 "$dir/ocamlc"
fi
cc=`which gcc`

dir="$(dirname $(which ocamlfind))"

if [ ! -e $dir/ocamlfind_ -a -e $dir/ocamlfind ]; then
  mv "$dir/ocamlfind" "$dir/ocamlfind_"
fi

if [ -e $dir/ocamlfind_ ]; then
  echo "#\!/bin/sh

if [ \"\$1\" = \"ocamlc\" ]; then
  \`dirname \$0\`/ocamlfind_ \"\$@\" -cc \"$cc\"
else
  \`dirname \$0\`/ocamlfind_ \"\$@\"
fi" > "$dir/ocamlfind"
fi

Myアニメ・映画・ノベルゲームキュー

僕がいつか見るアニメ・映画・ノベルゲームキューです。
キューなので先頭(上)からしか取り出せません。
おすすめされるとキューの末尾に追加されます。

たいていのアニメは数話で切ることになると思います。
キューに入っていても構わずおすすめしてください。
全話見る確率が高くなります。

  1. 蒼穹のファフナー
  2. エヴァ
  3. 有頂天家族
  4. メイドインアビス
  5. 氷菓
  6. クロックワーク・プラネット
  7. バッカーノ!
  8. 弱虫ペダル
  9. 3月のライオン
  10. 舟を編む
  11. 食戟のソーマ
  12. ジョジョ
  13. Re: ゼロ
  14. 僕のヒーローアカデミア
  15. ちはやふる (最高)
  16. Kanon カノン
  17. リトルバスターズ
  18. Air エアー
  19. Rewrite
  20. 神のみぞ知るセカイ
  21. シャナ
  22. ゼロの使い魔
  23. 電波女と青春男
  24. 中二病でも恋がしたい!(1期だけ)
  25. かんなぎ
  26. 攻殻機動隊
  27. モブサイコ100
  28. グリザイアシリーズ(果実→楽園→劇場版)
  29. SHIROBAKO
  30. 賭ケグルイ
  31. ルパン三世 part5
  32. DOUBLE DECKER
  33. GRIDMAN
  34. ゴールデンカムイ (2期)
  35. ゴブリンスレイヤー
  36. 辺獄のシュヴェスタ(漫画)
  37. 鋼の錬金術師
  38. ハンターハンター
  39. ヴァイオレットエヴァーガーデン
  40. Island
  41. ケムリクサ
  42. ソラとウミのアイダ
  43. 廻るピングドラム
  44. 結城友奈は勇者である

Myおすすめアニメランキング

僕(drafear)が全話視聴したアニメリストです.
個人的に良かった順に並べています.
あんまりだらだらと感想書いても仕方ないので短く書いています.
一部ノベルゲームが含まれています. 特におすすめしたいものなので.

あまり合わなかったアニメも載せていますが, どれも最後まで見たものなのでそこに入っていても糞アニメと評価しているわけではありません.
また, アニメ未完結で2期期待というものは評価がかなり落ちていたりします.

このリストを見て自分と合いそうだなーと思ったらおすすめのアニメを紹介してもらえると喜びます.

おそらく自分は、

  • 主人公が賢い
  • 設定が細部までしっかりしている
  • シリアス
  • 伏線回収が綺麗
  • 伏線の張り方が上手い
  • 考えさせられる

アニメを好みます.

おすすめ

1位 新世界より

人々が神の力を手にした1000年後の日本の話.
社会はどう変化し, 秩序はどう維持されているのか.

2位 約束のネバーランド

主人公らが賢くて, 毎回驚かされます.
視聴者に与えられる情報が絶妙で, 主人公らの立場に立って考えるのが楽しいですね.
伏線・回収に関しても非常に上手くできています.

3位 STEINS; GATE, STEINS; GATE 0

他のどのアニメと比較してもダントツで強烈な伏線を叩きつけてきます.
SFモノで, あれができてこれができないといった設定をしっかりと視聴者と共有し, それを上手く活かしています.

4位 CHAOS;CHILD (原作)

僕のアイコンです.

アニメは単なるネタバレ集なのであまりおすすめしません.
CHAOS;CHILDCHAOS;HEAD の続編なので CHAOS;HEAD を見てからの方がもちろん楽しめますが見なくても十分楽しめると思います.
CHAOS;HEAD はアニメでも十分です.

普通の高校3年生が主人公で、新聞部の活動として「ニュージェネレーションの狂気の再来」の事件を追っていきます.

store.steampowered.com

続編(ラノベ)

CHAOS;CHILD -Children's Revive-

5位 fault (ゲーム, steam)

平和主義を貫いていたルゼンハイド王国が突如襲撃されるところから物語は始まります.
魔法(マナクラフト)が使える世界なんですが, その仕組み・原理をちゃんと説明してくれるので, 魔法だからなんでもできますというわけではありません.

store.steampowered.com
store.steampowered.com
store.steampowered.com

6位 PSYCHO-PASS

人の「犯罪係数」を測定できるようになった世界で, その値によって人々が裁かる社会のお話です.
主人公は裁く側の人間で, 様々な犯罪と向き合うことになります.
最初の7話くらいは導入なので我慢してください.

7位 コードギアス 反逆のルルーシュ

全世界の1/3を統べる神聖ブリタニア帝国を相手に, 1人の学生が立ち上がり戦っていく物語です.
何度も狡猾な策でピンチを切り抜けるシーンがあって驚かされます.

8位 魔法少女まどか☆マギカ

何を書いてもネタバレになるので何も書けないのですが, 壮大な設定があって劇場版まで回収が続くので, 是非劇場版まで見てほしいです.

9位 ノーゲーム・ノーライフ

ゲームで全てが決まる世界に飛ばされる主人公「 」.
最弱の種族「イマニティ」として反撃の狼煙を上げる.

毎ゲーム, 不利な状況から上手い1手を返して, 普通のアニメならそれで勝ちなんですが, このアニメは更に数手返し合うのが見どころです.

10位 ワールドトリガー

最弱の主人公が戦略を武器に戦っていきます.
他のアニメとは異なって, 集団戦をしっかりやっていて見ごたえがあります.
設定をしっかり解説するため, 導入が長く20話くらい続くがワールドトリガーの世界を理解するにつれどんどん面白くなっていくので是非見て欲しいです.

mangatari.jp

11位 CLANNAD

クラナドは人生.

12位 僕だけがいない街 (アニメ)

15位 オーバーロード (1期)

16位 キノの旅

20位 ぼくらの

25位 C - The Money of Soul and Possibility Control

26位 屍鬼

28位 青春ブタ野郎はバニーガール先輩の夢を見る

微妙

  1. 喰霊-零-
  2. RErideD
  3. 約束の七夜祭り
  4. Another
  5. ハッピーシュガーライフ
  6. ガンスリンガー ストラトス
  7. 七つの大罪
  8. 魔法少女サイト
  9. グランクレスト戦記
  10. フルメタル・パニック
  11. 無限のリヴァイアス
  12. 十二国記
  13. お前はまだグンマを知らない
  14. Ergo Proxy
  15. クジラの子らは砂上に歌う
  16. ココロコネクト
  17. Robotics;Notes
  18. キディガーランド
  19. Evil or Live
  20. あるゾンビ少女の災難
  21. B: The Beginning




dijkstraの空間計算量(メモリ使用量)をO(V)に減らす

Priority Queue を使った実装だと時間計算量 \(O(V + ElogE)\), 空間計算量 \(O(V + E)\) になると思います。

実装は重くなるのと定数が重いですが、Priority Queue の代わりに Segment Tree を使うと時間計算量 \(O(V + ElogV)\), 空間計算量 \(O(V)\) に改善できます。

これを使うと楽に解ける問題

RUPC2019 Day2 E こたつがめを燃やさないで
https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/E

全方位木DPライブラリを作った

概要

森に対して全方位木DPを行うライブラリです。
全方位森DPの方がいいんかな。
森でないときにassertが落ちるようにするためにUnionFindを使っています。
パフォーマンスが気になるなら使わないように実装しなおすと良いかもしれません。

計算量

  • construct: \(O(n)\)
  • add: \(O(1)\)
  • dp: \(O(n\alpha(n))\) (実質 \(O(n)\))

コード

using ll = long long;

class UnionFind {
  vector<ll> par, h;
public:
  UnionFind(ll size) : par(size, 0), h(size, 0) {
    for (int i = 0; i < size; ++i) {
      par[i] = i;
    }
  }
  void unite(ll u, ll v) {
    u = root(u), v = root(v);
    if (u == v) return;
    if (h[u] < h[v]) {
      par[u] = v;
    }
    else {
      par[v] = u;
    }
    if (h[u] == h[v]) ++h[u];
  }
  bool isUnited(ll u, ll v) {
    return root(u) == root(v);
  }
  ll root(ll v) {
    if (par[v] == v) return v;
    return par[v] = root(par[v]);
  }
};

template<class Calc>
class EdgeDpOnForest {
public:
  using T = typename Calc::type;
  struct Edge {
    ll to, rev;
    T value;
  };
private:
  ll n;
  void dfs1(ll v, ll pv) {
    ll idx = -1;
    vector<T> values;
    for (int i = 0; i < G[v].size(); ++i) {
      const Edge& e = G[v][i];
      if (e.to == pv) {
        idx = i;
        continue;
      }
      dfs1(e.to, v);
      values.push_back(e.value);
    }
    // 根以外では親から入る辺の値を更新
    if (idx >= 0) {
      const Edge& e = G[v][idx];
      G[e.to][e.rev].value = Calc::merge(values);
    }
  }
  void dfs2(ll v, ll pv) {
    vector<T> values;
    for (auto&& e : G[v]) values.push_back(e.value);
    values = Calc::evaluate(values);
    for (int i = 0; i < G[v].size(); ++i) {
      const Edge& e = G[v][i];
      if (e.to == pv) continue;
      G[e.to][e.rev].value = values[i];
      dfs2(e.to, v);
    }
  }
public:
  UnionFind uf;
  vector<vector<Edge>> G;
  EdgeDpOnForest(ll n) : n(n), uf(n), G(n) {}
  // 辺を追加する
  void add(ll u, ll v) {
    assert(!uf.isUnited(u, v));
    G[u].push_back({v, ll(G[v].size())});
    G[v].push_back({u, ll(G[u].size())-1});
    uf.unite(u, v);
  }
  // 各有向辺の値 G[v][i].value を計算する
  void dp() {
    vector<bool> used(n, false);
    for (int i = 0; i < n; ++i) {
      if (used[uf.root(i)]) continue;
      dfs1(i, -1);
      used[uf.root(i)] = true;
    }
    used.assign(n, false);
    for (int i = 0; i < n; ++i) {
      if (used[uf.root(i)]) continue;
      dfs2(i, -1);
      used[uf.root(i)] = true;
    }
  }
  size_t size() const {
    return G.size();
  }
};

// これらを実装してください
/*
struct Merger {
  using type = ll;
  // その頂点から出ていく値から入ってくる値を計算する
  static vector<type> evaluate(const vector<type>& value) {
  }
  // (辺数-1)個の出ていく値から1個の入ってくる値を計算する
  static type merge(const vector<type>& value) {
  }
};
*/

使用例 (問題: V - Subtree)

#include <bits/stdc++.h>

// ここに↑を貼る

ll M;

struct Merger {
  using type = ll;
  // その頂点から出ていく値から入ってくる値を計算する
  static vector<type> evaluate(const vector<type>& value) {
    const ll n = value.size();
    vector<type> L(n+1, 1), R(n+1, 1);
    for (int i = 0; i < n; ++i) {
      L[i+1] = (L[i] * value[i]) % M;
    }
    for (int i = n-1; i >= 0; --i) {
      R[i] = (R[i+1] * value[i]) % M;
    }
    vector<type> res(n);
    for (int i = 0; i < n; ++i) {
      res[i] = (L[i] * R[i+1] + 1) % M;
    }
    return res;
  }
  // (辺数-1)個の出ていく値から1個の入ってくる値を計算する
  static type merge(const vector<type>& value) {
    ll res = 1;
    for (auto&& x : value) {
      res = (res * x) % M;
    }
    res = (res + 1) % M;
    return res;
  }
};

int main() {
  ll n; cin >> n >> M;
  EdgeDpOnForest<Merger> dp(n);
  for (int i = 0; i < n-1; ++i) {
    ll a, b; cin >> a >> b; --a, --b;
    dp.add(a, b);
  }
  dp.dp();
  for (int i = 0; i < n; ++i) {
    ll ans = 1;
    for (auto&& e : dp.G[i]) {
      ans = (ans * e.value) % M;
    }
    cout << ans << endl;
  }
}

gdbでredirectが使えない

僕の環境

$ gdb a.out -eval-command run < nyuryoku

通常の環境

普通、gdbでredirectするには、下のようにすれば良いらしい。

$ gcc -g a.cpp -o a.out
$ gdb a.out
(gdb) run < nyuryoku

ただ、僕の環境では

(gdb) run "<" "nyuryoku"

と解釈されてしまいうまく動かなかった。
ggっても解決には至らなかったのでここに残そうと思う。

$ gdb a.out -eval-command run < nyuryoku

JISキーボードをUSキーボードとして使う

結論

Windows

Keymapする。

1. お手軽な方法

↓をDLして実行、気に入ったらスタートアップ(shell:startup)に登録する。

www.dropbox.com

2. 編集したいなら

AutoHotkey をインストールして以下のスクリプトhoge.ahk などと保存して実行する。

気に入ったらスタートアップ(shell:startup)に登録する。

※↓のkeymapは ~全角/半角 ではなく バックスペース の左隣のキーに割り当てている

#InstallKeybdHook
$+2::Send,{@}
$+6::Send,{^}
$+7::Send,{&}
$+8::Send,{*}
$+9::Send,{(}
$+0::Send,{)}
$^::Send,{=}
$~::Send,{+}
$+-::Send,{_}
$]::\
$+]::\
$+;::Send,{vkBAsc028}
$@::[
$[::Send,{]}
$+@::Send,{{}
$+[::Send,{}}
$\::`
$+\::Send,{~}
$vkBA::Send,{'}
$+vkBA::2
$+vkBB::Send,{vkBA}
$sc056::`
$+sc056::Send,{~}
Mac

Karabiner - Software for macOS を使ってkeymapする。

(詳しいサイトが多いのでggってください)

動機: USキーボードじゃだめなんです

USキーボードはキーが少なく、全角/半角切り替えのコストがどうしても大きくなる。

しかも今の入力モードを意識しないといけないToggleはヤダ。

無変換 キーを無変換の機能を残しながら(macの) 英数 キーに、
カタカナ, ひらがな キーをそのまま使いたい。

無変換 キーの設定をしたい人は↓が参考になるかも。
ただこのサイトでは無変換機能を殺しているので残すなら「変換前入力中」だけ元のままに。

freelifetech.com