AtCoder Beginner Contest 305
結果
A - Water Station : AC(5:09)
B - ABCDEFG : AC(8:48)
C - Snuke the Cookie Picker : AC(19:25)
D - Sleep Log : AC(61:50)
E - Art Gallery on Graph : 提出無し
A - Water Station
全長$${100}$$kmのマラソンコースがあり、コースにはスタートから$${5}$$kmごとに給水所が設置されている
高橋君が$${N}$$km地点にいる時、最寄りの給水所はどこかを求める問題
自分の回答
int main(){
int N;
cin >> N;
if(N % 5 >= 3){
printf("%d\n", N + 5 - N % 5);
}
else{
printf("%d\n", N - N % 5);
}
}そのまま
もっときれいにできないもんかとは思う
公式解説
int main() {
int N;
cin >> N;
cout << ((N + 2) / 5) * 5 << endl;
return 0;
}https://atcoder.jp/contests/abc305/editorial/6533より
そうかそれでいいのか
なるほど
B - ABCDEFG
直線状に$${7}$$個の点$${A,B,C,D,E,F,G}$$が順に並んでいて、各点の間隔は$${3,1,4,1,5,9}$$である
$${2}$$つの英大文字$${p,q}$$が与えられ、その点の間の距離を求める問題
自分の回答
int main(){
vector<int> A(200, 0);
A['B']=3;
A['C']=4;
A['D']=8;
A['E']=9;
A['F']=14;
A['G']=23;
char p, q;
cin >> p >> q;
printf("%d\n",abs(A[p] - A[q]));
}累積和
公式解説
省略
C - Snuke the Cookie Picker
縦$${H}$$マス、横$${W}$$マスのグリッドがあり、その中に縦横$${2}$$マス以上の長方形にクッキーが置かれている
すぬけ君がその中から$${1}$$つクッキーを食べてしまい、その後の状態が与えられる
すぬけ君が食べたクッキーがどこかを求める問題
自分の回答
int main(){
int H, W;
cin >> H >> W;
vector<int> HC(H, 0),WC(W, 0);
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
char c;
cin >> c;
if(c == '#'){
HC[i]++;
WC[j]++;
}
}
}
int h, w;
for(int i = 0; i < H - 1; i++){
if(HC[i] != 0 && HC[i + 1] != 0){
if(HC[i] < HC[i + 1]){
h = i;
}
else if(HC[i] > HC[i + 1]){
h = i + 1;
}
}
}
for(int i = 0; i < W - 1; i++){
if(WC[i] != 0 && WC[i + 1] != 0){
if(WC[i] < WC[i + 1]){
w = i;
}
else if(WC[i] > WC[i + 1]){
w=i+1;
}
}
}
printf("%d %d\n", h + 1, w + 1);
}縦横それぞれでクッキーの数を数えてクッキーがある中で1つ少ない場所が答え
公式解説
省略
D - Sleep Log
高橋君の睡眠記録$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、奇数番目は起床時刻を、偶数番目は就寝時刻を表す
$${l_{i}}$$分から$${r_{i}}$$分の間に高橋君が何分間寝ていたかを$${Q}$$回質問されるため、全て答える問題
自分の回答
int main(){
int N;
cin >> N;
vector<int> A(N), sum(N, 0);
for(int i = 0; i < N; i++){
cin >> A[i];
if(i != 0 && i % 2 == 0){
sum[i - 1] = sum[i - 2];
sum[i] = sum[i - 1] + A[i] - A[i - 1];
}
}
int Q;
cin >> Q;
for(int i = 0; i < Q; i++){
int l, r;
cin>>l>>r;
auto itel = lower_bound(A.begin(), A.end(), l), iter = lower_bound(A.begin(), A.end(), r);
int li = distance(A.begin(), itel), ri =distance(A.begin(), iter);
int ans = sum[ri] - sum[li];
int corl = 0;
if(li % 2 == 0){
corl = A[li] - l;
}
int corr = 0;
if(ri % 2 == 0){
corr = A[ri] - r;
}
printf("%d\n", ans + corl - corr);
}
}基本は累積和だけど時間で取ると配列の要素数がとんでもないから記録のタイミングで作る
lower_boundでl,r以上で一番近い位置を探して累積和
l,rが睡眠時間の中だったらその分補正
公式解説
省略
E - Art Gallery on Graph
$${N}$$頂点$${M}$$辺の単純無向グラフがあり、頂点上に$${K}$$人の警備員がそれぞれ異なる点$${p_{i}}$$にいて体力は$${h_{i}}$$であり、警備員は距離が体力以下の頂点を警備できる
どの頂点が警備されているかを求める問題
自分の回答
警備員の位置から幅優先探索で体力が0になるまで移動しか思いつかなかったけど多分TLEするだろうなとは思った
時間内に書ききれなかったから後で出したけどダメだった
行き先がすでに自身以上の体力で警備したのがいたら終わらせたりして計算量を削減してみたけど足りない
公式解説
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int N, M, K;
cin >> N >> M >> K;
vector<vector<int>> g(N);
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b, --a, --b;
g[a].push_back(b), g[b].push_back(a);
}
vector<int> p(K), h(K);
for (int i = 0; i < K; i++) cin >> p[i] >> h[i], p[i]--;
vector<int> d(N, -1);
priority_queue<pair<int, int>> Q;
auto add = [&](int v, int x) {
if (d[v] < x) Q.emplace(d[v] = x, v);
};
for (int i = 0; i < K; i++) add(p[i], h[i]);
while (Q.size()) {
auto [x, v] = Q.top();
Q.pop();
if (d[v] != x) continue;
for (auto& u : g[v]) add(u, d[v] - 1);
}
vector<int> ans;
for (int i = 0; i < N; i++)
if (d[i] >= 0) ans.push_back(i + 1);
cout << ans.size() << "\n";
for (int i = 0; i < (int)ans.size(); i++)
cout << ans[i] << " \n"[i + 1 == (int)ans.size()];
}https://atcoder.jp/contests/abc305/editorial/6539より
値の大きい順に確定させるダイクストラ法みたいな感じか
なるほど
考えがあと一歩足りなかった感