AtCoder, ABC121: D. XOR World

atcoder.jp

非常に大きな数(になりうる)2数  A, B (A < B) が与えられます.
このときに,  F(A, B) を求める問題です.
ここで,  F(A, B) とは  F(A, B) = A \oplus A+1 \oplus A+2 \oplus ... \oplus B のように定義される関数です(ここで,  \oplus排他的論理和を表します).
 A が小さな値であり  B が非常に大きな数である場合,愚直に繰り返し計算をすると現実的な時間で計算ができません.
ここで,  F(A, B) をじっと眺めると(嘘: 私は解説を読みました), F(A, B) F(0, A-1) \oplus F(0, B) のように分解できることがわかります.
これについては解説を読んだだけではわからなかったのですが,実際に書き下してみると「なるほど!」となります.

f(a, b) = f(0, a-1) xor f(0, b) の解説
f(a, b) = f(0, a-1) xor f(0, b) の解説

これにより, F(0, k) を効率的に計算できれば良いということがわかりました.
では,これを求めるアルゴリズムを考えましょう.
連続する2数  t, t+1排他的論理和は,


t \oplus t+1 = \{
\begin{array}{l}
  1 & \text{(if t が偶数)} \\
  2 & \text{(if t が奇数)} \\
\end{array}

となります(実際に2進数で試してみてください).
実際にはどちらか一方を利用するととで問題は解けます.
ここでは,  t が偶数の時の結果を利用します.

 F(0, A) は2数  i, j を用いて  F(0, A) = i \oplus j のように表せます.
 i, j は以下のように定義できます.


i = \{
\begin{array}
  0 & \text{(if A+1を2で割ったとき商が偶数)} \\
  1 & \text{(if A+1を2で割ったとき商が奇数)}  \\
\end{array}


j = \{
\begin{array}
  0 & \text{(if A+1が偶数)}  \\
  A & \text{(if A+1が奇数)} \\
\end{array}


考え方としては以下ようになります.

  •  [0, A] の数列を [t, t+1] でくくり,くくれた部分を  0 とみなし, 0 \oplus 0 \oplus \dots \0 を考える
  •  A が綺麗にくくり出せない場合,前の処理で得られた数と  A との排他的論理和をとる


コードは↓

#include <iostream>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

long long f(long long a) {
    long long t, s;

    if (((a+1)/2)%2 == 0) t = 0;
    else t = 1;
   
    if ((a+1)%2 == 0) s = 0;
    else s = a;

    return t ^ s;
}


int main() {
    long long a, b; cin >> a >> b;
    cout << (f(a-1) ^ f(b)) << endl;
    return 0;
}

AtCoder, ABC060: B. Choose Integers

atcoder.jp

まず問題文を読むと,「整数をいくつ選んでもよい」とある.
じゃあめんどくさいし1つだけ選ぶことにしましょう.
(2つ以上選んでも最終的には1つ選んだ場合の問題に帰着できる)

選んだ数を  a としてみましょう.
このとき, a A の倍数です.
このため, a k \in \mathbb{N} を用いて,
 
\begin{align}
a = k \cdot A
\end{align}
と表せます.この  a の定義を 式1 とします.
問題文の条件が満たされるかどうかはこの  a C B を法として合同かどうかをチェックすればよいです.

次に,  a B で割った数の取りうる値について考えます.
そのために,まずは  a の最小値,最大値を考えてみます.
 a の取りうる数からなる数列を  \mathbf{X} とすると, \mathbf{X}

\begin{align}
\mathbf{X} = [ A, 2A, 3A, \dots]
\end{align}
と表せます.
 \mathbf{X} の要素を  B で割ったあまりは,数列を \mathbf{X}^\prime として

\begin{align}
\mathbf{X}^\prime = [ A\%B, 2A\%B, 3A\%B, \dots]
\end{align}
となります.
この数列の最大値は j B より小さい整数として,  j \cdot A です.
なぜなら, j B に等しいなら  {X^\prime}_j = 0 であり,
 j = B+i のときは  {X^\prime}_j \equiv {X^\prime}_i \text{ (mod $B$)} だからです.
つまり, \mathbf{X} のはじめの  B-1 個の要素が  B で割った時に  C に等しくなるかどうかを確かめればよいということです.

雑に考えるとエイっとそれっぽいコードがかけそうだけど,ちゃんと自然言語で説明すると意外と難しい...?となった問題でした.
コードは↓です.

#include <iostream>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
    long long a, b, c;
    cin >> a >> b >> c;
    
    string ans = "NO";
    rep (i, a*b) {
        if (i*a % b == c) {
            ans = "YES";
            break;
        }
    }

    cout << ans << endl;
    return 0;
}

AtCoder, ABC100: B. Ringo's Favorite Numbers

atcoder.jp

 100^D で割り切れるN番目に小さな数を求める.
 D \in {0, 1, 2} かつ  N \in [1, 100]なので,あらかじめ数列を作ってしまってもよい.

数列をAとすると,問題文のサンプルにもあるように

  •  D = 0 なら, A = [1, 2, 3, \dots]
  •  D = 1 なら, A = [100, 200, 300, \dots]
  •  D = 2 なら, A = [10000, 20000, 30000, \dots]

となる.
こう見てみると,数列の  k 番目の要素は  A_k = k \cdot 100^D で良さそうに見える.
しかし,  k \cdot 100^D の中には  100^D で割り切れる数が含まれる.
(例として, D=2かつ N=100 \rightarrow k=100のとき, A_k = k \cdot 100^D なら  A_{100} = 1000000 だが,これは 100 D+1回割り切れてしまう)
 100^D で割り切れてしまう場合は, A_{k+1} が答えとなる.

まとめると,

\begin{align}
A_k =
  \begin{cases}
    k \cdot 100^D~ \text{(if $k \cdot 100^D$ can be divided by exactly $D$ times}) \\
    (k+1) \cdot 100^D~ \text{(otherwise)}
  \end{cases}
\end{align}
となる.コードは↓の通り.

# include <cmath>
# include <iostream>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
    int d, n;
    cin >> d >> n;

    int base = pow(100, d);
    int ans = base * n;

    if ((ans / (int)pow(100, d)) % 100 == 0) {
        ans = base * (n+1);
    }
    cout << ans << endl;
    return 0;
}

Codeforces, Good Bye 2018: A. New Year and the Christmas Ornament

Problem - A - Codeforces

クリスマスツリーに3色の飾りを付けたい.
このとき,青色の飾りは黄色の飾りよりも1つ多く使い
赤色の飾りは青色の飾りよりも1つ多く使うという制約が課されている.

黄色の飾りが y 個,青色の飾りが b 個,赤色の飾りが r 個与えられたとき,
上記のルールに従って使える飾りの数の合計の最大値を求めたい.

求めたい数を ans とおき,そのときの黄色・青色・赤色の飾りの数をそれぞれ  \hat{y}, \hat{b}, \hat{r} とする.
題意を満たすときの  \hat{y}, \hat{b}, \hat{r} について考える.
y が最も少ないときに \tilde{y} \lt y であると仮定すると,
y+1 \leq b, y \lt \hat{y} \Rightarrow \tilde{y} \lt y \lt b-1
となり,yb の差が2以上になるが,これは制約を満たさない.
青色,赤色について同様に考えると,題意を満たすときには
y=\hat{y}, b=\hat{b}, r=\hat{r}
の少なくとも1つが成立していなければならないことがわかる.
(3つの等式が全て成立するときは与えられた飾りが全て使いきれて嬉しい)

上記の等式のそれぞれが成立するときの  y, b, r の組み合わせを求め,
与えられた飾りでその組み合わせを作れるかどうかをチェックする.
組み合わせを作れる場合,合計の数を計算する.
合計の数が複数計算できた場合,それらの最大値を計算する.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

template<typename integer>
integer __lcm(integer a, integer b) {
    return (a * b) / __gcd(a, b);
}


int main() {
    int a, b, c;
    cin >> a >> b >> c;

    int ans = 0;
    if (a+1 <= b && a+2 <= c) ans = max(ans, 3*a+3);
    if (b-1 <= a && b+1 <= c) ans = max(ans, 3*b);
    if (c-2 <= a && c-1 <= b) ans = max(ans, 3*c-3);

    cout << ans << endl;
    return 0;
}

オープンソース図書館システム Next-L Enjuの紹介

この記事は klis advent calendarの9日目の記事です.
adventar.org

klis13 & slis17のhimktです.
twitter.com

ぼくはとても図書館が好きなので,今日は図書館,とりわけ図書館システムの話をします.
図書館も日々の情報技術の進歩の影響を受けていて,電子化に関する取り組みなどが多くなされています.
スタンフォード大学の電子資料メインの図書館の話などを聞いたことがある方もいらっしゃるかもしれません.
www.mercurynews.com

このような先進的な図書館が出現し始めていることは事実です.
しかし依然として図書館のシステムに対して「古い」という印象を受けるかたは多いのではないでしょうか.
(図書館のシステムというと骨董品のようなPCの上で動作する様子を想像しませんか?)
地方の公共図書館などの資料検索システムや貸し出しシステムはリプレースされずに古いものが使われ続けていることが多いです.
(出身地域の公共図書館システムに基づく主観的な意見)

Next-Lは,このような図書館システムの現状を変化させる可能性のあるプロジェクトです.
Next-L Enju - Project Next-L
Next-Lはオープンソースソフトウェアです.
ソースコードや議論が公開された状態で開発が行われています.
プログラムのソースコードGitHubで閲覧できます.
github.com
プログラムはRuby(Ruby on Rails)で書かれているため,klisの学生には比較的とっつきやすいです.
プログラムにバグを見つけた場合はGitHubのissueというページに報告をすることができます.
(開発に関わっている方々が反応してくれます.)
github.com
動作のデモは以下のページで確認可能です.
えんじゅ図書館 - Next-L Enju Leaf


Next-Lの図書館システムはいくつかの企業や大学図書館公共図書館で実際に稼働しています.
詳しくはホームページを参照してください.
FrontPage - Project Next-L


Next-Lは月に一回程度筑波大学春日エリアで開発ワークショップを行なっています.
コアの開発メンバーにはklisの方々なら統計の授業でお世話になったであろう高久先生がいらっしゃいます.
twitter.com
開発への貢献に関心を持った方は,先生に質問をしに行けば快く対応してくださると思います(無責任な発言).

個人的に,図書館システムもより短い周期で進化していくべきだと思っていて,Next-Lはこれを実現するプロジェクトだと思います.
開発ワークショップにも数回しか参加していない身の上で身内ぶった説明をしていることに罪悪感を覚えますが,
オープンソースの図書館システムの試みをklisの方々に知っていただければうれしいです.
図書館に携わりたいがプログラミングもしたいという方々は一度覗きにいくとよいと思います.

以上,12/9の記事でした.引き続きklis advent calendarをお楽しみください.

2017/10/24 ~ 2017/12/1

更新サボってたら記憶が消えた

latexのalign環境で行列の下に説明文を追加する

DeepLearning Bookの式7.46を再現したかった.
mathopによって実現した.
ただ,行列のサイズが異なる場合説明文が上下で微妙にずれてしまう問題が残っている.
今回でいえば \mathbf{x}だけ少し下にずれている.
どうすれば良いのかはあとで調べる.

\mathop{\begin{bmatrix}
  18 \\
  5  \\
  15 \\
  -9 \\
  -3
\end{bmatrix}}_{\textstyle \mathbf{y}} &=& 
\mathop{\begin{bmatrix}
  4 & 0 &  0 & -2 &  0 &  0 \\
  0 & 0 & -1 &  0 &  3 &  0 \\
  0 & 5 &  0 &  0 &  0 &  0 \\
  1 & 0 &  0 & -1 &  0 & -4 \\
  1 & 0 &  0 &  0 & -5 &  0
\end{bmatrix}}_{\textstyle \mathbf{A}} & &
\mathop{\begin{bmatrix}
  2 \\
  3 \\
  -2 \\
  -5 \\
  1 \\
  4
\end{bmatrix}}_{\textstyle \mathbf{x}}
\end{align}

  \begin{align}
    \mathop{\begin{bmatrix}
        18 \\
        5  \\
        15 \\
        -9 \\
        -3
      \end{bmatrix}}_{\textstyle \mathbf{y}} &=& 
    \mathop{\begin{bmatrix}
          4 & 0 &  0 & -2 &  0 &  0 \\
          0 & 0 & -1 &  0 &  3 &  0 \\
          0 & 5 &  0 &  0 &  0 &  0 \\
          1 & 0 &  0 & -1 &  0 & -4 \\
          1 & 0 &  0 &  0 & -5 &  0
        \end{bmatrix}}_{\textstyle \mathbf{A}} & &
    \mathop{\begin{bmatrix}
        2 \\
        3 \\
        -2 \\
        -5 \\
        1 \\
        4
      \end{bmatrix}}_{\textstyle \mathbf{x}}
  \end{align}

tex.stackexchange.com

Amazing Mazes

入力データからグラフを作る部分を慎重に作る.
あとは幅優先or深さ優先を書く.

```cpp
//#define _GRIBCXX_DEBUG
#include
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;


class Graph {
public:
int n_node;
vector> edge;

Graph(int n_node) : n_node(n_node){
edge.resize(n_node);
};

void add_edge(int i, int j);
};

void Graph::add_edge(int i, int j) {
// cout << i << ", " << j << endl;
edge[i].push_back(j);
}

int main() {
int w, h, c;
int block;


while (cin >> w >> h, w) {
Graph g(w*h);

rep (i, 2*h-1) {
if (i%2 == 0) {
// yoko
rep (j, w-1) {
cin >> block;
int offset = w * (i / 2);
int c = offset + j;
if (block == 0) g.add_edge(c, c+1);
if (block == 0) g.add_edge(c+1, c);
}
}
else {
// tate
rep (j, w) {
int offset = w * *1 {
int current = que.front(); que.pop();

for (int next_ : g.edge[current]) {
if (cost[next_] == 1001001001) {
que.push(next_);
cost[next_] = cost[current] + 1;
// cout << "current: " << current << ", next: " << next_ << endl;
// cout << "current_cost: " << cost[current] << endl;
}
}
}

if (cost[w*h-1] == 1001001001) {
cout << 0 << endl;
}
else {
cout << cost[w*h-1] << endl;
}
}
return 0;
}
```

Amazing Mazes | Aizu Online Judge

Pythonにはオブジェクトの`__dict__`を返してくれる`vars`という組み込み関数がある.
これを使うと`argparse`の`Namespace`オブジェクトを辞書型のオブジェクトとして持ちたいときに便利.

stackoverflow.com

エイリアスを張っているコマンドに対しても呼び出し元を確認したいときは`type`コマンドが使える.

unix.stackexchange.com

PRMLの実装

github.com

Jupyter Notebook(Python)とPythonのプログラムがある.


argparseのdescriptionの中で改行する

RawTextHelpFormatterというクラスをformatterとして指定する必要がある.

stackoverflow.com

*1:i - 1) / 2); cin >> block; c = j + offset; if (block == 0) g.add_edge(c, c+w); if (block == 0) g.add_edge(c+w, c); } } } // bfs queue que; que.push(0); vector cost(w*h); rep (i, w*h) cost[i] = 1001001001; cost[0] = 1; while (!que.empty(

2017/08/13 ~ 2017/08/16

c++のヘッダを探索パスに追加

毎回調べては忘れているのでメモ.
g++などのコンパイラのオプションとして渡せないときは環境変数を使う.


たとえば,deepnlのビルドにはeigenが必要である.
linuxbrewを使ってeigenをインストールしていた場合,
ヘッダファイルは $(brew --prefix)/Cellar/eigen/version_name/include/eigen3 にある.
よって以下のようにヘッダを指定してやればよい.

CPLUS_INCLUDE_PATH=$(brew --prefix)/Cellar/eigen/3.3.4/include/eigen3 python setup.py build

github.com

Vimでヤンクなしで一行を削除する

"_dというコマンドがあることを知った.
以下のようなmappingをすることでdでヤンクなし削除が実現できた.

github.com


stackoverflow.com

Recurring Decimals

繰り返す10進数 | Aizu Online Judge

 a_{k-1} の各桁の数値を持つベクターを作り,
ソートはベクターに対して行う.
ソート後に a_k を計算すればよい.
コードやや汚い.

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int make_number(vector<int> &a, int l) {
  int res = 0;
  for (int ll=l-1; ll>=0; --ll) {
    res += a[l-ll-1] * pow(10, ll);
  }
  return res;
}

int main() {
  int a0_raw, l, d;
  vector<int> a, a0;

  int i, j;
  int ak_raw;


  while (cin >> a0_raw >> l, a0_raw || l) {
    a0.resize(0); a.resize(0);
    bool reached = false;

    for (int ll=l-1; ll>=0; --ll) {
      d = a0_raw / pow(10, ll);
      a0_raw -= d * pow(10, ll);
      a0.push_back(d);
    }

    a.push_back(make_number(a0, l));

    while (1) {
      sort(a0.begin(), a0.end());
      int amin = make_number(a0, l);

      reverse(a0.begin(), a0.end());
      int amax = make_number(a0, l);

      a0_raw = amax - amin;
      a.push_back(a0_raw);

      i = a.size() - 1;
      rep (j_, i) {
        if (a[i] == a[j_]) {
          j = j_; reached = true;
          break;
        }
      }

      if (reached) break;

      a0.resize(0);
      for (int ll=l-1; ll>=0; --ll) {
        d = a0_raw / pow(10, ll);
        a0_raw -= d * pow(10, ll);
        a0.push_back(d);
      }
    }

    cout << j << " " << a0_raw << " " << i-j << endl;
  }

  return 0;
}
latexなどで利用可能なフォントの一覧を見る

XeLaTeX環境を作るとき,フォントの設定をどうすればよいかわからず色々調べた.
結果として,使用可能なフォントの一覧は fc-list というコマンドで確認できることがわかった.

Presentation with XeLaTeX

matplotlib.pyplot で日本語を使う

matplotlib.rcでフォントを指定できる.

from matplotlib import rc

font = {'family': 'YuGothic'}  # NOTE: use YuGothic for Japanese
rc('font', **font)

paper.hatenadiary.jp