2017-08-01から1ヶ月間の記事一覧
Atcoder Grand Contest 008 F. Black Radius F: Black Radius - AtCoder Grand Contest 008 | AtCoder 感想 こちらのei1333さんの記事†全方位木DP†について - ei1333の日記で全方位木dpの概念を学んだところだったので、そこまで苦労しなかった。わかりやす…
Atcoder Grand Contest 017 E. Jigsaw E: Jigsaw - AtCoder Grand Contest 017 | AtCoder 感想 新しい感じのdfsをした。 解法 まずある右（左）の形状に対して、対応する左（右）の形状が一意に定まることに注意する。このうまくフィットする形状同士を同一…
Atcoder Beginner Contest 057 D. Maximum Average Sets D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder 感想 なぜかWAのまま放置していた。 解法 なんかやるだけ。 ただし$\ {}_n C _r \ $を求めるためにはパスカルの三角形による計算…
Atcoder Grand Contest 019 D. Shift and Flip 感想 結局やるだけだったけど、ひたすら補題の実装ができなかった。解説は自明なパートだけだらだらと書いていて最も知りたい部分が省略されていた。 解法 まず最終的に$\ a\ $のどの部分が$\ b\ $のどの部分に…
Atcoder Regular Contest 054 B. ムーアの法則 B: ムーアの法則 - AtCoder Regular Contest 054 | AtCoder 感想 はじめて三分探索を書いた。凸関数の解を求めるときに使えるやつ。零点が手で計算できるときはそっちの方が良いんだと思う。 解法 三分探索で、…
Atcoder Regular Contest 076 E. Connected? E: Connected? - AtCoder Regular Contest 076 | AtCoder 感想 だいぶ前に線分の交差判定などで解こうとしたけどダメだったので放置していた。条件をもう少し本質的にとらえることと、周を1次元に落とし込むこと…
Atcoder Regular Contest 079 F. Namori Grundy F: Namori Grundy - AtCoder Regular Contest 079 | AtCoder 感想 こういうグラフをNamoriグラフというらしい。 解法 まずグラフの形状が常に閉路を一つ含み、そこから木が外側に向かって生えたようなグラフに…
Atcoder Regular Contest 080 F. Prime Flip F: Prime Flip - AtCoder Regular Contest 080 | AtCoder 感想 解説を見た。簡単な方法に落とし込むまでの流れが好きな問題。 解法 まず区間をひっくり返すときのテクを使う。列においてある位置とその一つ前の位…
Atcoder AGC 005 E. Sugigma: The Showdown E: Sugigma: The Showdown - AtCoder Grand Contest 005 | AtCoder 感想 後半の考察に1時間以上かかったが、自力で一発ACしたので嬉しかった。木とゲームに関する問題はやっぱり得意だ。 解法 以下、先手を$\ N\ $…
Atcoder AGC 003 D. Anticube D: Anticube - AtCoder Grand Contest 003 | AtCoder 感想 素因数分解したときに出てくる3乗は消しても良いことには割とすぐに気づき、共存できない数同士のペアが一意に定まるところまでは落とし込めた。が、実装方法と計算量…
Atcoder ARC 061 D. すぬけ君の塗り絵 / Snuke's Coloring D: すぬけ君の塗り絵 / Snuke's Coloring - AtCoder Regular Contest 061 | AtCoder 解法 最も愚直な方法は、$\ H * W\ $の配列を用意し、そこにクエリに従って色をつけていき、最後に$\ 3 * 3\ $の…
Atcoder AGC 017 B. Moderate Differences B: Moderate Differences - AtCoder Grand Contest 017 | AtCoder 解法 数列において減少する回数を固定して、差分($\ B - A\ $)のとりうる最小最大を決めて条件を満たすものがあるかを判定する。例えば下限を考え…
Atcoder AGC 006 C. Rabbit Exercise C: Rabbit Exercise - AtCoder Grand Contest 006 | AtCoder 解法 まず、各ステップにおいて、期待値を決定していけることに注目する。うさぎ$\ a\ $について、そのジャンプ後の位置の期待値は、左右のジャンプが両方確…
CF Croc Champ 2013 - Round 1 E. Copying Data（別解） Problem - E - Codeforces 解法 RBSTの実装法を学んだので、過去に解いた問題をRBSTで書いてみた。遅延セグ木でぐちゃぐちゃする問題が、思考停止ではい、の問題に変わった。解としては自明に正しいけ…
Atcoder Typical DP Contest E. 数 E: 数 - Typical DP Contest | AtCoder 解法 自分の実際の思考の流れに従ってまとめておく。まず自明に思いつくDPが、$\ dp[i][j] := \ $(上からi番目までを見て、各桁の和をDで割った余りがjであるような組み合わせの数)…
Atcoder ARC 030 D. グラフではない D: グラフではない - AtCoder Regular Contest 030 | AtCoder 解法 RBST(Randomized Binary Search Tree)として知られる永続データ構造を使う。ググって色々調べたり、他の人のコードから学んで実装した。RBSTについて自…
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 F: Tree Game - AtCoder Grand Contest 010 | AtCoderこの点数の問題を完全に自力で通せたので驚いた。こういうタイプの問題が得意になってきた（気がする）ので嬉しい。思考の流れもまとめて記述しておく。まぁ順位表見てもわ…
AOJ Slim Span Slim Span | Aizu Online Judge 解法 まず全域木の中で、重みが最小となる辺を固定する。その重み以上辺のみを使って、$Kruskal$法によって最小全域木を作り、その時の$Slimness$を求め、その最小値をとる。 辺はあらかじめ重みで昇順にソート…
Atcoder ARC 080 E. Young Maids E: Young Maids - AtCoder Regular Contest 080 | AtCoder 解法 ある区間（最初は全体）の数列の偶数番目（$0-indexed$）の最小値と、その最小値より右側にあって、かつその数を基準に数えて、奇数番目にあるような数の最小…
Atcoder ABC 069 A. K-City A: K-City - AtCoder Beginner Contest 069 | AtCoder 解法 $(n - 1) (m - 1)$を出力するだけ。$O(1)$。 実装 #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; cout << (n - 1) * (m - 1) << endl; return</bits/stdc++.h>…
Atcoder AGC #018 F. Two Trees F: Two Trees - AtCoder Grand Contest 018 | AtCoder頂点数が等しい根付き木が２つ与えられる。この木の各ノードに対して、値を割り当てることを考える。ただしノード番号が同じものは同じ値を割り当てる。任意の部分木（根…
Atcoder AGC #015 C. Nuske vs Phantom Thnook C: Nuske vs Phantom Thnook - AtCoder Grand Contest 015 | AtCoder実はグラフの問題だったという感じがして好きな問題。色が塗られたグリッドが与えられる。その上下左右について辺を共有するマス同士を連結…
Atcoder AGC #005 C. Tree Restoring C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder頂点iからみて最も遠い点までの距離がa[i]として与えられるので、そのような木が構成可能かを答える問題。とりあえずa[i]の最小値が、3個以上ある場合は構成不…
