2019-12-18

ビットフラグの判定

競プロの問題でビットフラグの判定の問題があった。

ビットフラグの判定は初見だったので各桁が0か1かを文字列から取り出して判定したが、他の人の解答を見るとどうも自分の書き方はスマートではない。

ということでスマートなビットフラグの判定方法を調べた。

各桁のビットが立っている（1）か立っていない（0）かの判定は

for i in range(n):
   return (num >> i ) & 1

&演算子は論理演算のANDで、比較した両方のビットが1のときに1になる。& 1というのは000001(0は任意の数)との比較である。すなわち右から2番め以降のビットは比較せずとも必ず0になるので、一番右のビットのみ判定が可能ということである。ビットが立っていれば000001、立っていなければ000000になるので1 or 0の出力になり、右へのビットシフトを組み合わせることで各桁のビットの判定が可能ということである。

ちなみに私のabc014 B問題の解答は

n, x = map(int, input().split())
a = list(map(int, input().split()))

bx = bin(x)[::-1]
ans = 0

for i in range(n):
    if ((x >> i) & 1): ans += a[i]
    
print(ans)

とした。

2019-05-19

Rの出力結果をWordに貼り付ける

Rの出力結果をそのままwordにコピペすると、形式が崩れてしまいます。しかし、Rの貼り付けた部分のフォントをConsolas、またはLucida Consoleに変更すれば形式が崩れません。簡単に解決できますね。

2019-03-21

フィボナッチ数列で動的計画法に入門する

無数にある同様の記事の二番煎じになってしまうが、自分でまとめたいのでご容赦を。Pythonでフィボナッチ数列を実装することで、動的計画法に入門することが目的。

フィボナッチ数列とは

フィボナッチ数列とは、前の2つの数の和が次の数字となる数列のことである。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... といった具合に無限に続く。

再帰的に実装

再帰的に書くと以下の通りだ。

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

nが1になるまでfib(n-1) + fib(n-2)の両項で再帰を繰り返すので、同じ処理が2回発生する。これは計算量がO(2^n)となり、nの大きさに応じで計算量が指数関数的に増大する。nが小さい場合は計算可能だが、nが大きくなると計算できなくなってしまう。

最近atcoderにpythonで参加しているが、tle（制限時間超過）になってしまうことがしばしばあるので、計算量を意識してプログラミングしたいと思っている。一度計算した値をメモリに保存しておくことで、再度同じ処理が呼ばれた際に計算しなくていいメモ化という方法がある。これは参照透過性、すなわち引数に対して返り値が一意に定まる関数（単射）のことである。

from functools import lru_cache

@lru_cache(max_size=None)
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

このように@lru_cacheを関数の前に書くだけで自動でメモ化してくれる。しかし、競プロではメモ化だけ行ってアルゴリズムの改善を行っても依然としてTLEになってしまうことが多々あるので、よりよい改善を以下に記す。

動的計画法で実装

上述したような問題を解決する策として、動的計画法（Dynamic Programming）がある。動的計画法は対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく。

分割統治法
メモ化

参考

動的計画法 - Wikipedia

functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.7.3rc1 ドキュメント

2019-03-14

Pythonでリストを反転する

Python プログラミング競プロ

>>> [1, 2, 3, 4][::-1]
[4, 3, 2, 1]

>>> "apple"[::-1]
'elppa'

リストまたは文字列を[::-1]すると反転する。

2019-03-14

Pythonで桁数を指定して0埋めする方法

Python プログラミング競プロ

5桁の数字で余った位を0埋めする場合例: 123 を 00123と表示する。

>>> print("{:05d}.format(123)")
00123

>>> print("{:05d}".format(12345))
12345

>>> print("{:05d}".format(123456))
123456

上は0埋め、5桁、decimal(10進数)。 4桁なら"{:04d}".format(123)"

2019-02-25

karabinerで単体のcommandが効かなくなる問題の対処

その他（技術）

karabinerで日英の入力切り替えをcommandに割り当てると単体のcommandが使えなくなり、他の単体commandによる操作が行えなくなる。筆者の環境ではcheetsheetというアプリを入れていて、command長押しがそのショートカットなっているが、karabinerが悪さをするせいで機能しない。今回はその解決策を記す。

解決策

設定ファイルを少しいじるだけなので簡単である。

まず、karabinerのアプリからこの問題を解決することは不可能なので、karabinerの設定ファイル~/.config/karabiner/karabiner.jsonを開く。

"to": [
    {
        "key_code": "left_command",
        "lazy": true
    }
],

"to": [
    {
        "key_code": "right_command",
        "lazy": true
    }
],

という箇所が複数箇所に見られるので、"lazy": trueなっている箇所を"lazy": falseに修正する。筆者の環境ではcommandによるtoggle方式の入力切り替えを設定しているが、左右別に日英を割り当てている場合も修正箇所は同じである。なお、左右どちらかのみ単体commandを効かせたい場合は、left_commandあるいはright_commandのどちらかを修正すればよい。

最後に設定ファイルを保存すれば修正完了である。

2019-02-12

C++入門

C++

最近競プロを始めたことに伴い、C++を勉強している。自分用のtipsとしてメモを残していく。細かい話は慣れてから再度調べるため、おまじないとして自分に言い聞かせている箇所がある。読者はあまり参考にしない方がいい。

using namespace std;

using namespace std;
cin >> hoge;

これは毎回std::を書かなくていいよう名前空間を宣言しているのだが、できるだけ使用を避けたほうが良い。そうでないと他のモジュールのの名前とぶつかる可能性がある。競プロではよく利用されているがシンプルなプログラムを書くときのみの使用に留めておくのが良い。

ちなみにusing namespace std;を書かないと、

std::cin >> hoge;

などと修飾して書く必要がある。

コンパイル

g++ -o hoge hoge.cpp

hoge.cppをコンパイルしてhogeという名前のファイルとして出力する。

g++ hoge.cpp

としてもコンパイル可能だが、a.outという名前のファイルで出力され、どのファイルをコンパイルしたものかわからなくなるため、g++ -o [output_file] [input_file]を使ったほうが良い。

入出力

# include <iostream>

string hoge;

cin >> hoge;
cout << hoge;

入門の記事では入出力にiostreamを使っている様子が多く見られるが、これはどうやら遅いらしい。

【調べ途中: scanf, printfの使い方を調べる】

# include <cstdio>

string hoge;

scanf("%s", &hoge)
printf("%s\n", hoge)

を使うほうが良い。

文字	意味	型
%c	一文字	char
%s	文字列	string
%d	10進数	int
%f	浮動小数点	float

他にもあるがよく使いそうなものだけ。

クラス

class Car {
    private:
        string name;
    public:
    Car(string s) {
        name = s;
    }
};

クラスの名前と同じ関数がコンストラクタとなる。また、上の書き方ではnameという変数を作ってからsを代入しているが、

class Car {
    private:
        string name;
    public:
    Car(string s): name(s) {
    }
};

と書くことで、変数作成時に同時に値を代入することもできる。

関数

class Car {
    private:
        string name;
    public:
    Car(string s): name(s) {
    }
    void printName() const {
        cout << "この車の名前は" << name << "です。" << endl;
    }
};

まずvoidはreturnによる返り値のない関数の宣言である。関数printName()はクラスに属する関数なのでメンバ関数と呼ばれ、coutで画面に出力しているだけである。また、変数を何も書き換えないため、関数の名前のあとにconstを書いている。

ちなみにprivateとクラスの先頭で宣言しているが、public:の上に記述されたものはすべてprivateとなるため、省略可。

インライン関数

上記のコンストラクタCarとメンバ関数printNameはどちらもクラスの中に書かれているため、インライン関数となっている。インライン関数とはクラスから生成されたそれぞれのオブジェクトすべてが、その関数のコードをオブジェクト自身に持つことである。一方クラスの外に関数を書くことも可能で、この場合オブジェクトから関数を呼び出すと、その関数のポインタが指すメモリに格納されたソースコードを読み関数が実行される。どちらも同じ関数を実行することは可能であるが、クラスの内側に関数を書くとソースコードが増えるため、基本的には外に書く。しかし、インライン関数としてクラスの内側に関数を書くことで、メモリの参照をせず、直接オブジェクトが持つ関数のソースコードを実行し、高速に関数を実行することもできる。高速に呼び出したい関数はインライン関数としてクラスの内側、コンパイル後のソースコードを減らしたい場合はクラスの外側に書くと良い。

class Car {
    private:
        string name;
    public:
    Car(string s);
    void printName() const;
};

Car::Car(string s): name(s) {
    }
void Car::printName() const {
    cout << "この車の名前は" << name << "です。" << endl;
}

また、コンストラクタCarをクラスの外側に移動したため、クラス内のコンストラクタの引数であるsを省略することができる。定義が直後に書かれない場合は、引数の型のみ指定して、名前は省略可。

class Car {
    private:
        string name;
    public:
    Car(string);
    void printName() const;
};

Car::Car(string s): name(s) {
    }
void Car::printName() const {
    cout << "この車の名前は" << name << "です。" << endl;
}

クラスに引数の異なる同名のメンバ関数（*コンストラクタも含む）をいくつ書いても良い。

int main() {
    return 0;
}

本来intで宣言された関数は上のように返り値として整数を返さなければいけないが、C++ではmain関数の最後で自動的にreturn 0;してくれる。したがってまmain関数に限り、return 0;は省略可能である。また、main関数の宣言はintで行うように決められているので返り値がないからといって勝手にvoidなどで宣言してはいけない。

Machine Morning

機械学習やWebについて学んだことを記録しています。