Learning Algorithms

アルゴリズムの勉強メモ

発想

Atcoder AGC 006 C. Rabbit Exercise

Atcoder AGC 006 C. Rabbit Exercise C: Rabbit Exercise - AtCoder Grand Contest 006 | AtCoder 解法 まず、各ステップにおいて、期待値を決定していけることに注目する。うさぎ$\ a\ $について、そのジャンプ後の位置の期待値は、左右のジャンプが両方確…

Atcoder AGC #018 F. Two Trees

Atcoder AGC #018 F. Two Trees F: Two Trees - AtCoder Grand Contest 018 | AtCoder頂点数が等しい根付き木が2つ与えられる。この木の各ノードに対して、値を割り当てることを考える。ただしノード番号が同じものは同じ値を割り当てる。任意の部分木(根…

Atcoder AGC #015 C. Nuske vs Phantom Thnook

Atcoder AGC #015 C. Nuske vs Phantom Thnook C: Nuske vs Phantom Thnook - AtCoder Grand Contest 015 | AtCoder実はグラフの問題だったという感じがして好きな問題。色が塗られたグリッドが与えられる。その上下左右について辺を共有するマス同士を連結…

Atcoder AGC #005 C. Tree Restoring

Atcoder AGC #005 C. Tree Restoring C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder頂点iからみて最も遠い点までの距離がa[i]として与えられるので、そのような木が構成可能かを答える問題。とりあえずa[i]の最小値が、3個以上ある場合は構成不…

Atcoder ARC #004 D. 表現の自由 ( Freedom of expression )

Atcoder ARC #004 D. 表現の自由 ( Freedom of expression ) D: 表現の自由 ( Freedom of expression ) - AtCoder Regular Contest 004 | AtCoder整数nをm個の整数の積で表す方法の数を求める問題。真っ先に考えたのは、負の数をどう処理するかであった。と…

Atcoder ARC #002 D. ボードゲーム

Atcoder ARC #002 D. ボードゲームD: ボードゲーム - AtCoder Regular Contest 002 | AtCoder2時間ほどかかったが自力で通したので、個人的にはARCのD(F)にしてはぬるめの考察問題だったと思う。ボード上の2種類のコマ'o'と'x'の状態が与えられる。'o'は…

Atcoder AGC #009 B. Tournament

Atcoder AGC #009 B. Tournament B: Tournament - AtCoder Grand Contest 009 | AtCoder解いたあとに解説見たらDPでごにょごにょって書いていたが、もっとわかりやすくあっさり書けた。n人の人が、負けたらそこで終わりのトーナメント形式で優勝を目指して戦…

Atcoder ARC #029 C. 高橋くんと国家

Atcoder ARC #029 C. 高橋くんと国家 C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoderある無向グラフが与えられる。その各辺について、それを舗装するコストと、各都市についてそこに交易所を設置するコストが与えられている。すべての都市につい…