C++の約数とか使う時用の関数

O(\sqrt{N})なのでN=1e10とかなら動くはず。

vector<ll> divisor(ll M){ //約数の全列挙
    vector<ll> dd;
    for(ll i = 1; i*i <= M; i++){
        if(M % i == 0){
            dd.push_back(i);
            if(i * i != M){
                dd.push_back(M/i);
            }
        }
    }
    sort(dd.begin(), dd.end());
    return dd;
}
vector<ll> factor(ll M){ //素因数分解
    vector<ll> dd;
    if(M == 1){
        dd.push_back(1);
        return dd;
    }
    for(ll i = 2; i*i <= M; i++){
        while(M % i == 0){
            dd.push_back(i);
            M /= i;
        }
    }
    if(M != 1) dd.push_back(M);
    sort(dd.begin(), dd.end());
    return dd;
}

よくある処理を使いやすい関数にまとめていく作業って大事。

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水色になりました

無事水色になることができた。
f:id:yuji9511yuji:20181014004849p:plain
ぶっちゃけると水色ならもうちょっとすぐになれると思っていた...笑

水色を目前に控えた時に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次元いもすをしてみた

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

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

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

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

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

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

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