Tamflexの貯蔵庫

やる気のない備忘録

c++

aoj 0039

ローマ数字 | Aizu Online Judge よく読めばできる. int main() { cin.tie(0); ios::sync_with_stdio(false); string s; map<char,int> T; T['I'] = 1; T['V'] = 5; T['X'] = 10; T['L'] = 50; T['C'] = 100; T['D'] = 500; T['M'] = 1000; while(cin >> s) { int ans </char,int>…

aoj 0038

ポーカー | Aizu Online Judgeポーカーの問題. 似たようなものに麻雀の得点計算プログラムがあり,既出だと思うけど, いつか作ってみたい. void solve(int a1, int a2, int a3, int a4, int a5) { int a[13]; fill_n(a,13,0); a[--a1]++;a[--a2]++;a[--a3]++;…

aoj 0037

格子状の経路 | Aizu Online Judgeあまり見慣れない問題で面食らってしまった. 各点に対して壁の方向を保存する方法に関して, 構造体を作るのがあまり綺麗でないと思ったので, 4bitの数で表現することにした. これでn*nの問題に対しても高速に対処できそう. …

aoj 0036

平面の中の図形 | Aizu Online Judgeやるだけだがエレガントにかけない. 実際図形の認識は画像認識で重要で平面を走査して探索するのだけれども, 今回はそんなに複雑な問題ではないのでこの程度のソースでもできてしまう. テトリスAIとか作るときに役に立ち…

aoj 0035

凹みの検知 | Aizu Online Judge幾何の問題 対角線となる二直線の交差を確認する解法 対角線で三角形2つに分割し面積で求める開放 が等が考えられる. 今回は後者で解いてみた.でも本当はrubyのコードにあるように https://www.jaist.ac.jp/~uehara/course/20…

aoj 0033

玉 | Aizu Online Judge深さ優先探索で全探索する方法と貪欲的にやる方法がある. 後者のほうが計算量が少なそうだけど, 練習のためdfsでもやる. 貪欲的 int a[10]; bool solve() { int s = 0, t = 0; REP(i,10) cin >> a[i]; REP(i,10) { if(a[i] > s) s = a…

aoj 0032

Plastic Board | Aizu Online Judgeひし形とか長方形とか懐かしい... int main() { cin.tie(0); ios::sync_with_stdio(false); int x, y, z; int a1 = 0,a2 = 0; while (~scanf("%d,%d,%d",&x,&y,&z)) { if(x*x+y*y==z*z) a1++; if(x==y) a2++; } printf("%d…

aoj 0031

Weight | Aizu Online Judge ビット演算の練習 int main() { cin.tie(0); ios::sync_with_stdio(false); int w; while (~scanf("%d",&w)) { string str = ""; FOR(i,0,9) if(w>>i & 1) { char tmp[256]; sprintf(tmp,"%d ",1<

aoj 0030

Sum of Integers | Aizu Online Judge高々2^10=1024回計算する int n, s; int ans; void solve(int num, int m, int sum) { if(sum > s || m > 10) return; if(num == 0) { ans += (sum == s); return; } solve(num-1,m+1,sum+m); solve(num,m+1,sum); } int…

codeIQ 2669

codeiq.jp「やるだけ」なのかもしれないけどどうもエレガントに書けない. 問題では分割していたけれど, 逆に条件に合うような長方形を生成すれば高々O(2^n)のコストで済み, また条件に合わないときに枝刈りすればもっと計算量は減らせる. mは1000以下の縛り…

aoj 0028

Mode Value | Aizu Online Judge最頻値を求める問題.setみたいな連想配列を使っても良かったかもしれないけど面倒なのでこれで済ませた. 別の言語だともっと楽にかけるのかなあ. int main() { vector<int> a(101,0); int x, tmp = 0; while(~scanf("%d",&x)) a[x]</int>…

abc 032

D問題 N void solve1() { int n1 = N/2; int n2 = (N + 1)/2; vector<pair<ll,ll> > a; REP(i,1<</pair<ll,ll>

c++でソート

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

abc 019

D問題 abc019.contest.atcoder.jpdouble sweepというアルゴリズムを用いる(らしい) 任意の頂点から最も離れた頂点をとした場合、木の直径はから最も離れた頂点までの距離となる。背理法によって簡単に示せる。 これによって回の検索で直径が計算される。 int…

abc 020

D問題 abc020.contest.atcoder.jp を求めよ。 15点解法 ll gcd(ll x, ll y) { if(x == 0 || y == 0) return max(x,y); ll a = max(x,y); ll b = min(x,y); return gcd(a%b,b); } ll lcm(ll x, ll y) { return x * y / gcd(x,y); } int main() { cin.tie(0); …

abc 031

D問題 abc031.contest.atcoder.jp数字iがa[i-1]の長さの文字列に対応しているとして、深さ優先探索で解く。最大9種類のパターンに対しそれぞれ最大3文字なので3^9 = 19683通りしかないので時間内に解けそう。判定はそれぞれのデータセット(v,w)に対して Σ{i …