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解きたかったな…