読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

複数プロジェクトが併存できるC++用の汎用的なMakefile

c++

汎用的に使えるMakefileを作ってみた github.com詳細はこちらから qiita.com

anaconda3でgraph_toolを使う

ubuntuでgraph_tool(graph-tool: Efficent network analysis with python)を使うときには、以下のリンクに従ってレポジトリを登録したあと、以下のコマンドで簡単にインストールできる。 sudo apt install python-graph-tool # python2 version sudo apt ins…

フィボナッチ数の一般項

フィボナッチ数の一般項は以下の式で表される。 これを展開して、無理数をなくしてあげると以下のようになる。 計算量はである。例えばpython3で実装すれば以下のようになる。 import scipy.misc as scm import math fib = lambda n : int(sum([scm.comb(n,2…

ssh設定の備忘録

よく設定する癖によく忘れるので備忘録を書きます クライアント側設定 鍵の作成 $ ssh-keygen -t rsa -b 4096 -C "your_email@example.com" 鍵にかかっているパスワードの変更 $ ssh-keygen -p Enter file in which the key is (/home/user/.ssh/id_rsa): [P…

codeIQ 2751

図形に関して, 3*7の長方形を3個つなげた対称性の高い空間だと言える. これらの長方形をそれぞれworld 0,1,2として範囲外に出たら「奈落」/「ワープ」させる条件分岐を書けばわかりやすいかもしれない. 文字の変換についてだが, こちらもASCIIコードを駆使し…

codeIQ 2767

説明が不十分だと思うのだけど, 同じ類似度の時にインデックスの小さい方を先に出さないとtest case2で落ちる. int tn; vector<int> ns; vector<int> tmp; int norm(vector<int> v) { int ans = 0; int until = v.size()-1; FOR(i,1,until) ans+=v[i]*v[i]; return ans; } i</int></int></int>…

codeIQ 1678

count{|a|...}はブロックの返り値でtrueとなるもののみをcountする. b,e=gets.split(',').map(&:to_i);$><<[*b+1..e-1].count{|a|a.to_s(2).reverse==a.to_s(2)}

codeIQ 1630

abc029にも似た, というかほぼ同じな問題があった. 念の為long long intを用いて解いた. void solve(ll n) { n++; ll d = 1, t, ans = 0; while(n>d) { t = d; d *= 10; ans += (n/d)*t+(n%d>t*7?(n%d>=t*8?t:(n%d)%t):0); } cout << ans << "\n"; } int mai…

codeIQ 1621

なんとなくlower_boundでやりたかった. vector<ll> p; void init() { p.resize(10000); fill(p.begin(),p.end(),1LL<<30); int m = 0; p[m++] = 2; for(int i=3;i<=100000;i+=2) { bool flag = true; for(int j=0;p[j]*p[j]<=i;j++) { if(i%p[j]==0) { flag = fa</ll>…

【python】pythonで変数名を取得する

ラムダ式で書いてみた var_name = lambda val : [k for k, v in globals().items() if id(v) == id(val)] a = 1 s = var_name(a)[0]

【c++11】warning: deleting object of polymorphic class type ‘Derived’ which has non-virtual destructor might cause undefined behaviour [-Wdelete-non-virtual-dtor]

自作クラスでdeleteでデストラクタを呼ぼうとしたら以下のような警告が出た。 warning: deleting object of polymorphic class type ‘Derived’ which has non-virtual destructor might cause undefined behaviour [-Wdelete-non-virtual-dtor] delete v;こ…

テンプレートクラスTの内部クラスを呼び出す

共通の内部クラスを持っている複数のクラスをつくって、テンプレートからそれを呼び出したいことがあるかもしれません。その時は以下のように書けばうまく動くでしょう。 #include <iostream> using namespace std; class A1 { public: struct Param { Param(){cout <<</iostream>…

循環少数のプログラム

c

フロイドの循環検出法 - Wikipedia これを使うらしい int f(int n) { int p = 1, q = 1; int s = 0, t = 0; // start : s, goal : t while(1) { p = (p*10)%n; q = (q*10)%n; q = (q*10)%n; if(p==q) break; } if(p!=0) { q = 1; s = 1; while(p!=q) { s++; …

aoj 0503

少し考えれば一番下のものを順番に移動していくしかないことがわかります。 置く場所を#0,#1,#2としてgoalを#0に固定する。1〜nまでのコップが順に並んだものが #0にあるとき => 0 #1にあるとき => 3^n #2にあるとき => 2*3^n したがって下のコードのように…

パスワードで保護されているpdfファイルを解除する

パスワードクラックの方法ではないのであしからず。配布された資料のパスワードを逐一解除するのは手間がかかるし、将来見たい時には忘れているかもしれない。 それに個人的に利用する限りでは、パスワードを解除してもそれほど問題にはならない(あくまで個…

aoj 0502

サイコロ | Aizu Online Judgeクラスを使えば結構綺麗にかけるかもしれないけど、まあ個人的な趣味でしょう。 今回はわかりやすさのために変数を3つ導入したけど、サイコロの現在の姿勢は2変数で書けます。文字数チャレンジをする人はここらへんを切り詰める…

aoj 0501

データ変換 | Aizu Online JudgeC++は便利だけどもcだけで書いたほうが勉強になりそうです。 int main() { int n,m; string s,t; string ans; while(cin >> n) { if(n == 0) break; map<string,string> d; REP(i,n) { cin >> s >> t; d[s] = t; } cin >> m; ans = ""; REP(i</string,string>…

ssh経由でリモートとローカルを判別してLAN内のサーバに接続する

LANの中にgitBucket用のサーバがあり、ノートPCでLANの内側・外側の両方から切り替えを自動化してアクセスしたいと考えて.ssh/configの設定を考えてみた。自分がLANの内側か外側にあるのか判別するにはnslookupを使えばいいことに気が付き以下のように.ssh/c…

arc 059

arc059.contest.atcoder.jp 飴が個,人がのときの答えをとおけば以下の漸化式が成立する。 の部分は最初に計算しておいてのオーダで計算できて結局時間計算量は template <long long modulo> class Modulo { private: long long pow(long long q) { long long a=1; long long y=</long>…

ファイル名を一括置換

ファイル名を一括で置換したいシチュエーションはたくさんあると思うけど、そういう時に逐一find-sedコマンドを使うのが面倒なときはrenameコマンドを使うといいでしょう。 Linuxであればどのディストリビューションにもおそらく入っていると思われます。 使…

abc 040

abc040.contest.atcoder.jp解説を勉強してみた トポロジカルソートの場合の数の算出をbitDPを用いてO(n!)をO(m2^n)にする問題 (頂点集合Sとおいた時のルートの要素数) とおけば以下の漸化式で求まる ただし からへの辺が存在しない 集合をbit列で表し小さい…

ubuntu 16.04のwifiの不具合について

14.04からアップグレードしたのは良いもののwifiのアクセスポイントが見つからなくなってしまった。 復旧方法は以下の通り sudo iwconfigで無線LANのインターフェース名を知りましょう。あとは sudo ifconfig [interface] up sudo service network-manager r…

codeIQ 2529

codeiq.jpf,gは割と簡単だけど,hが面倒. #include <bits/stdc++.h> #define EPS 1e-10 ll power(ll x,ll n){ll a=1;REP(i,n)a*=x;return a;} ll f(double a, double b, double c, double d) { double e = 180-(b+c+d); double f = 180-(a+b+c); a *= M_PI/180; b *= M_PI/18</bits/stdc++.h>…

codeIQ 2717

dfsで全探索する. int n; vector<int> a; int dfs(int k, int sum) { if(k==a.size()) return sum; int x = dfs(k+1,sum+a[k]); int y = dfs(k+1,sum); return abs(n-x)<abs(n-y)? x : y; } int main() { int t; cin >> n; while(cin >> t) a.push_back(t); sort(a.begin(),a.end()); cout << abs(n-dfs(0,0)) <</abs(n-y)?></int>…

abc 040

abc040.contest.atcoder.jpunion findを使いましょう. 新しい道からどんどん素集合データ構造を更新して行って,その時の各クエリが要求するノードが含まれる集合の濃度(要素数)を記憶,あとで出力すればとける. unionfind自体は知っていてなんとなく使う気が…

abc 039

abc039.contest.atcoder.jp白の周囲を白にして、その後黒の周囲を黒にして元に戻るか判定する. int h,w; int a[100][100]; int b[100][100]; int c[100][100]; bool range(int x, int y) { return x >= 0 && x < h && y >= 0 && y < w; } int main() { cin >…

abc 037

abc037.contest.atcoder.jp DPの問題. 点を始点とする場合の数はその点の周囲のマス+1になる.あとは再帰的に計算してメモ化すればできる. ll T[1010][1010]; ll dp[1010][1010]; int h, w; ll f(int x, int y, ll p) { if(x<0||x>=h||y<0||y>=w) return 0; i…

ubuntuで「画面だけ」オフにしたい

ノートpcにubuntuを入れているのだけど, 開いた状態のまま,サスペンドせずに画面だけオフにするには以下のコマンドを打てばいい $ xset dpms force standby これで強制的にスタンバイ状態にできる. もしノートpcを閉じてもサスペンドしたくなければ以下を参…

abc 038

LISの二次元バージョン.x座標でソートしてy座標のLISを求めればいい ここでうまいと思ったのはy座標を負にすること. 問題では狭義単調増加の最長増加列を求めさせているので,x座標が同じだと条件に合わない. そこで負にすることで絶対値が大きい順に並べこれ…

codeIQ 2796

codeiq.jp期待値を計算すればよい あとはargminなので以下のように簡略化できる. p [*1..n=eval(*$<)].max_by{|t|(n-t).to_f*(n+t-1)/(n+1-t)}

codeIQ 2791

codeiq.jp例によってdfsとメモ再帰で解けます. struct P { int x; int y; P(){}; P(int x,int y):x(x),y(y){}; P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;} P operator+=(const P&q){x+=q.x;y+=q.y;return *this;} bool operator!=(const P&…

utroam-1xにubuntuから接続する

公式にページがなかったので今後のために備忘録を記します。 Windows7の接続方式と割と似ているのかな... utroam-1xを選択して以下のwifiセキュリティの画面に飛んで以下のように設定するだけ簡単な各項目についての説明について wpa2-エンタープライズ 無線…

c++11でグラフ理論

競プロで頻繁にグラフが絡む問題が出題されます. 隣接リストvector<vector<Edge>>を継承してグラフの様々な値を求めることができるクラスを作ってみました. 使い方 ・宣言 graph<T> g((int)n): 重みの型がTの,頂点の数がn個の隣接グラフの宣言. ・辺の挿入 g.direct(src,dst,</t></vector<edge>…

c++11で計算幾何

競プロでは平面幾何の問題が結構出題されます. c++ならば複素数を扱うcomplexを使ってもいいのだけどx,yではなくreal,imagになるのがなんとなく気持ちが悪いので自作してみました. computer geometry

arc 051

arc051.contest.atcoder.jp A問題 円の中心が長方形の内側か外側にあるかで場合分けすれば解けます. int main() { P p; double r; cin>>p.x>>p.y>>r; P q1,q2; cin>>q1.x>>q1.y>>q2.x>>q2.y; P q = (q1+q2)/2; P q3(q1.x,q2.y); P q4(q2.x,q1.y); bool red, …

codeIQ 2769

よくよく考えればルートの長さはたかだか2種類しかないとわかる. a,b=gets.split(',').map &:to_i p x=a.lcm(b),x==a*b ?x:x*2

abc 034

c問題 abc034.contest.atcoder.jp前にやった剰余のやつ. フェルマーの小定理を用いて逆元を求める. template <long long modulo> class Modulo { private: long long inv() { long long p = mod - 2; long long ans = 1; for(;p != 0;p >>= 1LL) { if(p&1LL)ans=(ans * x) % mo</long>…

c++11でモジュロ演算

競プロでモジュロ演算が面倒だったのでこれを簡単に扱えるクラスを作ってみた. 剰余類環と言われているやつで特に素数を法にするものは剰余体と呼ばれ以下のように積に対して逆元が定義できる. よく10^9+7で割った余りを求めさせたりするのでこれでmod周りの…

abc 033

abc033.contest.atcoder.jp解説が詳しい 各点からすべての点への線分を考え角度を求める. 角度を求めた後, 鈍角と直角の数を数える. ここでミソなのはx軸のx特異点)でこれはすべての角度に2πを足して二分探索すればとける. int main() { ll n; cin >> n; ll …

abc 036

d問題 abc036.contest.atcoder.jpdfsとメモ再帰化でできる…はずだったのにlonglongとintを使い間違えて無事終了 #include <bits/stdc++.h> #define SIZE 300005 #define MOD 1000000007LL #define INF 1 << 29 #define LLINF 1LL << 60 #define REP(i,n) for(int i=0;i</bits/stdc++.h>

aoj DPL_3_B

最大長方形 | 動的計画法 | Aizu Online Judge最大長方形を求めさせる問題. こちらを参考に応用する. ヒストグラムの中の最大長方形を求める問題はlog(n)のオーダで求まる. あとはそれを行について行えばいいので計算量はlog(w*h)のオーダーで行ける. struct…

aoj DPL_2_B

Chinese Postman Problem | Aizu Online Judge Spaghetti Source - 無向中国人郵便配達問題 ll chinesePostman(const Graph &g) { ll total = 0; vector<int> odds; REP(u, g.size()) { for(auto e : g[u]) total += e.cost; if (g[u].size() % 2) odds.push_back</int>…

aoj DPL_2_A

Traveling Salesman Problem | Aizu Online Judge 巡回セールスマンの問題 bit dpを使う問題 bit列にした時1を訪れていない頂点, 0を訪れた頂点としてdpを用いる. 計算量はO(n^2*2^n) int n; int d[15][15]; int dp[1<<15][15]; void solve() { REP(i,(1<<n)) fill_n(dp[i],n,INF); dp[(1<<n)-1][0] = 0; DOWN(i,(1<<n)-2,0) REP(v,n) REP(u,n) if(!(i>>u&</n))>…

codeIQ 2740

正規表現 (Ruby 1.9.3) キャプチャを使ってあげれば一瞬で解ける. x=/(?<a>.)(?<b>.)\k<a>/;$<.map{|s|s=s.sub(x,$2)while x=~s;$><</a></b></a>

codeIQ 2749

オセロのAIと同じ要領でできる. 初手判定に要注意 int a[25]; int dx[] = {1,1, 1, 0,-1,-1,-1,0}; int dy[] = {1,0,-1,-1,-1, 0, 1,1}; vector<string> split(const string &str, char delim) { istringstream iss(str); string tmp; vector<string> res; while(getline(iss</string></string>…

codeIQ 2730

n=(a=$<.map &:to_s).count{|s|s[0]=='#'} puts"code:#{a.count-n}\ncomments:#{n}"

aoj DPL_1_E

Edit Distance (Levenshtein Distance) | Aizu Online Judge レーベンシュタイン距離を求めるアルゴリズム. 下が詳しい レーベンシュタイン距離 - Wikipedia dpでいける. int solve(string s, string t) { int sn = s.size(); int tn = t.size(); vector<vector<int>> dp</vector<int>…

aoj DPL_1_D

Longest Increasing Subsequence | Aizu Online Judge まずはTLEする回答 dp[i] := (i番目の数まで使った時の最長部分増加列の大きさ) と定義しnについて2重ループを回せばO(n^2)で解ける. すなわちが以前の数より大きければ のような漸化式が書ける int mai…

aoj DPL_1_C

Knapsack Problem | Aizu Online Judge 0/1ナップサック問題とループの向きが単に逆になったパターン. 今回は中間結果の情報は破棄しているが問題によっては必要になる. #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i<n;i++) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define DOWN(i,b,a) for(int i=b;i>=a;i--) using namespace std; int main() {</n;i++)></bits/stdc++.h>…

aoj DPL_1_B

0-1 Knapsack Problem | Aizu Online Judge 前にも書いたが0/1ナップサック問題には大きく分けて3つの解法がありそのうちdpである2つの解法で解いてみた dp[i][j] := (i番目の品物まで使った時の合計重さjを実現できる最大合計価値) dp[i][j] := (i番目の品…