ABC251の感想などなど
感想と自分のやった解法をただ書くだけです。
A～Dまでの４完でした。
簡単に解説も載せました。
今回のコンテストのリンクはこちら↓
https://atcoder.jp/contests/abc251
A問題
A問題って感じの簡単な問題。このぐらいの難易度がやっぱA問題って感じがしていい。
stringは足し算で連結できるのでそれで長さが6になるようにする。
#include<bits/stdc++.h>
using namespace std;
int main(){
string S,ans;
cin>>S;
while(ans.size()<6)ans+=S;
cout<<ans<<endl;
}#include<bits/stdc++.h>
using namespace std;
int main(){
string S,ans;
cin>>S;
if(S.size()==1)ans=S+S+S+S+S+S;
if(S.size()==2)ans=S+S+S;
if(S.size()==3)ans=S+S;
cout<<ans<<endl;
}#include<bits/stdc++.h>
using namespace std;
int main(){
string S;
cin>>S;
if(S.size()==1){
cout<<S+S+S+S+S+S<<endl;
}else if(S.size()==2){
cout<<S+S+S<<endl;
}else{
cout<<S+S<<endl;
}
}B問題
全探索する問題。その数が存在するかをフラグとして管理していけばOK。私はめんどくさかったのでsetで管理しました。
O(N³logN)となり、N³logN≒243000000≒2.43×10⁸なのでかなりぎりぎりですが、定数倍が速いので通ります。REP(j,0,N)とすると通らなくなるようです。
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
int main(){
int N,W;
cin>>N>>W;
set<int> ans;
REP(i,0,N){
cin>>A[i];
if(A[i]<=W)ans.insert(A[i]);
}
REP(i,0,N)REP(j,i+1,N)if(A[i]+A[j]<=W){
ans.insert(A[i]+A[j]);
}
REP(i,0,N)REP(j,i+1,N)REP(k,j+1,N){
if(A[i]+A[j]+A[k]<=W)ans.insert(A[i]+A[j]+A[k]);
}
cout<<ans.size()<<endl;
}【5/15追記】
setでTLEする場合、unordered_setに変更するとよい場合があります。
setはほとんどの操作がO(logN)ですが、
unordered_setはならしO(1)でできます。
C問題
まずは問題を整理します。
１．同じ提出があったときは早いときのみを考える
２．最も点数が高いものが何番目か答える
３．点数が同じ時は最も早いものが答え
つまり、オリジナルでないものは考えなくていいですね
さらに、入力順にTが最大になったときのみ更新すれば２と３を満たします
ということでset<string>でオリジナルかを管理して、頭から最大値を更新していきます
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i=a;i<(b);i++)
using namespace std;
int main() {
int N;
cin >> N;
set<string> flags;//フラグ管理
int maxs = -1, index = -1;
REP(i, 0, N) {
string s;
int t;
cin >> s >> t;
if (flags.count(s)) continue;//オリジナルでなければ無視
flags.insert(s);
if (maxs < t) {//最大値を超えたときのみ更新する
maxs = t;
index = i;
}
}
cout<<index+1<<endl;//答えは1-indexed
}正直C問題のほうが簡単ですね
D問題
条件に合う数列を作る問題。
（条件）
１～Wまでの各整数に対して、数列から３つまで選んで作ることができる
【制約】
数列はの要素は1～300個
1≤W≤10⁶
私の考えたことですが、
２進数→20までだから気合で行けないかと思ったけど３つという制約がかなりきつい
今まで出た数のDP→O(N²)で間に合わない
ここまで考えたうえでゆっくり考察しました。
ここで10⁶という数に着目します。
(10²)³です。つまりこれは、100進数で表すと10⁶までの数をすべて表すことができることを意味します。
なので、数列は{1,2,…,99,100,101,…9900,10000,…990000,1000000}となります。
これはWがいくつであっても満たすので常にこれを出力するようにすればACです。
ちなみに、1～99が３桁分と10⁶で298個となり、制約は常に満たしていることがわかります。
#include <bits/stdc++.h>
#define REP(i, a, b) for(int i=a;i<(b);i++)
#define ALL(A) A.begin(),A.end()
using namespace std;
int main() {
int W;
cin>>W;
vector<int> ans;
REP(i, 1, 100) {
ans.push_back(i);
ans.push_back(i * 100);
ans.push_back(i * 10000);
}
ans.push_back(1000000);
sort(ALL(ans));//順番にする必要はありませんがした方が美しいです。
cout<<ans.size()<<endl;
REP(i,ans.size())cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
}前述のようにこれは、どのWに対しても成り立つのでText(Cat)で提出することができます。
提出例
E問題
本番中に解けてません…
考えたことだけメモしておきます。
Nが偶数の時→重複しないように選択するのが２パターンなのでこのmin
Nが奇数の時→ここが実装しきれなかった。
0の時のを求めて1～Nを総和を使ったりしてこねこねしてたらバグりました。
まとめ
今回のABCはそこまで難しくなかったかなという感じ。
B<Cという感じはしたけれども(Bで計算量を気にするのは早い)
Dに関しては発想の問題なので、正直解けなかったかもしれないと振り返っています。
E解きたかったな…