問題概要 略 リンク やや雑な解法メモ 次のようなデータ構造を考える。 child[i] = [人iに負けた人たち] また、次のようなDPを考える。 DP[i] = 人iが勝ち進んだところまでのトーナメント表の最小の深さ child[v] = [m1, m2, m3, m4]の時、 miを人vが直近に…
年末で会社が休みなので、自分のために今年読んだり読まなかったりした技術書を整理します。 目次 全部読んだ 半分以上読んだ 半分未満しか読んでない 全部読んだ オブジェクト指向でなぜつくるのか 評価: ★★★★☆ 自分用メモ: もう一度読むなら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した問題は緑色になる． 作った経緯 競技プログラミングの能力を効率的にあげるには，自分に適したレベルの問題を解く…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の25日目のエントリです． 問題 問題概要 トーナメントを行う 参加者iのレートはRiである レートRpとレートRqが戦った時，前者が勝つ確率は [latex]\frac{1}{1+10^{(Rq-Rp)/400}}[/latex] 各参加者が…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の24日目のエントリです． 問題 問題概要 N問のコンテストがある i問目の点数はpiである このコンテストで獲得できる得点のパターンは何種類か 解法 dp[i][j]:=i問目までj点を獲得できるか (できる: …
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の23日目のエントリです． 問題 ARCのB問題埋め． 問題概要 あみたくじと到達したい地点が与えられる 到達するために選ぶべきは線はどれか 解法 amita_to_r[高さ][線番号]にその縦線でその高さにいる…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の22日目のエントリです． 問題 ARCのB問題埋め． 問題概要 エアコンの設定温度をA度からB度にしたい エアコンは1度，5度，10度刻みで温度を変えることができる 何回の操作が必要か 解法 ある温度iか…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の21日目のエントリです． 問題 ARCのB問題埋め． 問題概要 点iと点i+1の距離，di与えられる (i=0~N-1) 点0と点Nの距離として考えられる最大値，最小値を求める 解法 最大値は点が一直線に並んだ場合…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の20日目のエントリです． 問題 ARCのB問題埋め． 問題概要 AtCoder国では日本と同じアラビア数字を用いている しかし数字の大きさはb0 < b1 <‥‥< b9である AtCoder国の数字がN個与えられるので昇順…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の19日目のエントリです． 問題 またARCのB問題 問題概要 看板にしたい文字列と英字キット1袋に文字の列が与えられる 看板を作るのには何セット必要か 解法 看板の文字列に出てきたアルファベットの…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の18日目のエントリです． 問題 ARCのB問題が全部埋まりそうなので年内に埋めようと思います． 問題概要 与えられた文字列を，辞書順で末尾が若い順に並べ替える 末尾が同じなら末尾から2番めの文字…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の17日目のエントリです． 問題 ※ 出題が終わってしまったため上記のURLから問題が見られません．「マヨイドーロ問題」で検索すると出題pdfが見られます．(pdfへの直リンクは禁止らしいのでここに貼…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の16日目のエントリです． 問題 問題概要 AtCoder国の2012年の祝日が与えられるので最大の連休の数を求める 解法 長さ366の配列で2012年のi-1日目が休日がどうかを管理する 1日が日曜のためi%7==0は…
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の15日目のエントリです． 問題 問題概要 ルイス・キャロルの記憶法によって文字列から数字を復元する 解法 連想配列を知っていればやるだけ問題． しかし，文字列の扱うのが苦手だったりで無限にバ…
