2016-01-01から1年間の記事一覧
年末で会社が休みなので、自分のために今年読んだり読まなかったりした技術書を整理します。 目次 全部読んだ 半分以上読んだ 半分未満しか読んでない 全部読んだ オブジェクト指向でなぜつくるのか 評価: ★★★★☆ 自分用メモ: もう一度読むなら9章から 概要・…
問題概要 りんごさんは1秒で1枚クッキーを焼ける りんごさんはA秒かけて今あるクッキーT枚を全て食べることができ、それによって1秒でT枚クッキーを焼けるようになる N枚以上のクッキーを最短何秒で焼けるか リンク 部分点解法 N <= 106なので、O(N)かO(N lo…
ライブラリとして持ってはいたけど、あまり理解していなかったDinic法について学び直したのでメモ。 Dinic法とは Dinic法は、最大フロー問題を効率的に解くためのアルゴリズムである。 最大フロー問題については、蟻本第二版188ページ参照。 概要 N個のノー…
問題概要 リンク 略 解法 コメント #define MAX_N 16 int N,M; ll dp[1 << MAX_N]; bool edge[MAX_N][MAX_N]; int main(){ ios::sync_with_stdio(false); cin >> N >> M; REP(i, M) { int x, y; cin >> x >> y;x--;y--; edge[x][y] = true; } // dp[mask]:=m…
POJは制約が多すぎる (unordered_mapが使えなかった) 問題概要 リンク N種類の文字で構成された長さMの文字列Sが与えられる この文字列にいくつかの文字を追加、あるいは削除して回文にする i番目の文字を追加するには、a_iのコスト、削除するにはb_iのコス…
問題概要 リンク 略 解法 ある車xに着目する時、あるエッジの両端u,vについて、min(u,v) >= xの時、その道にまだ車が止まっていないため通行可能である 通行可能な道をUnion Findでマージし、same(S, x)がtrueとなれば到達可能である この制約はxが大きくな…
蟻本章末問題 問題概要 リンク ある数字Nが与えられる Nを2の累乗の数の和で表す 例えば4なら 4 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 そのような組み合わせは何通りか 解法 dp[i] := N=iの時の組み合わせの数 dp[i] = dp[i/2] + dp[i-1] then i mod 2=0 dp[i] = d…
蟻本章末問題 問題概要 リンク ボーリングのピンが並んでる 一番前のピンを倒す その後ろのピンのうち左右どちらかのピンを倒すことができる さらに、その後ろのピンのうち左右どちらかのピンを倒すことができる 以上の作業を繰り返し一番後ろのピンまで倒す…
問題概要 リンク 木 ノードとノードの単純パスの距離は通ったエッジのXOR和 XOR和がXになるのは何通りか 解法 あるノードを根とした時、aとbの単純パスはa-LCA(a,b)-bである。 ※LCAはLowest Common Ancestor すなわちその距離L(a,b)は、 L(a,b) = L(a,LCA(a,…
問題概要 (リンク)http://arc048.contest.atcoder.jp/tasks/arc048_c 高橋君はN本の足がある N本の足はLi本のパーツに分かれている Li本の足に0か1を書き込む 任意の2本の足A,Bを選んだ時、Aのつま先-胴体-Bのつま先と辿った時、0、1は回文となっていなけれ…
頂点が有向グラフである意味がない… 問題概要 (リンク)http://arc049.contest.atcoder.jp/tasks/arc049_c N頂点の有向グラフがある 頂点に色を塗る その際以下の制約つける 頂点xに色をぬるとき、頂点yに色が塗られていなければならない 頂点uに色を塗るとき…
問題概要 (リンク)http://abc040.contest.atcoder.jp/tasks/abc040_d y_i年に作られた道は都市a_iと都市b_iを結ぶ 住民jはv_jに住んでいてw_j以前に作られた道を通りたくない 全ての住人が移動できる都市の数を求める 解法 UnionFindを使う 少し拡張してUnio…
ABCのBなのに、難しいと感じた人が多かった問題。 1回REでWAを出してしまった。 問題概要 (リンク)http://abc040.contest.atcoder.jp/tasks/abc040_b n枚のタイルを敷き詰めて、長方形を作る。 その時、短辺と長辺の差 + 余ったタイルが最小になるようにする…
問題概要 リンク 1 ~ Nまでの数字が書かれたせんべいがランダムな順番で与えられる シカは1枚目から順にせんべいを食べるか、食べないか選ぶ シカは全部でK枚のせんべいを食べられる シカはn枚目のせんべいを見ている時, 1 ~ n枚目のせんべいの大小関係がわ…
問題概要 リンク 文字列Sに対して S=A+B+C+A+C となるような部分文字列A, B, Cがいくつ考えうる数え上げる。 解法 部分点 AとCの文字数を決める O(N2) 条件を満たすかはローリングハッシュでO(1) 満点 SをABCとACに分ける境目を探索する その際、Z algorithm…
本番中は，UnionFindのコードをコピペして座ってるだけ． 本番後，Twitterで参加者のツイートを見てAC． 問題はこちら 問題概要 a,b,cから構成される文字列に対応したグラフを考える 文字列のi番目の文字はi番目のノードに対応している 文字列のi番目の文字…
新しいアルゴリズムを学んだので自分用の備忘録． Suffix Arrayとは 日本語では接尾辞配列 ある文字列の全ての接尾辞を辞書順に並べたもの 例えば “coder” という文字列について考える 接尾辞は “coder”, “oder”, “der” “er”, “r”, “” 接尾辞配列は以下の通…
CodeforcesでACした問題を確認できるサイトを作った． Codeforces AC List 使い方 フォームにCodeforcesのIDを入れてEnterを押すだけ． ACした問題は緑色になる． 作った経緯 競技プログラミングの能力を効率的にあげるには，自分に適したレベルの問題を解く…
