Tamflexの貯蔵庫

やる気のない備忘録

Aizu Online Judge

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

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

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番目の品…

aoj DPL_1_A

Coin Changing Problem | Aizu Online Judge コイン問題 貪欲法では解けないのでDPを使う. dp[i][j] := (i枚目までのコインを使った時の金額jの最小実現枚数) とすれば計算量O(nm)で解ける #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 INF 1 << 30 using namespace std; int main() { int n, m; cin >> n …</n;i++)></bits/stdc++.h>

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 ALDS1_14_B

String Search | Aizu Online Judge 逐一比較だとTLEしてしまったがsubstrなるものを使うと通る. アルゴリズム的には同じオーダなのだけど内部処理で何かが違うのだろう. std::string::substr - C++入門 #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++) using namespace std; int main() { string t,p; cin>>t>>p; int</n;i++)></bits/stdc++.h>…

aoj ALDS1_14_A

Naive String Search | Aizu Online Judge やるだけ a,b=$<.map{|s|s.chomp};(c=a.size).times{|v|a[v..c-1]=~/^#{b}/&&p(v)}

aoj 0099

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

aoj 0097

整数の和 | Aizu Online Judge 動的計画法を用いてやる. dp[i][j] := (i個の異なる0〜100の数を用いて和jを実現する場合の数) あとは0〜100まで順に更新する. ここでポイントはdp[i][j]の更新の順序で必ずiについて逆順で更新しなければならない. なぜならば…

aoj 0096

4つの整数の和 | Aizu Online Judge 動的計画法を使ってやる dp[i][j] = (i+1個の数を使って和jを実現する場合の数) あとは適当に1000までという条件を組み込めばOK #include <bits/stdc++.h> #define REP(i,n) for(int i=0;i</bits/stdc++.h>

aoj 0095

ワカサギ釣り | Aizu Online Judge ホントは$> gets;x,y=$<.max_by{|s|eval s.split*'*-1+101*'}.split;puts x+' '+y

aoj 0094

土地面積 | Aizu Online Judge 一文字のリテラル/文字列リテラルは?をつけることで実現できる(ex 'd'=?d) リテラル (Ruby 2.0.0) evalをつければ簡単に計算できる. p eval(gets.split*?*)/3.30578

aoj 0092

正方形探索 | Aizu Online Judge 動的計画法の問題. dp(i,j)を(i,j)を右下の頂点とするの最大サイズと定義し以下のような漸化式を計算すれば良い. dp(i,j) = min(dp(i-1,j),dp(i-1,j-1),dp(i,j-1))+1 あとは最大値を求めればよい. int main() { string s; in…

aoj 0091

にじみ | Aizu Online Judge dfsを使うところまでは良かったが探索の仕方がまずかった. まず最初に試したのは全ての探索木の節/葉において全部(8*8)を探索する方法でこれだとTLEしてしまった. 自力では解けなかったので先人達の答えを拝見させていただいた. …

aoj 0090

シールの重なり | 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;r…

aoj 0089

菱形上の最短経路 | Aizu Online Judge 添字の扱いが厄介 vector<string> split(const string &str, char delim) { istringstream iss(str); string tmp; vector<string> res; while(getline(iss, tmp, delim)) res.push_back(tmp); return res; } int main() { vector<int> v; st</int></string></string>…

aoj 0087

逆ポーランド記法 | Aizu Online Judge やるだけ vector<string> split(const string &str, char delim) { istringstream iss(str); string tmp; vector<string> res; while(getline(iss, tmp, delim)) res.push_back(tmp); return res; } int main() { string s; while(getl</string></string>…

aoj 0086

パトロール | Aizu Online Judge 一筆書き可能か判定する問題, すなわちグラフGが与えられた時そのグラフがオイラー路であるか判定すればよい. オイラー路となる条件は, すべての頂点の次数が偶数⇔オイラー閉路(オイラーグラフ) 奇数次数の頂点が2つで残りが…

aoj 0085

ヨセフのおイモ | Aizu Online Judge 愚直にやるとこうなる main(n,m,i,c,p){while(scanf("%d %d",&n,&m),n){int a[1010]={};c=p=0;while(c++!=n){for(i=0;i++

aoj 0084

検索エンジン | Aizu Online Judge splitで指定文字を除くのがミソ $>Errorになるのでこれで妥協 puts gets.split(/[ ,.]/).select{|v|v[2]&&!v[6]}*' '

aoj 0083

西暦と和暦の変換 | Aizu Online Judge 無理やり感ある #!ruby -nrdate a=Date;y,m,d=$_.split.map &:to_i s=((b=a.new(y,m,d))

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

BMI | Aizu Online Judge (64byte) $<.map{|s|a,b,c=s.split(',').map &:to_f;p a.to_i if b/c**2>=25} すごい答え(42byte) #!ruby -n i,w,h=eval"[#$_]" w/h/h<25||p(i) $_について module Kernel (Ruby 2.0.0) オートスプリットを利用した答え(52byte) #!r…

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

aoj 0065

AIZU ONLINE JUDGE 今ひとつ配列について分かっていなかったので補足. slice_afterはEnumeratorを返す.Enumeratorは配列の操作に関する様々なメソッドを提供するクラスである. 便利な半面このままでは値が読み込めないので,値が欲しいときは直前に*をつける…

aoj 0064

readで入力を文字列として渡してくれる. instance method IO#read (Ruby 1.9.3) evalは文字列を式として評価する. これで勝つる!?(29byte) p eval$<.read.scan(/\d+/)*"+" 上には上がいたようです.(6byte) p 5450 これセコくない??

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 0061

チームの順位 | Aizu Online Judge setを使って無理やり数えるという暴挙 require 'set' T,U={},{};S=Set.new while true a,b=gets.split(',').map &:to_i break if a==0&&b==0 T[a]=b;S.add(b) end T.each{|k,v|U[k]=S.count{|a|a>v}+1} $<.map{|l|p U[l.to…

aoj 0060

カードゲーム | Aizu Online Judge これでも頑張った方(111byte) #!ruby -n l=$_.split.map &:to_i;a=[*1..10];l.each{|v|a[v]=nil};puts a.count{|v|v&&l[0]+l[1]+v<=20}<4?'NO':'YES'

aoj 0059

長方形の重なり | Aizu Online Judge #!ruby -n a,b,c,d,x,y,z,w=$_.split.map &:to_f;puts z

aoj 0058

直交 | Aizu Online Judge やる気のないコード(110byte) #!ruby -n l=$_.split.map(&:to_f) puts ((l[3]-l[1])*(l[7]-l[5])+(l[2]-l[0])*(l[6]-l[4])).abs<1e-12? 'YES': 'NO' すごい答え(91byte) $<.map{|s|a,b,c,d,e,f,g,h=s.split.map(&:to_f);puts ((d-b…