脳の連携が取れていない男の備忘録です
コンテスト概要
AtCoder Beginner Contest 416
開催日:2025年7月26日 21:00-22:40
A - Vacation Validation
考察
文字列を取ってその間が全部oになってるかを確かめる。
こういう素直なA問題、いいと思います。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,l,r;
string s;
cin >> n >> l >> r >> s;
string ans= "Yes";
for(int i=l-1;i<r;i++){//言われた範囲を調べる。
if(s[i] != 'o') ans = "No";//バツが1つでもあるならNo
}
cout << ans << endl;
}
B - 1D Akari
考察
250点問題、少々警戒。
左から順に見ていき、最初に見つけた点はとりあえずOにしても問題がない。
後は2つ目以降だが、間に1回でも#があるならいつでもOが置けるようになる。
というわけで、これまでに#があったかの変数を用意しておき、1回でもあったなら点にOを置いていけばいい。
まあ、B問題なんでこんな考察でいいだろうと提出。
提出
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
bool bef = true;// #の有無を確認する。1番目は置けるのでTRUEスタート
for(int i=0;i<s.length();i++){
if(s[i] == '.' && bef){//現在地点がピリオド、かつ#があったならOに
s[i] = 'o';
bef = false;//いったFALSEにする。
}else if(s[i] == '#') bef = true;//#を見つけたら再びTRUE
}
cout << s << endl;
}
C - Concat (X-th)
考察
計算量が心配になる課題。ただ制約が驚くほどに小さい。
そもそも全部で$10^5$通りしかないし。文字列を全部作ったときの文字数も高々$5\times10^6$文字なのでメモリも大丈夫そう。
というわけで、コンピューターの力を信じてDFSで全列挙作戦決行。
最後にソートしてほしいところだけ出せばOK。
提出
#include <bits/stdc++.h>
using namespace std;
vector<string>ans;
vector<string>str;
void DFS(string s,int k,int n){
if(k == 0){//並べ終わったらvectorに入れる。
ans.push_back(s);
return;
}
k--;//管理数を減らす
for(int i=0;i<n;i++){
string t = s + str[i];
DFS(t,k,n);//文字を追加して次につなぐ
}
return;
}
int main(){
int n,k,x;
cin >> n >> k >> x;
str.resize (n);
for(int i=0;i<n;i++) cin >> str[i];
ans.resize(0);
string s = "";
DFS(s,k,n);//空文字から始めて文字列を生成。
sort(ans.begin(),ans.end());//ソートして小さい順に
cout << ans[x-1] << endl;//X番目(0-indexでX-1番目)を出力
}
D - Match, Mod, Minimize 2
考察
なかなか考察が詰め切れず時間を浪費する。
まずMODを取らないことを考えると当然値は数列A,Bの総和になる。ただ、ペアにして足すだけなので。
じゃあどんな時MODを取ると値が減るのか？それは$A_i + B_j$の和がMODを超えたときのみ。要は和がMODを超えるようなペアをなるべく多く作ればいい。
というわけで、まずは数列Aを大きい順に、数列Bを小さい順に並べる。そして数列Aを前から見ていきMODを超えるものを順にあてがっていく。
なぜ、これでうまくいくのか？
今ある一番小さい値Bについて、一番大きい値Aですら和が超えないなら、値Bは何と組んでも超えないよね。じゃあこのBかなかったことにしよう。という発想。
そして、和がMODを超えたものは値がMODだけ小さくなるので、超えた回数だけ引き算すればOK。
考察一本勝負、今日は行けない日だった。
提出
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
ll m,p;
cin >> m >> p;
ll sum = 0;//とりあえずA,Bの総和を求める
vector<ll>num (m);
for(int j=0;j<m;j++){
cin >> num[j];
sum += num[j];
}
sort(num.begin(),num.end(),greater<ll>());//Aは大きい順
priority_queue<ll,vector<ll>,greater<ll>> que;//Bは小さい順
for(int j=0;j<m;j++){
ll x;
cin >> x;
que.push(x);
sum += x;
}
for(int j=0;j<m;j++){
if(que.empty()) break;//あてがえるBがもうないいならおしまい。
while(!que.empty()){
ll x = que.top();
que.pop();
if(num[j] + x >= p){//AとBの和がmodを超えるなら引き算して次の数へ
sum -= p;
break;
}
}
}
cout << sum << endl;
}
}
E - Development
考察
ぱっとD問題が思いつかなかったので一旦E問題を考える。
空港の存在が厄介なのでハブ空港を作り、そこと結ぶことで計算量の削減を図る。
そしてシンプルにダイクストラ法で全部の距離を求めTLE。
余計なパスが多いので二次元配列で全ペアを管理したうえで実装。TLE。
あらかじめワーシャルフロイド法で距離を求めておき、変更点だけを更新する形で実装。WA。
解説を読む。考察はばっちり。
一体何が駄目なんでしょうか？
結果
ABCD 62:46 4完
順位 2889位
パフォーマンス 1050
レート 1320(-26)
感想
考察はできてるんです。実装が駄目なだけで。
来月の課題は「実装力」ということにします。
JOI過去問解きなおしかな。