ABC338に参加してきました。
bitDPを勉強して、E問題を演習して、
「そろそろ緑or水色パフォでもとりたいな～」と意気込んだ結果、、、
2完
え？かなしすぎん？
目も当てられない成績をたたき出してしまったので、基礎からちゃんと勉強しなおします。。
特に「変数を１つ固定して考える」という考え方は勉強済みだったのにできなかったのが良くない！
A Capitalized?
#include<bits/stdc++.h>
using namespace std;
int main () {
string S;
std::cin >> S;
bool ret = true;
char c;
c = S[0];
if(c >= 'a' && c <= 'z'){
// 小文字
ret = false;
}
else{
for(int i=1; i<S.size(); i++){
c = S[i];
if(c >= 'a' && c <= 'z'){
// 小文字
}else if(c >= 'A' && c <= 'Z'){
// 大文字
ret = false;
}
}
}
std::cout << (ret == true?"Yes":"No") << std::endl;
}
絶対もっといいやり方があるが、考える時間がもったいなかったので上記で提出。
こういうところかもな、、
B Frequency
#include<bits/stdc++.h>
using namespace std;
int main () {
string S;
std::cin >> S;
std::vector<int> chars(26, 0);
for(int i=0; i<S.size(); i++){
chars[S[i]-'a']++;
}
char ret='a';
int count=0;
for(int i=0; i<26; i++){
if(count<chars[i]){
ret = ('a'+i);
count = chars[i];
}
}
std::cout << ret << std::endl;
}
C Leftover Recipes
AtCoder
404 Not Found - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
以下で実装しようとしてTLE。
C問題が解けないのは相当悔しかった。。
#include <iostream>
#include <vector>
#define INF (1LL<<30)
int main() {
int N;
std::cin >> N;
std::vector<int> Q(N), A(N), B(N);
for (int n = 0; n < N; n++) std::cin >> Q[n];
for (int n = 0; n < N; n++) std::cin >> A[n];
for (int n = 0; n < N; n++) std::cin >> B[n];
int max_a = INF;
int max_b = INF;
for (int n = 0; n < N; n++) {
if (Q[n] == 0) continue;
if (A[n] != 0) max_a = std::min(max_a, int(Q[n] / A[n]));
if (B[n] != 0) max_b = std::min(max_b, int(Q[n] / B[n]));
}
int ans = 0;
for (int a = max_a; 0 <= a; a--) {
std::vector<int> tmp_Q = Q;
bool is_ok = true;
for (int n = 0; n < N; n++) {
tmp_Q[n] -= (a* A[n]);
if (tmp_Q[n] < 0) is_ok = false;
}
if (is_ok == false) continue;
int tmp_ans = a;
for (int b = max_b; 0 <= b; b--) {
bool is_ok_b = true;
for (int n = 0; n < N; n++) {
if (tmp_Q[n] < (b*B[n])) is_ok_b = false;
}
if (is_ok_b == false) continue;
else{
tmp_ans += b;
break;
}
}
ans = std::max(ans, tmp_ans);
}
std::cout << ans << std::endl;
}解きなおしたコードがこちら
#include <iostream>
#include <vector>
#define INF (1LL<<30)
int main() {
int N;
std::cin >> N;
std::vector<int> Q(N), A(N), B(N);
for (int n = 0; n < N; n++) std::cin >> Q[n];
for (int n = 0; n < N; n++) std::cin >> A[n];
for (int n = 0; n < N; n++) std::cin >> B[n];
int max_a = INF;
//int max_b = INF;
for (int n = 0; n < N; n++) {
if (Q[n] == 0) continue;
if (A[n] != 0) max_a = std::min(max_a, int(Q[n] / A[n]));
//if (B[n] != 0) max_b = std::min(max_b, int(Q[n] / B[n]));
}
int ans = 0;
//Aを固定した状態で、Bを作れる最大数を求める
for (int a = max_a; 0 <= a; a--) {
std::vector<int> tmp_Q = Q;
bool is_ok = true;
for (int n = 0; n < N; n++) {
tmp_Q[n] -= (a* A[n]);
if (tmp_Q[n] < 0) is_ok = false;
}
if (is_ok == false) continue;
int b = INF;
for (int n = 0; n < N; n++) {
if (B[n] != 0) {
b = std::min(b, int(tmp_Q[n] / B[n])); //max_bと同じ（QからAを引いた状態でmax_bを求めるイメージ）
}
}
if (b == INF) b = 0;
ans = std::max(ans, a + b);
}
std::cout << ans << std::endl;
}「料理Bの方は１つ１つやっていく必要はなかった」ということですね。
D Island Tour
以下のように愚直に実装するとTLEを食らうため、工夫が必要な問題。
#include <iostream>
#include <vector>
#include <algorithm>
#define INF (1LL<<30)
int main() {
int N, M;
std::cin >> N >> M;
std::vector<int> X(M);
for (int m = 0; m < M; m++) {
int x;
std::cin >> x;
x--;
X[m] = x;
}
auto distance = [&](int from, int to) {
if (from <= to) return (to - from);
else return ((to + N) - from);
/*
* N=5の場合、島は１、２、３、４，５
* １ ⇒ ４と移動するときは 4 - 1 = 3 回の移動が必要
* ４ ⇒ １と移動するときは1を６（= 1+5 = 1+N ）と見立てて 6 - 4 = 2 回の移動が必要
*/
};
long long ans = INF;
for (int n = 0; n < N; n++) {
long long tmp_ans = 0;
for (int m = 0; m < (M - 1); m++) {
//distance(X[m], X[m + 1]); // a ⇒ a+1 ⇒ a+2 ⇒ ... ⇒ bと移動する経路
//distance(X[m + 1], X[m]); // a ⇒ a-1 ⇒ a-2 ⇒ ... ⇒ bと移動する経路（同じ関数で距離計算するためにfromとtoを逆にして渡す）
int small = std::min(X[m], X[m + 1]);
int large = std::max(X[m], X[m + 1]);
if ((small <= n) && (n < large)) {
tmp_ans += distance(large, small); // a ⇒ a-1 ⇒ a-2 ⇒ ... ⇒ bと移動する経路（同じ関数で距離計算するためにfromとtoを逆にして渡す）
}
else {
tmp_ans += distance(small, large); // a ⇒ a+1 ⇒ a+2 ⇒ ... ⇒ bと移動する経路
}
}
ans = std::min(ans, tmp_ans);
}
std::cout << ans << std::endl;
}imos法なるものを使って、ある橋を封鎖した場合に移動距離がいくら増加になるかを計算するといいらしい。。
#include <iostream>
#include <vector>
#include <algorithm>
#define INF (1LL<<30)
int main() {
int N, M;
std::cin >> N >> M;
std::vector<int> X(M);
for (int m = 0; m < M; m++) {
int x;
std::cin >> x;
x--;
X[m] = x;
}
auto distance = [&](int from, int to) {
if (from <= to) return (to - from);
else return ((to + N) - from);
/*
* N=5の場合、島は１、２、３、４，５
* １ ⇒ ４と移動するときは 4 - 1 = 3 回の移動が必要
* ４ ⇒ １と移動するときは1を６（= 1+5 = 1+N ）と見立てて 6 - 4 = 2 回の移動が必要
*/
};
std::vector<long long> dist(N, 0); //dist[x]：橋xを封鎖した状態でツアーを敢行した際の移動距離の総和の増分
long long d = 0; //どの橋も封鎖されてない状態でツアーを行った場合（全部最短経路を通る）の移動距離の総和
for (int m = 0; m < (M-1); m++) {
int small = std::min(X[m], X[m + 1]);
int large = std::max(X[m], X[m + 1]);
d += std::min(distance(small, large), distance(large, small));
int dist_diff = abs(distance(small, large) - distance(large, small));
if (distance(large, small) < distance(small, large)) {
// 0を通った方が近い場合（橋0～橋small、橋large～のimos法）
dist[0] += dist_diff;//橋xを封鎖すると距離が延びる
dist[small] -= dist_diff;//imos法の調整
dist[large] += dist_diff;//橋xを封鎖すると距離が延びる
}
else {
// 普通に行った方が近い場合（橋small～橋largeのimos法）
dist[small] += dist_diff;//橋xを封鎖すると距離が延びる
dist[large] -= dist_diff;//imos法の調整
}
}
for (int n = 0; n < (N-1); n++) dist[n+1] += dist[n]; //一気に数え上げる（＝累積和をとる）
d += *min_element(dist.begin(), dist.end());
std::cout << d << std::endl;
}おまけ
F問題が最近勉強したbitDPっぽかったので解いてみる。
F Negative Traveling Salesman
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#define INF (1LL<<30)
struct Node {
std::vector<std::pair<int, long long>> children;
};
int main() {
int N, M;
std::cin >> N >> M;
std::vector<Node> Nodes(N);
for (int m = 0; m < M; m++) {
int u, v;
long long w;
std::cin >> u >> v >> w;
u--; v--;
Nodes[u].children.push_back({ v, w });
//Nodes[v].children.push_back({ u, w }); //有向グラフなので逆にはいけない
}
auto dfs = [&](int from) {
std::vector<long long> dist(N, INF);
dist[from] = 0;
std::stack<int> s;
s.push(from);
while (0 < s.size()) {
int tmp = s.top();
s.pop();
if (Nodes.size() <= tmp) continue;
for (auto child : Nodes[tmp].children) {
//if (dist[child.first] == INF)
{
long long tmp_dist = dist[tmp] + child.second;
if (tmp_dist < dist[child.first]) { //値を更新する前に判定する！！
s.push(child.first); //値を更新した時だけスタックに積む
}
dist[child.first] = std::min(dist[child.first], tmp_dist);
}
}
}
return dist;
};
std::vector<std::vector<long long>> distance(N);
for (int n = 0; n < N; n++) distance[n] = dfs(n);
std::vector<std::vector<long long>> dp((1 << N), std::vector<long long>(N, INF));
for (int n = 0; n < N; n++) dp[(1 << n)][n] = 0;
for (int visited = 0; visited < (1 << N); visited++) {
for (int last = 0; last < N; last++) {
if ((((visited >> last) & 1) == 0) && (visited != 0)) continue;
if (dp[visited][last] == INF) continue;
for (int next = 0; next < N; next++) {
if (last == next) continue;
if (((visited >> next) & 1) == 1) continue; //たどりつける全ての場所への最短経路は既に計算済みなので、1度行ったところは行かなくてよい
if (distance[last][next] == INF) continue; //たどりつけない所には行けない
int v = (visited | (1 << next));
dp[v][next] = std::min(dp[v][next], dp[visited][last] + distance[last][next]);
}
}
}
long long ans = INF;
for (int n = 0; n < N; n++) ans = std::min(ans, dp[(1 << N) - 1][n]);
//std::cout << (ans == INF ? "No" : ans) << std::endl;
if (ans == INF) std::cout << "No" << std::endl;
else std::cout << ans << std::endl;
}「ギリギリ解けそうだな～」「青diffではないだろ～」とか思いながらもREが取れずめっちゃ時間かかったけど何とかACできた。
本番でこの問題選べてても今の実力じゃまだ時間内に正解できないから、もっと勉強頑張るしかない。
コメント