Learning Algorithms

アルゴリズムの勉強メモ

発想

Atcoder Grand Contest 014 E. Blue and Red Tree

Atcoder Grand Contest 014 E. Blue and Red Tree E: Blue and Red Tree - AtCoder Grand Contest 014 | AtCoder 感想 難しいがおもしろい。解説を読んで、少し人のコードを参考にして書いた。 解法 辺の色が異なる2つの木を重ね合せて考える。そのグラフ上…

AOJ Graph Automata Player

AOJ Graph Automata Player Graph Automata Player | Aizu Online Judge 感想 ICPCのチーム練習で解いた。好きな感じの問題なので、じーーっと考察していると解法がわかった。 解法 ある頂点に注目して考える。ある状態から次の状態に遷移するとき、その頂点…

CODE FESTIVAL 2017 qual B C. 3 Steps

CODE FESTIVAL 2017 qual B C. 3 Steps C: 3 Steps - CODE FESTIVAL 2017 qual B | AtCoder 感想 qual Aには出れなかったので、qual Bから参戦していた。40分で3完し、そのあとはひたすらDのバグをつぶそうとしていた。総合243位、日本人98位なので本戦には…

Atcoder Grand Contest 012 D. Colorful Balls

Atcoder Grand Contest 012 D. Colorful Balls 感想 前半の考察はできたのに、ほとんど同じの後半の発想がなぜかできなかった。 解法 まずすべての色が等しければ、答えは$\ 1\ $となる。以下は2種類以上の色があるものとする。操作1では色の配置を変えるこ…

CS Academy 46 Div. 1.5 C. Set Subtraction

CS Academy 46 Div. 1.5 C. Set Subtraction CS Academy 感想 ちょっと応用できそう。 解法 まず数列はソートしておく。そして$\ X\ $について全探索する。全探索といっても$\ X \leq A_{n - 1}\ $ですべて試していると間に合わないので、$\ X\ $の候補とし…

Atcoder Grand Contest 017 E. Jigsaw

Atcoder Grand Contest 017 E. Jigsaw E: Jigsaw - AtCoder Grand Contest 017 | AtCoder 感想 新しい感じのdfsをした。 解法 まずある右(左)の形状に対して、対応する左(右)の形状が一意に定まることに注意する。このうまくフィットする形状同士を同一…

Atcoder Regular Contest 076 E. Connected?

Atcoder Regular Contest 076 E. Connected? E: Connected? - AtCoder Regular Contest 076 | AtCoder 感想 だいぶ前に線分の交差判定などで解こうとしたけどダメだったので放置していた。条件をもう少し本質的にとらえることと、周を1次元に落とし込むこと…

Atcoder AGC 005 E. Sugigma: The Showdown

Atcoder AGC 005 E. Sugigma: The Showdown E: Sugigma: The Showdown - AtCoder Grand Contest 005 | AtCoder 感想 後半の考察に1時間以上かかったが、自力で一発ACしたので嬉しかった。木とゲームに関する問題はやっぱり得意だ。 解法 以下、先手を$\ N\ $…

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ある無向グラフが与えられる。その各辺について、それを舗装するコストと、各都市についてそこに交易所を設置するコストが与えられている。すべての都市につい…