問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2692 解法 包除原理。 チームにしないといけない組は確定で組ませる。 また、チームにしてはいけない組のすべての部分集合に対して、その集合に含まれる組は確定でチームを組ませるとする…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1628&lang=jp 解説 実装するだけ。 仮数部表現は 1 も含めた 53 bit で表現すると楽だと思う。 a を何回足せば仮数部に収まらなくなるかは簡単な式で O(1) で求まる。 それを今の値に足し…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2604\ 解法 変数は 10 個しかないので、それぞれの変数を何桁にするか最初に全探索する。 すると、変数の桁ごとに、どの桁と対応するかを決定できる。 対応する集合を union find 木かなに…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1388 解法 m つまり愚直にサイクルを探索しても、そこまで探索空間は大きくない。サイクル空間を考えるにしろ、n, m が大きすぎるので、小さくしたい。 よく考えると、次数が 2 以下の頂点…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2686 解法 自明ケースからちょっとずつ難しくしていくのが良いと思った（実験しても良いかも）。 a == b 同じ条件なので Nim (grundy 数) に帰着可能。 ある山の石の個数を s とすると s %…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2250 解法 二分探索やるだけじゃーんとなってサンプルチェックして違うことが判明するやつ。見事に引っかかってしまった。良い性質がないか観察してみると、少なくとも可能かどうかの人数…

問題概要 n 頂点 m 辺の単純で連結な無向グラフが与えられる。n は奇数である。 deg(v) を頂点 v の次数とし、k を deg(v) の最大値以上で最小の奇数と定義する。 このとき、グラフを k 色以下で頂点彩色せよ。・制約 3 1 n は奇数 解法 n と k が両方奇数な…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2861 解法 典型構築だと思われる。 4n - 1, 4m - 1 であることが重要で、この制約のためにすべてのマスを回収するようなパスが存在する。 イメージとしては蛇のようにうねうねしながら移動…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1382 解法 いかにも DP の高速化をする見た目をしている。 DP を考える前に、操作を観察する。 色々実験などして考えてみると、 ある位置を3回以上塗るのは最適ではなさそう 2つの区間を違…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1622 解法 右手法かフロー（最大流）で解けるが、今回はフローで解く。 フロー解は割と一発ネタなところがある。まず、各マスを2つの頂点に倍化（入力ノード、出力ノード）し、これら2つの…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2785 解法 とりあえず C[i] については無視して考えてみる。 最終日に使うドリンクを決めたとする。このドリンクを k とする。 すると、L - a[k] をできるだけ早く達成したいということに…

問題文 https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d 解法 区間同士でうまくマージできるような形であればセグ木に乗せることができるので、とりあえずその方針で考えてみる。 2つの区間 A, B があって、それらをマージしたときに "D…

はじめに C++14, 17, 20 と規格が改定されていくにつれ、色々便利な機能が追加されています。 そのうちのいくつかは競プロであっても有用なのですが、特に最近始めた人のコードを読んでいるとほとんど使われておらずもったいないと感じることが多いです。 そ…

問題文 https://codeforces.com/contest/364/problem/D 解答 https://github.com/Suikaba/procon-solved/blob/master/Codeforces/Round200-249/Round213/Div1-D.cpp 感想 計算量と TL の割に配列サイズでかすぎない？

これまでは、難しいなと思った問題や AOJ で解説がない問題の記事をはてなに直接書いてきた。 しかし最近は解いたときのコードを git で管理するようになったので、今後は github の解答コードへのリンクを貼るようにしようと思う。 解説や考察メモはコード…