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個以上ある場合は構成不…
Codeforces Round #304 Div.2 E. Soldier and Traveling Problem - 546E - Codeforcesフローで解けることを知っていながら解いたが、解説無しでACしたのでよし。n個の街があって、m個の道によって連結である。各街には兵士がa[i]人かいて、彼らは今いる街に…
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. 情報伝播 D: 情報伝播 - AtCoder Regular Contest 010 | AtCodern人の青木くんとm人のスパイが平面上にいて、青木くんは、自分を中心とする任意の半径をもつ円の内部に情報を拡散できる。スパイに情報がもれないように、青木くん全員に…
ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem Problem - D - Codeforces2SATの問題。ドアがn個あって、それぞれのドアはそれぞれちょうど2個の異なるスイッチによって操作でき、スイッチは動かすと状態が反…
Atcoder ARC #006 D. アルファベット探し D: アルファベット探し - AtCoder Regular Contest 006 | AtCoderある決められた図形A, B, Cの非負整数倍拡大図形が90度毎の回転を許していくつか描かれているので、A, B, Cがそれぞれ何個ずつ含まれているかを数え…
Atcoder ARC #004 D. 表現の自由 ( Freedom of expression ) D: 表現の自由 ( Freedom of expression ) - AtCoder Regular Contest 004 | AtCoder整数nをm個の整数の積で表す方法の数を求める問題。真っ先に考えたのは、負の数をどう処理するかであった。と…
Atcoder ARC #002 D. ボードゲームD: ボードゲーム - AtCoder Regular Contest 002 | AtCoder２時間ほどかかったが自力で通したので、個人的にはARCのD（F）にしてはぬるめの考察問題だったと思う。ボード上の２種類のコマ'o'と'x'の状態が与えられる。'o'は…
Atcoder AGC #009 B. Tournament B: Tournament - AtCoder Grand Contest 009 | AtCoder解いたあとに解説見たらDPでごにょごにょって書いていたが、もっとわかりやすくあっさり書けた。n人の人が、負けたらそこで終わりのトーナメント形式で優勝を目指して戦…
Atcoder ARC #022 B. 細長いお菓子 B: 細長いお菓子 - AtCoder Regular Contest 022 | AtCoder数列が与えられるので、その部分列の中で、相異なる数のみを含むもので最長のものの長さを答える問題。すごくシンプルなのだけれど、少し手こずった。いまどの区…
Atcoder ARC #048 D. たこ焼き屋とQ人の高橋君 D: たこ焼き屋とQ人の高橋君 - AtCoder Regular Contest 048 | AtCoderある木と、各ノードにたこ焼き屋さんがあるかどうかの情報が与えられる。最初はノード間の移動に２秒かかるが、たこ焼き屋さんがあるノー…
Atcoder ARC #029 C. 高橋くんと国家 C: 高橋君と国家 - AtCoder Regular Contest 029 | AtCoderある無向グラフが与えられる。その各辺について、それを舗装するコストと、各都市についてそこに交易所を設置するコストが与えられている。すべての都市につい…
Codeforces Croc Champ 2013 - Round 1 E. Copying Data Problem - E - Codeforces数列a[i]とb[i]が与えられる。これらの数列について、以下の２種類のクエリを実行していくという問題。 ・aのx番目からk個をbのy番目からk個にコピーする ・b[x]を出力する …
Codeforces Round #271 Div.2 F. Ant colony Problem - F - Codeforcesある数列に対するクエリに順に答えていく。クエリは[l, r]で与えられ、その区間の各数について、「その数が他のすべての数を割り切る」という条件を満たさないものの数を求める。総数はr…
Codeforces Round #223 Div.1 C. Sereja and Brackets Problem - D - Codeforces"("と")"のみからなる文字列が与えられる。クエリとしてある区間[l, r]が与えられるので、その区間の中で、"("と")"のペアがうまくつくれるようなものは何個あるかを答える問題…
Codeforces Round #197 Div.2 D. Xenia and Bit Operations Problem - D - Codeforces2のn乗個の数列に対して、 奇数番目の数とその次の数同士のorをとって数列をつくる 奇数番目の数とその次の数同士のxorをとって数列をつくる という操作を数が1個になるま…
Codeforces Round #208 Div.2 E. Dima and KicksProblem - E - Codeforceskmjpさんの解法を丸パクリ参考にさせていただきました。ありがとうございます。 kmjp.hatenablog.jpとはいえ、自分で理解するためにコメントを書き、少し理解しやすいように書き換え…
Codeforces Round #375 Div.2 E問題Problem - E - Codeforces与えられた単純無向グラフに対して、入次数と出次数が等しい頂点の数が最大化されるように各辺に向きをつける、という問題。連結とは限らないことに注意する。辺の追加はできないので、そもそも次…
Codeforces Round #296 Div.1 C. Data Center Dramaオイラー路の問題をまとめて解いている。 Problem - C - Codeforcesn頂点、m辺の無向グラフが与えられる。各頂点について、その頂点から出ていく本数とその頂点に入ってくる本数がともに偶数になるように、…
AOJ Patrolパトロール | Aizu Online Judge無向オイラー路の判定をするだけなので、スタート地点とゴール地点の字数が奇数でかつ他の点の字数がすべて偶数であるかどうかを判定するだけである。入力の受け取り方の方が面倒な問題......。問題解いてる部分は…
