問題 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 の正方形の網がある。その網をグリッド上に設置したとき、その領域に含まれる魚を得られる。 その網をグリッド上の考えられるすべての場所に設置するとき…

問題文 重み付き有向グラフが与えられる。 頂点を２つのグループに分け、お互いの頂点間を移動できないようにしたい。 そのために、辺を取り除いていくことができる。 取り除いた辺の重みの最小値は？ http://judge.u-aizu.ac.jp/onlinejudge/description.js…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1069&lang=jp 解法 解法1 二分探索 を二分探索で求める。それだけ。 ソースコード int n, N; vector<int> even_b, odd_b; bool check(double x) { vector<double> a(2); Rep(i, 2) a[i] = (double)even_</double></int>…

概要 N*Mの領域にあるn本の座標(xi, yi)が与えられる。 (x,y)からは与えられた座標のうち(x±K, y±K)の範囲に含まれる座標、または(0, 0)(N, M)に移動できる。 (0, 0)から(N, M)に移動することを考える。 与えられた順番に座標を取り除いていくとき、(0, 0)か…

概要 英小文字のみからなる文字列が与えられる。 をいくつかの空でない部分文字列に分割する。 そのとき、部分文字列は以下の条件を満たす。 ・の文字を並べ替えて回文が得られる。 文字列の最小の分割数を求めよ。 問題文 D: Yet Another Palindrome Partit…

9月18日～20日に行われた「会津大学競技プログラミング合宿2017」に参加しました。 Day1：立命館セット ～コンテスト前～ 会場の準備や買い出しのため、会津大生は朝9時の集合だった。生活リズムが崩壊していたため2時間ほどしか寝られなかった。11時を過ぎ…

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define fr first #define sc second #define Rep(i,n) for(int i=0;i<(n);i++) #define All(v) v.begin(),v.end() #define Uniq(v) v.erase(unique(All(v))</bits/stdc++.h>…