アルゴリズム
atcoder.jp 2、3回解いているが、なかなか覚えられないのでメモ。 マンハッタン距離が出たら、ひとまず45度回転を考えるのは覚えていた。 45度回転の方法は (X, Y) = (x-y, x+y) を計算すること。 45度回転すると、距離の領域が正方形になり、処理がしやすく…
atcoder.jp ソートして、最小値と最大値に対して、操作を繰り返せば良いかなと思ったが、うまくいかずにTLE。 答えに上限があることは分かったが、２分探索する発想はできなかった。 典型問題の「答えで２分探索する」は思いつきたかった。 そのあとの判定問…
atcoder.jp 末尾がT[i]個の0になっている整数を作っていけば良いことは分かったが、作り方の方針が誤っていた。 「2T[i] で割り切れて、2T[i]+1で割り切れない整数」と言い換えられるところは典型っぽい考え方か？ 上記の条件に加えて、「A[i-1]より大きい整…
atcoder.jp 浮動小数点の理解があまかったせいでACできなかった。 100倍して計算結果を100で割るところまでは思いついたが、キャストの部分でも誤差が出ることを理解していなかった。 例えば 0.79の場合、２進数で表すと 0 .1100101000111101011100001010001…
atcoder.jp 1の位の周期性を考える。 BCは繰り返し二乗法で求めて、周期の長さで割れば良い。 周期の中でどの位置にあるのかを求めるのが少し苦戦してしまった。 例えば、3 の周期は「3 9 7 1」の長さ4であり、39 の場合は周期により、1となる。単純に 9 % 3…
atcoder.jp 茶diffらしいが、実感としては緑diffくらいに感じる。 値の範囲にマイナスが含まれているので、場合分けや反転させる処理が思いつけなかった。 値の範囲が正のみ(D>0 && A,X > 0)であれば、特に難しいことはない。 負の場合(D<0)、反転するには、…
atcoder.jp 結構雰囲気で解いてしまった。 まずceil(AiM/N)でBiをざっくり求める。 Biの合計値を算出したら、Mと差分が出るので、max(BiN - AiM)が最小になるように、Biの値を減らしていく。 max(BiN - Ai*M) が大きい順に減らしていきたいので、PriorityQue…
atcoder.jp 表か裏かで遷移する動的計画法。 dp[i][j] := カードi,...,iまでの和をjにできるなら1、そうでないなら0 dp[i][j] = 1 の場合、以下の遷移をする。 - dp[i+1][i+a[i]] = 1 - dp[i+1][i+b[i]] = 1 dp[N][S]が1であればYes、そうでないならNo。 ま…
atcoder.jp UnionFindだろうと思ったが、ACLの使い方の理解が浅かったので、BFSで解いてしまった。 void solve(long long N, long long M, std::vector<long long> u, std::vector<long long> v){ vvl G(N+9); REP(i, M) { G[u[i]].push_back(v[i]); G[v[i]].push_back(v[i]); } vb</long></long>…
atcoder.jp 再帰的なDFS。 パッと書けるようにしたい。 void dfs(string S, ll n) { if (n==0) { cout << S << endl; return; } REP(i, 3) { S.push_back('a'+i); dfs(S, n-1); S.pop_back(); } } void solve(long long N){ dfs("", N); }
perlでBresenhamアルゴリズムを書いてみました。 考え方は下記のような感じ。 xが増えたら、だけyが増える 整数単位の話なので、が1以上になったら、yが1増える じゃなくて、で比較すれば、割り算が無くなって便利 use strict; use warnings; bresenham_line…
ツイートストリームをベイジアンフィルタでカテゴリ分けしていく様子を見てみました。 カテゴリとしてハッシュタグを利用します。 ハッシュタグが付いているツイートは、フィルタの学習テキストとなります。 ハッシュタグが付いていないツイートは、どのハッ…
WEB+DB PRESS Vol.56作者: 赤松祐希,紀平拓男,牧大輔,西林孝,中島聡,中島拓,角田直行,はまちや2,舘野祐一,きしだなおき,和田裕介,伊藤直也,大沢和宏,塙与志夫,増井俊之,ミック,WEB+DB PRESS編集部出版社/メーカー: 技術評論社発売日: 2010/04/24メディア: 大…
バブルソートを行なうプログラムをperlで書いてみました。 use strict; use warnings; { my @a = (8,4,3,9,7,6,5,2,1); print "===================\n"; print join(',',sort(@a)) . "\n"; } sub bubble_sort { my @a = @_; my $a_length = @a; for (my $i =…
配列に入っている式から四則演算行なうプログラムをperlで書いてみました。 演算子とカッコの優先度を考慮しながら計算するために、逆ポーランド記法に直して計算するようにしています。 use strict; use warnings; { cal(qw|5 + 4 - 3|); cal(qw|5 + 4 * 3 …
ユークリッドの互除法をperlで書いてみました。 use strict; use warnings; { gcd(160,48); } sub gcd { my ($x, $y) = @_; my $c; while ($x > 0 && $y > 0) { if ($y > $x) { $c = $x; $x = $y; $y = $c; } print "$x, $y\n"; $c = $y; $x = $x - $y; $y =…
クイックソートを行なうプログラムをperlで書きました。 use strict; use warnings; { my @a = qw/3 2 0 5 8 3 4 1 3 2/; print join(',',@a) . "\n"; print "===================\n"; print join(',',sort(@a)) . "\n"; } sub pivot { my ($ar, $i, $j) = @…
perlのsort関数はマージソートを使っているということなので、 勉強のため、perlでマージソートするプログラムを書きました。 use strict; use warnings; { my @a = (8,4,3,9,7,6,5,2,1); print join(',',@a), "\n"; print "===================\n"; print j…
