問題文 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 と規格が改定されていくにつれ、色々便利な機能が追加されています。 そのうちのいくつかは競プロであっても有用なのですが、特に最近始めた人のコードを読んでいるとほとんど使われておらずもったいないと感じることが多いです。 そ…