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

Tamflexの貯蔵庫

やる気のない備忘録

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>…

【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>…

aoj 0503

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

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>…

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>…

abc 040

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

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>…

abc 040

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

abc 038

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

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&…

c++11で計算幾何

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

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_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))>…

aoj ALDS1_14_D

Multiple String Matching | Aizu Online Judge 文字列Sの接尾辞配列を構築すると文字列Tの検索が二分探索で行えるためO(|T|log|S|)のオーダーで行える. 接尾辞配列の構築にかかるコストはO(|S|(log|S|)^2)なので何度もTの検索を行う場合有用である. #includ…

aoj ALDS1_14_C

Pattern Search | Aizu Online Judge二次元配列の効率的なハッシュの精製方法について配列 から以下のような行方向のハッシュの配列 を生成する. この時 のように計算すればO(h)のオーダーでハッシュが計算できる.同様に以下のような列方向のハッシュの配列 …

aoj 0099

ワカサギ釣り | Aizu Online Judge priority_queueは最大値を一番上に持ってくるSTLでこれを使えばとても便利. データごとにpqに挿入し現在の魚の数を集計. 現在の状態と一致するものの中で最大のものを出力し残りはpopする. こうすることによって古いデータ…

codingame - Dwarfs standing on the shoulders of giants

メモ再帰によって簡単に解ける template<typename T> struct Edge { int dst; T w; Edge() {}; Edge(int dst): dst(dst) {w=1;}; Edge(int dst, T w): dst(dst), w(w) {}; bool operator < (const Edge &e){return w != e.w ? w > e.w : dst < e.dst;} }; typedef vector<Edge<ll></edge<ll></typename>…

aoj 0081

線対称の位置にある点 | Aizu Online Judge回転行列を利用してといてみた. class P { public: double x,y; P(){};P(double x,double 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;ret…

aoj 0076

宝探し | Aizu Online Judge 久々の投稿 複素数を使うと以下のような漸化式になる あとはやるだけ int main() { int n; complex<double> T[1001]; T[0] = 0.0; T[1] = 1.0; FOR(i,2,1000) T[i] = complex<double>(1.,1./sqrt(i-1))*T[i-1]; while(cin >> n, n!=-1) { printf(</double></double>…

aoj 0074

ビデオテープ | Aizu Online Judge 更に短いコードのためもう一度cから勉強したほうがいいかもしれない. #include <bits/stdc++.h> #define A printf("%02d:%02d:%02d\n",a/e,a/d%d,a%d); main(){int h,m,s,a,d=60,e=d*d;for(;scanf("%d%d%d",&h,&m,&s),~h;){a=e*2-h*e-m*d-</bits/stdc++.h>…

aoj 0072

灯篭 | Aizu Online Judge 最小全域木のコストを求めさせる問題. プリムのアルゴリズムを用いる. Spaghetti Source - 最小全域木 (Prim) typedef int Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src)…

aoj 0068

輪ゴムで囲んだ釘 | Aizu Online Judge 凸包を求めるアルゴリズムが蟻本に乗っていたのでそのまま書いてみた. class P { private: double add(double a,double b){if(abs(a+b)<1e-10*(abs(a)+abs(b)))return 0;else return a+b;} public: double x,y; P(){};…

aoj 0062

一番下の数 | Aizu Online Judge やるだけ void solve(string s) { string t; while(s.size()>1) { t = ""; REP(i,s.size()-1) t+=to_string((s[i]+s[i+1]-2*'0')%10); s = t; } cout << s << endl; } int main() { string s; while(cin >> s) solve(s); ret…

aoj 0041

数式 | Aizu Online Judge いわゆる「10ゲーム」の除算がないもの. もっと簡潔に書けるかもしれないけど, どうも煩雑になってしまう. あとnext_permutaionを使う前はsortするのを忘れてはいけない. map<string, int> generate(vector<int> v) { map<string, int> T; if(v.size() == 1) { if(</string,></int></string,>…

c++でソート

C++でソートするときの備忘録 参考文献 C++(ソートの補足) - アルゴリズム講習会stlを用いてソートしたいとき少し困ったので書き留める。 基本的にはvectorに入れてsortすれば一番目の要素の小さい順に二番目の要素が小さい順にsortされる。 自作のstruct…