Pythonでsubprocessを用いてshellコマンドを実行する

PythonからJavaのプログラムを直接呼び出したくなる場面があったので調べたところsubprocessという標準ライブラリを用いるとできるらしい。

import subprocess

if __name__ == '__main__':
    result = subprocess.Popen("java -cp ./path/to file_1".strip().split(), stderr=subprocess.PIPE, stdout=subprocess.PIPE)
    if not result.stderr.read():
        print(result.stdout.read())

このように実行すると別プロセスでシェルコマンドが実行されるがpythonは終了まで結果を待機する同期的な実行となる。subprocess.PIPEを用いることで標準出力や標準エラー出力をパイプを用いてresult変数に格納することが可能となる。

上の例ではエラーを吐かずに正常終了した場合のみ標準出力の結果を出力するような処理になっている。

Code Festival 2018 qual B

ABC3完の91位。500点のCを20分程度で一発で通せたのはなかなか大きかった。

A
100 -(Nの倍数な数字の個数)

B
一番顔が面白いやつにXを全て足すと最適

C
制限の201800をみて、1000 * 1000/201800をしたらほぼ5だったので、よっぽどのことがない限りは一つのXで5個分をカバーしないとわかった。効率よく埋めようと考えて十字形のパーツを隙間なく入れていくことを考えた時に一番はじめに桂馬とび型のパターンが浮かんだのが幸いだった。
桂馬じゃない形で埋まりそうなのもあったっぽいがそれだと250000個くらい必要でWAするらしい。こっち先に思いつかなくてよかった...

WAペナがなかったので1000 * 1000でもXの個数確かめずに出したのが結果的に時間の短縮になってよかったかも。

D
なんか確率の問題やばそうって思ってどちらかというととっつきやすそうなEに移動した

E
1/最小公倍数に持っていくのは良いとして、±LCM/nを使って1を作れればいいなーと思ってたけどなんせ数が大きすぎるし320回でおさまる気もしなかった。MODでどうにかするんだろうなーという発想は浮かんだがそこから考察を進める力はなかった

100位以内に入ったからThanksの方はもしかしたら参加できるのかな？こんな運がよかった早解きで参加していいものなのかどうか...

AtCoder水色になりました

無事水色になることができた。

ぶっちゃけると水色ならもうちょっとすぐになれると思っていた...笑

水色を目前に控えた時にC問題にどハマりして死ぬみたいな展開を何回かやってしまったのでそれでしばらく停滞したんだと思う。
あと、AGC早解きは貴重なレートアップの機会だった()

別にここまでは特にストイックに何かをやったということはなく、過去のC問題とD問題を新しいものから順にやっていってるくらい。
C問題はほとんど解けるけどD問題でヒントなしで行けるのはまだ2~3割程度か。
500点とかになった瞬間手も足も出なくなるケースが多いけどそこは慣れていくしかなさそう。

とりあえず今後レート上げてくためにしばらくはCD早解きになると思うので、まずは最低限400点のD問題をささっと解けるレベルにしていきたいと思ってる。

あと、これからARCになるとNo sub撤退したくなる機会が増えてくる気もするけど、出来るだけしないように心がけよう。
多分レート上がるに従ってレートの減少を怖がり始めるだろうけどそこ気にしてたら肝心の精進の妨げになると思われるので。

これからもしばらくはCD問題の過去問を潰していくつもり。一通り潰した上でこっから伸ばすには何が必要なのかとか考えていこうかな。とりあえず今の所全く要領がつかめないDPをどうにかしないといけない。

github pagesをつくった

githubアカウントさえ持っていれば誰でも気軽に自分のホームページを置くことができるgithub pagesというものをつくってみた。
pages.github.com
作成はめちゃくちゃ簡単だった。

1. (自分のアカウント名).github.io という新しいレポジトリを作成する(正確に一致してないとダメらしい)。

2. cloneして適当にindex.htmlとかつくってcommitする。

3. https://(アカウント名).github.io にアクセスする

これだけ！

面倒な設定なしにSSL化したWebページをすぐ作ることができた。

自分のホームページ作りも兼ねてVue.jsの勉強でもしようかなーと思ってます。

ちなみに自分のページはこれ
https://ysugiyama12.github.io/

シンボリックリンクってなんぞや

よく「シンボリックリンクを貼る」みたいな操作を目にするが、実際に何をしているかちゃんと把握していなかったので調べてみた。

シンボリックリンクとは

別ディレクトリに存在するファイルやディレクトリを参照するファイルのことを指す。
ファイルの実体はそこには存在しないが、そのファイルにアクセスすることで元ファイルへと自動で参照が行われる。
ハードリンクと対比させてソフトリンクとも呼ばれる。

ハードリンクとシンボリックリンクはどう違うのか

ハードリンクは同一ディレクトリ下のみで作成可能で、ディレクトリに対しては実行することができない。
「iノード番号」と呼ばれる、ファイルを識別するための番号が元ファイルと一致する。
つまり、ハードリンクは別のファイル名で同一ファイルにアクセスできるようにしている。

シンボリックリンクではiノード番号ではなくパスを用いてファイルを参照するため、別ディレクトリであってもファイルを参照することができる。
シンボリックリンクを貼った後に元ファイルを移動すると参照できなくなり、元ファイルを消せば消えてしまう。

実行方法

lnコマンドを用いる。 -sをつければシンボリックリンクを、無しならハードリンクを作成する。

2次元いもすをしてみた

２次元平面で異なるN個の範囲を示す座標が与えられ、その重なりがもっとも多い部分を求めるような問題。

普通の解法であれば二次元の配列を用意していN個それぞれについて指定された範囲の数値をインクリメントする事になる。

しかし、二次元平面の縦と横の長さをH,Wとするとこの方法の最悪計算量はO(NWH)であり、Nやら二次元平面の縦横の値が大きくなるとTLEしてしまう。

そこで、いもす法というアルゴリズムを用いてこの数え上げをO(N + WH)で行うことを試みる。いもす法は当然１次元でも使用でき、２次元以上の多次元においても適用できるが、今回はわかりやすくて威力を感じられる二次元を選択することにした。

操作の概要としては
1. 左上、右下に+1を、右上と左下に-1をかく
2. 左から右へ書いてある値を足していく
3. 同様に上から下へ書いてある値を足していく

このようにすることで全範囲の累積値が簡単に求まる。WH回のインクリメント操作がたった4回で済むので大きく計算量が落ちる。

ただ、はじめの説明にある+1と-1の場所に少し注意。下の写真に示したように-1を加える場所は右上の角の一つ右、左下の角の１つ下となる。右下に+1するものはx,yともに一つずらした場所となる。このようにすることで左と上から累積和を求めた時に正しく結果が求まるようになる。

Combinationの求め方まとめ

c++でnCkの計算でnの値に応じた2種類の導出方法をメモ。

1. nの値が50程度でlong long型に収まるとき

このときはオーバーフローや時間制約を気にする必要はないが、階乗を愚直に計算することはできないので注意する。
nCk = n-1Ck-1 + n-1Ckというパスカルの三角形から導かれる公式を用いることでO(n^2)で計算が可能である。

#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e9)
using namespace std;
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;
int N,K;
ll v[51][51];

void nck(){
    rep(i,0,N+1){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    rep(i,1,N+1){
        rep(j,1,i){
            v[i][j] = v[i-1][j-1] + v[i-1][j];
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    nck();
    print(v[N][K]);

}

50C25で1e14程度のオーダーなのでN<=50程度の制約であればこちらの方法で問題ない。

1. nが大きくmodを用いる場合

当然nが1000などになってくればオーバーフローするので1e9+7などの値でmodを取ることを要求してくるのが普通である。
また、nが100000程度になればO(n^2)で計算を行うことも不可能である。
このような場合、逆元を用いたmod計算を行うことで結果を導出することができる。
ここで用いるのがフェルマーの小定理。
aとpが互いに素であるときに

が成り立つというものである。詳しいことはこちら↓
mathtrain.jp
この式の両辺にをかけると

となる。したがって、の逆数のmodはのmodに等しいということがわかる。
これで準備が整う。こうして求まったmodの値を保持しておいて、の3つを掛け合わせて再びmodを取る(この時オーバーフローに注意)ことで答えが求まる。
その場で考えずに貼り付けるケースが多そうだから原理はそこまで重要じゃなさそうだけど。
以下実装の例。

#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;
const ll max_N = 110000;
ll fac[max_N + 1000], facinv[max_N + 1000];
const ll MOD = 1e9 + 7;
ll N,K;

ll power(ll x, ll n){
    if(n == 0) return 1LL;
    ll res = power(x * x % MOD, n/2);
    if(n % 2 == 1){
        res = res * x % MOD;
    }
    return res;
}

ll nck(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[k] % MOD * facinv[n-k] % MOD;
}

ll npk(ll n, ll k){
    if(k == 0 || n == k){
        return 1;
    }
    return fac[n] * facinv[n-k] % MOD;
}



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    fac[0] = 0;
    fac[1] = 1;
    rep(i,2,max_N){
        fac[i] = (fac[i-1] * i) % MOD;
    }
    rep(i,0,max_N){
        facinv[i] = power(fac[i], MOD - 2);
    }
    print(nck(N,K));
}

facが通常の階乗のmodで、facinvが逆元を表している。
これを用いるとn = 100000程度であっても答えを得ることができる。