A: やるだけ
B: どういう数列に変化させるのが最適かは簡単に分かる。1ステップでは出来る限り範囲をインクリメントするべき。
C: dp[ n桁目 ][ 最後に使った数字 ][ 小さくなったか ][ 最初の非 0 の数字 ]
D: やるだけ
以下、本番で投げたコード
A
#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)
typedef long long int lli;
using namespace std;
int main(int argc, char *argv[])
{
int n;
while (cin >> n) {
int m[n];
for (int i = 0; i < n; ++i) {
cin >> m[i];
}
const string S = "Still Rozdil";
const int *mn = min_element(m, m + n);
if (count(m, m + n, *mn) == 1) cout << mn - m + 1 << endl;
else cout << S << endl;
}
return 0;
}
B
#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)
typedef long long int lli;
using namespace std;
int main(int argc, char *argv[])
{
lli n;
while (cin >> n) {
lli m[n];
for (int i = 0; i < n; ++i) {
cin >> m[i];
}
lli x[n];
x[0] = m[0];
for (int i = 1; i < n; ++i) {
x[i] = max(x[i - 1], m[i]);
}
lli diff[n];
for (int i = 0; i < n; ++i) {
diff[i] = x[i] - m[i];
}
lli sum = 0;
lli y = 0;
for (int i = 0; i < n; ++i) {
if (diff[i] <= y) y = diff[i];
else {
sum += diff[i] - y;
y = diff[i];
}
}
cout << sum << endl;
}
return 0;
}
C
#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)
typedef long long int lli;
using namespace std;
const int D = 20;
vector<int> v;
lli memo[D][11][11][12];
lli rec(int d, int last, bool small, int first)
{
lli &ret = memo[d][last][small][first];
if (ret != -1) return ret;
if (v.size() == d) return ret = (last == first);
lli sum = 0;
if (small) {
for (int i = 0; i <= 9; ++i) {
sum += rec(d + 1, i, true, (first == 11 && i ? i : first));
}
} else {
for (int i = 0; i <= v[d]; ++i) {
sum += rec(d + 1, i, i < v[d], (first == 11 && i ? i : first));
}
}
return ret = sum;
}
lli f(lli n)
{
v.clear();
while (n) {
v.push_back(n % 10LL);
n /= 10LL;
}
reverse(v.begin(), v.end());
fill(&memo[0][0][0][0], &memo[D][0][0][0], -1);
return rec(0, 10, false, 11);
}
int main(int argc, char *argv[])
{
lli small, large;
while (cin >> small >> large) {
cout << f(large) - f(small - 1) << endl;
}
return 0;
}
D
#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)
typedef long long int lli;
using namespace std;
int main(int argc, char *argv[])
{
int n;
while (cin >> n) {
map<lli, lli> F, B;
pair<lli, lli> p[n];
for (int i = 0; i < n; ++i) {
cin >> p[i].first >> p[i].second;
++F[p[i].first];
if (p[i].first != p[i].second) ++B[p[i].second];
}
const lli H = (n + 1) / 2;
const lli inf = 1LL << 60;
lli mn = inf;
for (int i = 0; i < n; ++i) {
if (H <= F[p[i].first] + B[p[i].first]) {
lli cost = (H - F[p[i].first]);
mn = min(mn, cost);
}
if (H <= F[p[i].second] + B[p[i].second]) {
lli cost = (H - F[p[i].second]);
mn = min(mn, cost);
}
}
mn = max(mn, 0LL);
cout << (mn == inf ? -1 : mn) << endl;
}
return 0;
}
