マルチコアでtar解凍/圧縮

いつまでたってもコマンドを覚えられないので自分用にまとめておく。 tar.gz圧縮解凍(シングルコア) 圧縮 tar -zcvf archive.tar.gz archive 解凍 tar -zxvf archive.tar.gz tar.gz圧縮解凍(マルチコア) 圧縮(8core並列の場合) tar cv archive | pigz -9 -p …

pymatgenの小さなバグを直した

pymatgen.analysis.graphsにnetworkx周りのバグがあったので修正とユニットテストの追加をしてプルリクエストを送った。 github.com OSSにプルリクエストを送って英文で説明するのが初めてだったのでめっちゃググった: sucrose.hatenablog.com github.blog q…

結晶の次元数

pymatgenのサブモジュールを眺めていたらpymatgen.analysis.dimensionalityという結晶の次元数を調べるモジュールを見つけた。 pymatgen.org 関数の使い方よりもそもそも結晶の次元数とはどのように定義されるか、そしてどのようにそれを計算するかに興味が…

周期表を描く(pymatgen+matplotlib)

pymatgen.util.plotting.periodic_table_heatmapを使うと周期表の形で元素ごとにある実数値をヒートマップで可視化することができる。 一方、例えば元素ごとにイオン半径を可視化したいときなどは対応する関数がpymatgenにないので自分でいろいろと書かない…

整数行列のスミス標準形・エルミート標準形を計算する

整数行列のスミス標準形とエルミート標準形とそれぞれの変換行列が欲しい状況に遭遇したのだが、標準的なpythonのライブラリには実装されていなかったので自分で書いた。github.comスミス標準形の実装には以下のブログを大いに参考にした(というかほぼそのま…

pymatgenで状態図を描く

pymatgenで状態図を描く方法の備忘録。 ついでにMaterials Project Rest を使う方法も調べた。 Materials Project API key の登録 まず、Materials Project Rest を使うにはユーザー登録してAPIキーを作成しなければならない。 登録は以下のリンクから行える…

graphillion.graphset.graphsの引数

graphillionでグラフセットを作成する方法を公式ドキュメントで調べたときのメモ。 graphillionのバージョンはv1.01。 複雑な条件でグラフセットを作成するにはgraphillion.graphset.graphsを使えば良さそう。 graphillion.graphset.graphsで指定できる引数…

pymatgenで結晶の体積を予測する

pymatgenにはpymatgen.analysis.structure_prediction.volume_predictor.DLSVolumePredictorというクラスがあって、ボンド長のデータベースに基づいて与えられた結晶の体積を予測することができる(すごい)。 DLSVolumePredictor を使えるようにする pymatgen…

pymatgenでVASPの入力ファイルを作る

pymatgenを使うとVASPの入力ファイルを簡単に作ることができるが、公式ドキュメントにはまとまった記述がなかったので自分用に備忘録を残しておく。 正直、pymatgenのAPIドキュメントを読めばこの記事を読む必要はないと思う。 POTCAR http://pymatgen.org/i…

周期カーネルに対するFeature Map

ガウス過程回帰の課題のひとつとしてスケーラビリティがあります。 データ数をNとしてfitting の時間計算量、predict の時間計算量がであることから大量のデータを扱いたいときは何らかの近似が必要です。そのような近似手法のひとつとして、カーネルを有限…

化合物の構造を表現する記述子

無機化合物の化学式とユニットセルの情報及び原子の座標から物性値(結合エネルギー・バンドギャップ)を予測するKaggleコンペに参加していた。 Nomad2018 Predicting Transparent Conductors | Kaggle feature engineering の過程で分子および無機結晶の構造…

マルチカノニカル法で個数推定

はじめに 去年の11,12月にマルコフ連鎖モンテカルロ法(MCMC)の集中講義を受けてきました。 講義の中で紹介されたマルチカノニカル法を応用してレアイベントをサンプリングする手法が特に面白かったので、復習も兼ねて実装してみました。 マルチカノニカル法 …

AOJ 1320 City Merger

AOJ

問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320)AOJ2022(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2022)とほとんど同じ問題。他の都市名の部分文字列になっている都市名を予め取り除いてからbitDPをする。 #inclu…

AOJ 2534 Dictionary

AOJ

問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534)まず、与えられた文字列の組(string_i, string_j)(i このグラフの構築段階で(i,j)に辺があるのに(j,i)にも辺が張られているば矛盾しているのでfalseを返す。また、'@'は最小であるは…

Codeforces Round #341 (Div. 2) D. Rat Kwesh and Cheese

問題文はこちら(Problem - D - Codeforces)まず\( (x^y)^z = (x^z)^y \)であることから\(a_4, a_8, a_{12}\)が候補から外れる。 単純に与えられた式を計算するとオーバーフローしてしまうため、対数をとって比較していく。ただし、\(x (i) x,y,zが全て1より…

焼きなまし法でThomson問題の解を探索する

Thomson問題 Thomson問題とは、三次元単位球の表面にN個の電荷の等しい粒子を配置するとき、クーロンポテンシャル\( U = \sum_{i wikiをThomson problem - Wikipedia, the free encyclopedia。N=5のときにて三方両錐形が解になったり、N=8で立方体が解になら…

SRM 667 Div1 Easy Order Of Operations

どのメモリを使用したかをbitで管理する。 n個の指示を完了するためには、goal := s[0] | s[1] | ... | s[n-1] でbitの立っているメモリを少なくとも一回は使わなければならない。 逆に、goalで立っているbitに対応するメモリを全て実行したならば全ての指示…

Richardson補外とか丸め誤差について

『数値計算の常識』(伊理正夫・藤野和建著)を読んでいろいろ試したくなったので、取り敢えず簡単にできるものをやってみる。定積分\( I = \int_{a}^{b} f(x) dx\)をN等分した台形\(I_N\)で近似するとき、 \( I_{1} = \frac{1}{2}(b - a)(f(a) + f(b)) \) \( …

AOJ 2333 My friends are small

まず、wを昇順でソートする。 dp[i][j] = #{w[i]以降のみを使って和がjとなる組} sum[i] = w[i]までの和 とするとき、次の3つの場合を考えれば良い。(i) w[0]を使わない (ii) w[0]からw[i]までを使い、w[i+1]を使わない(0 (iii) 全て使う(i)の場合, (i=1,j) …

SRM 664 Div1 Easy Bear Plays

組(X,Y)(X f(X) = 2X or S - 2Xこれをmod S で見ると、f(X) ≡ 2X or -2X であるから、f^K (X) ≡ 2^K * X or -2^K * Xf^K (X) ≡ -2^K * X は個数がS - 2^K * X の場合に対応するから、X = min(A,B)として、min(2^K * X, S - 2^K * X) (mod S) が答えとなる。 …

Codeforces Round #304 (Div. 2) E Soldier and Traveling

sourceとsinkを追加し流量制限にa[i],b[i]を与えることで二部グラフのフローになることは本番中に気づいたが、YESだった場合に経路復元する方法が分からなかった。考えてみると、逆辺のcapはその辺に流したフローの量であるから、ここから容易に復元すること…

Codeforces Round #304 (Div. 2) D Soldier and Number Game

dp[i]をi以下の各自然数について素因数分解したときの素因数の個数の総和とすると、dp[a]-dp[b]が答えとなる。よって、前処理で素因数分解をしておけばいい。エラトステネスの篩をするときにsieve[i]にiの素因数のひとつ(最小や最大のものに固定することもで…

高速メビウス変換について

高速メビウス変換について自分が勉強した内容をまとめておく。証明はいい感じのサイトを参照のこと。 (http://d.hatena.ne.jp/simezi_tan/20130522/1369203086)集合に関する関数f,gについて次式が成り立つとき、g(S)が計算できているならば、任意のSについて…

ネットワークフロー

練習会でフロー関連の発表をした。内容は↓のとおり。 今までフローを避けてきたので、まとまった勉強をする良い機会となった。しかし、一般マッチングや最大マッチングと最小点カバーにおける関係などはまだ理解できてないので、もう少し蟻本を睨む必要があ…

SRM 657 Div1 Easy Problem Sets

二分探索するだけ。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define ll long long class ProblemSets { public: bool judge(ll E,ll EM,ll M,ll MH,ll H,ll num){ ll x=max(0ll,num-E); ll y=max(0ll,num-H); if(x>E</bits/stdc++.h>…

ARC 37 C問題 億マス計算

制約からして二分探索なんだろうとは思ったが本番では解けなかった。 a,bを最初にソートしておき、付値関数C(x)として次のものを考える。C(x): a[i]*b[j]a[i]*b[pos]x のとき、a[i]x なるpos'について pos>pos' が成り立つ。従ってC(x)はO(N)で計算できる。 …

最短経路問題

蟻本等の内容を復習していく。 Bellman-Ford法 頂点sから頂点iまでの仮の最短距離をd[i]とする 0: d[s]=0, d[i(≠s)]=INF とする 1: u,v∈V に対してd[v]=min(d[v],d[u]+w(u,v))で更新。更新できなくなったら終了 step1がV回実行されても終了しない場合、負の…

SRM 656 Div1 Easy RandomPancakeStack

dp(i,j):i番目の操作でj番目のパンケーキを置く確率 class RandomPancakeStack { public: int N; double memo[300][300]; double dp(int i,int j){ if(memo[i][j]>1e-9) return memo[i][j]; if(i==0) return memo[i][j]=1.0/N; double res=0; for(int k=j+1;k

AOJ 1056 Ben Toh

AOJ

n日までに得る弁当の総数の期待値を計算すればいいわけだが、漸化式がうまく作れない && 他の人のコードを読んでも自明のようにdpしていてよく分からない、というツラさがあったので、この問題の漸化式が私のように漸化式が思いつかなかった人のために愚直に…

scipyの特殊関数

量子力学の教科書を読んでいて、球Bessel関数とかLaguerreの陪多項式がある微分方程式の解だと言われてもいまいちピンと来なかったので適当に実装してmatplotlibでグラフを書いてみようと思っていたところ、scipyに特殊関数のmoduleがあることを知った。Spec…