2022-02-10

JavaでC++のlower_boundとupper_boundを実装

AtCoderでよく使うので、念のため書き残しておく。

詳細は Javaでの二分探索、lower_boundとupper_boundの実装 - naoppyの日記に記述されています。Integerの配列aに対して、値bのlower_boundを求めるのに、

~Arrays.binarySearch(a, b, (x,y)->(x.compareTo(y)>=0) ? 1 : -1);

を使う。ここでArraysでComparatorを指定するため、必ずObject型の配列を使用する必要がある。また、aがCollectionsの場合では、

~Collections.binarySearch(a, b, (x,y)->(x.compareTo(y)>=0) ? 1 : -1);

を使う。

また、upper_boundを求めるのに、

~Arrays.binarySearch(a, b, (x,y)->(x.compareTo(y)>0) ? 1 : -1);

か

~Collections.binarySearch(a, b, (x,y)->(x.compareTo(y)>0) ? 1 : -1);

を使う。

2021-09-30

Vimで数字を一つ繰り上げて置き換える方法

Vimの編集内容の数字を一つ繰り上げる必要があるときに

:%s/$[0-9]\+$/\=submatch(1)+1

を使う。

数字の正規表現（[0-9]\+）には必ず$と$で囲む必要がある。Vim深い！

2021-06-16

Gitで各ブランチを最近commitした日時順にソートした一覧を表示する

Gitで各ブランチの一覧を最近commitした日時順にソートしたい。

List remote Git branches and the last commit date for each branch. Sort by most recent commit date. · GitHub

にコマンドが書かれている。

for branch in `git branch -r | grep -v HEAD`;do echo -e `git show --format="%ci %cr" $branch | head -n 1` \\t$branch; done | sort -r

を実行すればよい。

2021-06-07

Maximaで関数の最小値を得るための引数を計算する

Atcoderのabc204問題E（E - Rush Hour 2）では $\frac{D}{t+1} + t$ の最小値を得るための $t$ を計算する必要があった。

後で調べたMaximaでの計算方法であるが、記録のため保存する。

How to find the maximum and minimum of a function using Maxima? - Stack Overflow

に参考して、Maximaには以下のように入力する。

f(t):=d/(t+1) + t;

（関数定義）

f_deriv: diff(f(t),t);

（関数の微分を求める）

solve(f_deriv=0,t);

（微分が0の解を求める）

結果としては

[t = (- sqrt(d)) - 1, t = sqrt(d) - 1]

と出力されるが、本来関数の最大値と最小値のときの両方のtが入っている。今回はE問題の解説で $\sqrt{t} - 1$ が回答となることがわかる（E問題ではまた整数に丸める必要がある）。

念のため、グラフでの確認も可能ですが、Maximaで関数に $d$ のような変数が定義されている場合のグラフの出力する方法がわからず、とりあえずd=10のときのグラフを出力してみた。

f(x):=10/(t+1)+t;

plot2d(f(x), [t,0,10])$

出力されたのは以下のようなグラフ

f:id:hanaokaiwa:20210607044849p:plain

$\sqrt{10} - 1 \approx 2.16$ のところに最小値になっていることが確認できる。

2021-06-01

Vimで編集内容に現在の行番号を入れる

VimでDBに入れるためのマスターデータのCSVファイルを作成して、最初の項目が数字のIDであるが、実は現在の行番号と同じ数字である。

現在の行番号を1行ずつ入れるのは面倒なので、一括置き換えでできないかを調べてみた。

Replace a pattern with current line number - Vi and Vim Stack Exchange

に答えが書かれていた。xを現在の行番号に置き換える場合、

:%s/x/\=printf("%d", line('.'))

を実行すればよい。

それを自分の場合では，

:%s/^/\=printf("%d,", line('.'))

（行の先頭に「行番号,」を挿入）を実行すればよい。

2021-05-16

数列の任意の2つの項のXORの結果の合計を計算する方法

とある長さ $N$ の数列 $A_1, A_2, \dots , A_N$ に対し、 $1\leq i\leq j\leq N$ を満たす全ての組 $(i,j)$ について $A_i$ XOR $A_j$ をもとめ、その合計を計算する問題の解き方。

詳細については

Editorial - Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）

の後半に説明されている。

まず、ある桁数 $k$ に対し、すべての $1\leq i\leq N$ について、 $A_i$ の $k$ 桁目が1か0かを判定して、それぞれの $A_i$ の数を数える。例えば、 $k$ 桁目が1の数が $C_{k1}$ で、 $k$ 桁目が0の数が $C_{k0}$ の場合、 $k$ 桁目関して、合計の結果は $C_{k1} \times C_{k0} \times 2^{k-1}$ となる。