Tamflexの貯蔵庫

やる気のない備忘録

c++

codingame - Stock Exchange Losses

int main() { ll n; cin >> n; ll ans = 0, m = LLINF; vector<ll> a(n); REP(i,n) cin >> a[i]; DOWN(i,n-1,0) { m = min(a[i],m); ans = min(m-a[i],ans); } cout << ans << endl; return 0; }</ll>

aoj 0082

メリーゴーランド | Aizu Online Judge 愚直そのもの int main() { int a[] = {1,2,1,2,1,4,1,4}; int p[8],i=0; while(cin >> p[(i++)%8]) { if(i%8==0) { int ans=0, md = 1e5, dist; REP(j,8) { dist = 0; REP(k,8) dist+=(p[k]>a[(k+j)%8])?p[k]-a[(k+j)…

aoj 0080

3乗根 | Aizu Online Judge やるだけ void solve(const double q) { double a = q*0.5; while(fabs(a*a*a-q)>=1e-5*q) a -= (a*a*a-q)/(3*a*a); printf("%lf\n",a); } int main() { double q; while(cin>>q,q>0) solve(q); return 0; }

aoj 0078

魔方陣 | Aizu Online Judge やるだけ int main() { int n; while(cin>>n,n) { vector<vector<int> > T(n,vector<int>(n,0)); int k=1, x=n/2+1, y=n/2; while(k<=n*n) { while(T[x][y]!=0) { x = (x+1)%n; y = (y-1)%n; y = y<0? y+n : y; } T[x][y] = k; x = (x+1)%n; y = (</int></vector<int>…

aoj 0077

ランレングス | Aizu Online Judge やるだけ int main() { string s, t = ""; while(cin >> s) { int i = 0; while(i < s.size()) { if(s[i]=='@'){REP(j,s[i+1]-'0')t+=s[i+2];i+=3;} else{t+=s[i];i++;} } cout << t << endl; t = ""; } return 0; }

aoj 0073

四角すいの表面積 | Aizu Online Judge #include <bits/stdc++.h> main(){int x,h;while(scanf("%d%d",&x,&h),x)printf("%f\n",x*(x+sqrt(4*h*h+x*x)));} $<.map(&:to_i).each_slice(2){|a|puts (x=a[0]**2)+Math.sqrt(x*(x+4*a[1]**2))if a[0]!=0}</bits/stdc++.h>

aoj 0071

爆弾の連鎖 | Aizu Online Judge x,y座標の変換に注意. int a[8][8]; void f(int x, int y) { a[x][y]=0; for(int i=1;i<=3;i++) { if(x+i>7) break; if(a[x+i][y]) f(x+i,y); } for(int i=1;i<=3;i++) { if(x-i<0) break; if(a[x-i][y]) f(x-i,y); } for(in…

aoj 0070

組み合わせの個数 | Aizu Online JudgedfsでやるとTLEしてしまった... int a[10]; int n, s, cnt; void dfs(int m,int r) { if(r > s) return; if(m==n+1) { if(r==s) cnt++; return; } FOR(i,0,9) { if(a[i]) { a[i] = 0; dfs(m+1,r+m*i); a[i] = 1; } } } …

aoj 0067

島の数 | Aizu Online Judgeやるだけ. int a[144]; void flip(int x, int y) { if(x>11||y>11||x<0||y<0) return; if(a[x+y*12]) { a[x+y*12] = 0; flip(x+1,y); flip(x-1,y); flip(x,y+1); flip(x,y-1); } } void solve() { int cnt = 0; REP(i,144) if(a[i…

aoj 0066

三目並べ | Aizu Online Judge やるだけ. char solve(string s) { REP(i,3) { if(s[i*3]==s[i*3+1]&&s[i*3]==s[i*3+2]&&s[i*3]!='s') return s[i*3]; if(s[i]==s[i+3]&&s[i]==s[i+6]&&s[i]!='s') return s[i]; } if(s[0]==s[4]&&s[4]==s[8]&&s[4]!='s') retu…

codeIQ 2685

https://codeiq.jp/q/2685(404になっていたので説明すると,順次追加される数字に対し, それまで追加された数の集合のメジアンを求めさせる問題, だったはず)参考にしたのはこれ↓ でもこれだと負の数に対応できないので無理やり大きい数を足して調整している.…

codeIQ 2683

F(n) = [n*log10(n)] ([x]はxより大きい最小の整数) と定義されるとき G(m) = n (F(n) = m) となるようなnを求めよ, という問題. 2≦m≦1e10なので大体nの範囲は1~1e9程度, なので多めに見積もって1~1e10の範囲を二分探索すれば一瞬で求まる. void solve(ll …

aoj 0048

階級 | Aizu Online Judge「やるだけ」なのに何故か頑張ってしまった...(277 byte)上には上がいるみたいです(T T) AIZU ONLINE JUDGE #include <bits/stdc++.h> main(){char* s[]={"light fly","fly","bantam","feather","light","light welter","welter","light middle","m</bits/stdc++.h>…

aoj 0047

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0047scanfの使い方の復習. int main() { cin.tie(0); ios::sync_with_stdio(false); char c1, c2; int a[3] = {1,0,0}; while(~scanf("%c,%c\n",&c1,&c2)) swap(a[c1-'A'],a[c2-'A']); REP(i,3) i…

aoj 0044

最小の素数と最大の素数 | Aizu Online Judge全探索してからやったけど, 直近だけ探索すればよかったかも. bool prime(int n) { if(n<=1) return false; if(n==2) return true; if(n%2==0) return false; for(int i=3; i<=sqrt(n); i+=2) if(n%i==0) return …

競技プログラミング 備忘録

c++

競技プログラミングでつよい人のコードを見ると, 冒頭に大量のマクロや一行で記された関数の羅列を見かけることが多い.競プロにおいてはコード自体の保守性や拡張性よりも,アルゴリズムそのものに対する理解,およびその実装力が求められるので本質的なところ…

aoj 0043

パズル | Aizu Online Judge いわゆる麻雀. 清一色の状況下, 一向聴かどうか判定し上がり牌を出力する. dfsで順子・暗刻を落としていき,最後に対子が残ればtrueとなるようにすればよい. 13枚しかないので1〜9について仮想的な1枚を加え,それぞれ「上がり」か…

aoj 0042

泥棒 | Aizu Online Judge 0-1ナップサック問題. abc 032 - Tamflexの貯蔵庫 でも書いたように大きく3種類の解法が考えられる. 物体の集合を2分割し組み合わせをすべて試す i番目までの物体を用いたとき重さjを実現できる最大の価値をdp[i][j]とおく i番目ま…

テンパズル

c++

テンパズル - Wikipedia数式 | Aizu Online Judge においては除算が含まれなかったが, 除算も含めて計算できるものを作成した. まず除算について, すべて整数なので計算結果は0除算の時を除き有理数になることが保証される.したがってpairで分母分子を保存し…

aoj 0040

アフィン暗号 | Aizu Online Judge初歩的な暗号. シーザー暗号に毛の生えた程度. 今回も問題そのものよりI/Oに手間取ってしまった. まず空白で区切らないでcinする方法について,これはgetlineを用いる.一番目にnをとるのでcin.ignore()でバッファを消去する…

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以下の縛り…