Learning Algorithms

アルゴリズムの勉強メモ

Atcoder

Atcoder Regular Contest 054 B. ムーアの法則

Atcoder Regular Contest 054 B. ムーアの法則 B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder 感想 はじめて三分探索を書いた。凸関数の解を求めるときに使えるやつ。零点が手で計算できるときはそっちの方が良いんだと思う。 解法 三分探索で、…

Atcoder Regular Contest 076 E. Connected?

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

Atcoder Regular Contest 079 F. Namori Grundy

Atcoder Regular Contest 079 F. Namori Grundy F: Namori Grundy - AtCoder Regular Contest 079 | AtCoder 感想 こういうグラフをNamoriグラフというらしい。 解法 まずグラフの形状が常に閉路を一つ含み、そこから木が外側に向かって生えたようなグラフに…

Atcoder Regular Contest 080 F. Prime Flip

Atcoder Regular Contest 080 F. Prime Flip F: Prime Flip - AtCoder Regular Contest 080 | AtCoder 感想 解説を見た。簡単な方法に落とし込むまでの流れが好きな問題。 解法 まず区間をひっくり返すときのテクを使う。列においてある位置とその一つ前の位…

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 003 D. Anticube

Atcoder AGC 003 D. Anticube D: Anticube - AtCoder Grand Contest 003 | AtCoder 感想 素因数分解したときに出てくる3乗は消しても良いことには割とすぐに気づき、共存できない数同士のペアが一意に定まるところまでは落とし込めた。が、実装方法と計算量…

Atcoder AGC 017 B. Moderate Differences

Atcoder AGC 017 B. Moderate Differences B: Moderate Differences - AtCoder Grand Contest 017 | AtCoder 解法 数列において減少する回数を固定して、差分($\ B - A\ $)のとりうる最小最大を決めて条件を満たすものがあるかを判定する。例えば下限を考え…

Atcoder AGC 006 C. Rabbit Exercise

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

Atcoder Typical DP Contest E. 数

Atcoder Typical DP Contest E. 数 E: 数 - Typical DP Contest | AtCoder 解法 自分の実際の思考の流れに従ってまとめておく。まず自明に思いつくDPが、$\ dp[i][j] := \ $(上からi番目までを見て、各桁の和をDで割った余りがjであるような組み合わせの数)…

Atcoder ARC 030 D. グラフではない

Atcoder ARC 030 D. グラフではない D: グラフではない - AtCoder Regular Contest 030 | AtCoder 解法 RBST(Randomized Binary Search Tree)として知られる永続データ構造を使う。ググって色々調べたり、他の人のコードから学んで実装した。RBSTについて自…

Atcoder ABC 031 D. 語呂合わせ

Atcoder ABC 031 D. 語呂合わせ D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder 解法 各数字が表す文字列$\ s_j\ $の長さに関する全探索をする。それぞれの文字列の情報$\ i\ $に対して、$\ \sum_{j = 0}^k |s_j| = |w_i|\ $を満たすかどうかを判…

Atcoder AGC 010 F. Tree Game

Atcoder AGC 010 F. Tree Game F: Tree Game - AtCoder Grand Contest 010 | AtCoderこの点数の問題を完全に自力で通せたので驚いた。こういうタイプの問題が得意になってきた(気がする)ので嬉しい。思考の流れもまとめて記述しておく。まぁ順位表見てもわ…

Atcoder ARC 080 E. Young Maids

Atcoder ARC 080 E. Young Maids E: Young Maids - AtCoder Regular Contest 080 | AtCoder 解法 ある区間(最初は全体)の数列の偶数番目($0-indexed$)の最小値と、その最小値より右側にあって、かつその数を基準に数えて、奇数番目にあるような数の最小…

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 ABC #029 D. 1

Atcoder ABC #029 D. 1 D: 1 - AtCoder Beginner Contest 029 | AtCoder1からnまでの数字を全て書いた時、1が何回現れるかを求める問題。例えばn=15なら8と答える。部分点のn デバッグができるようにてきとうに書いておいた。さて、n #include "bits/stdc++.…

Atcoder ARC #010 D. 情報伝播

Atcoder ARC #010 D. 情報伝播 D: 情報伝播 - AtCoder Regular Contest 010 | AtCodern人の青木くんとm人のスパイが平面上にいて、青木くんは、自分を中心とする任意の半径をもつ円の内部に情報を拡散できる。スパイに情報がもれないように、青木くん全員に…

Atcoder ARC #006 D. アルファベット探し

Atcoder ARC #006 D. アルファベット探し D: アルファベット探し - AtCoder Regular Contest 006 | AtCoderある決められた図形A, B, Cの非負整数倍拡大図形が90度毎の回転を許していくつか描かれているので、A, B, Cがそれぞれ何個ずつ含まれているかを数え…

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 #022 B. 細長いお菓子

Atcoder ARC #022 B. 細長いお菓子 B: 細長いお菓子 - AtCoder Regular Contest 022 | AtCoder数列が与えられるので、その部分列の中で、相異なる数のみを含むもので最長のものの長さを答える問題。すごくシンプルなのだけれど、少し手こずった。いまどの区…

Atcoder ARC #048 D. たこ焼き屋とQ人の高橋君

Atcoder ARC #048 D. たこ焼き屋とQ人の高橋君 D: たこ焼き屋とQ人の高橋君 - AtCoder Regular Contest 048 | AtCoderある木と、各ノードにたこ焼き屋さんがあるかどうかの情報が与えられる。最初はノード間の移動に2秒かかるが、たこ焼き屋さんがあるノー…

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

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