問題 F - Permutation Tree 解法 まず、数列から木を作ってみる。 作ると木に頂点を追加するときは、脚を増やすか胴体を伸ばす選択肢しかないことが分かる。 （こういう木をcaterpillarというらしい。確かに毛虫っぽい。） なぜ、caterpillarになるのかのイ…

問題 F - Normalization 解法 この問題の部分問題として、S->Tに変換できるか考える。 まず、Sから変換している以上、同じ文字が連続している箇所がないとおかしい。 さらに、a->0 b->1 c->2 とそれぞれの文字に数字を割り当てS,Tを数列とみなしたとき、 (∑S…

問題 D - Worst Case 解法1 公式解説通り #include <bits/stdc++.h> using namespace std; using Int = long long; int main() { Int Q; cin >> Q; while ( Q-- ) { Int A, B; cin >> A >> B; if ( A > B ) swap(A, B); if ( B - A <= 1 ) cout << 2*A-2 << endl; else { In</bits/stdc++.h>…

問題 C - 01文字列 解説 https://ddcc2016-final.contest.atcoder.jp/data/other/ddcc2016-final/editorial.pdf 考察 公式解説そのまま NをTのサイズとすると、 操作１と操作２は合計で N 回行われることは明らか。 よって、操作１と操作２をそれぞれ何回行…

問題 E - Addition and Subtraction Hard 解説 公式 https://atcoder.jp/img/arc066/editorial.pdf kmjpさん AtCoder ARC #066 : E - Addition and Subtraction Hard - kmjp's blog 考察 どうすれば式の値を最大化できるかを考える。 -の後に開き括弧を挿入…

問題文 n × m マスのグリッドにk匹の魚がいる。（それぞれのセルには魚は高々一匹しかいない） r × r の正方形の網がある。その網をグリッド上に設置したとき、その領域に含まれる魚を得られる。 その網をグリッド上の考えられるすべての場所に設置するとき…